teorija brojeva

Harmonijski brojevi i Euler-Mascheronijeva konstanta

Tomislav Burić i Lovro Sindičić
[email protected]

Sažetak
U ovom članku uvodimo pojam harmonijskih brojeva i objašnjavamo njihovu vezu s Euler-Mascheronijevom konstantom. Također proučavamo njihovu brzinu rasta povezujući je s logaritamskom funkcijom te prikazujemo neke zanimljive formule pomoću kojih se harmonijski brojevi mogu brzo i lako približno izračunati. Na kraju smo naveli neke primjene i probleme povezane s harmonijskim brojevima.



1Uvod i motivacija

Niz racionalnih brojeva zadan općim članom a_{n}=\frac{1}{n}, n\in\mathbb{N}, zovemo harmonijski niz. Napišimo prvih par članova ovog jednostavnog niza:

1,\ \frac{1}{2},\ \frac{1}{3},\ \frac{1}{4},\ \frac{1}{5},\ \frac{1}{6},\ \dots

Ime mu potječe iz glazbe i teorije valova. Naime, svaki glazbeni ton sastoji se od prostih tonova - harmonika, koji se još nazivaju parcijalni ili alikvotni tonovi. Niz harmonika izgrađen na fundamentalnoj frekvenciji f glasi f, 2f , 3f ,... pri čemu je \lambda, \frac{1}{2} \lambda, \frac{1}{3}\lambda,... niz odgovarajućih valnih duljina harmonika.

U našem članku detaljnije ćemo se pozabaviti zbrojem prvih n članova harmonijskog niza. Takav zbroj nazivamo harmonijski broj i označavamo s H_{n}, odnosno

H_{n}=1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}.

Očigledno je svaki sljedeći harmonijski broj veći od prethodnog (jer su članovi harmonijskog niza pozitivni brojevi), odnosno niz harmonijskih brojeva je rastući. No taj rast je vrlo polagan, zbroj prvih deset članova harmonijskog niza iznosi približno 2.93, prvih sto 5.19, a zbroj prvih 1000 članova je svega 7.49. Prirodno se nameće pitanje je li rastući niz harmonijskih brojeva omeđen odozgo, odnosno konvergira li prema nekoj vrijednosti. Očito je harmonijski niz \frac{1}{n} padajući i teži k nuli, no pokazat ćemo da usprkos tome niz harmonijskih brojeva divergira.

Grupirajmo pribrojnike n-tog harmonijskog broja na sljedeći način:

H_{n}=1+ \underbrace{\frac{1}{2}+\frac{1}{3}}_{\gt \ 2\cdot\frac{1}{4}}+\underbrace{\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}}_{\gt \ 4\cdot\frac{1}{8}}+\underbrace{\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+\frac{1}{11}+\frac{1}{12}+\frac{1}{13}+\frac{1}{14}+\frac{1}{15}}_{\gt \ 8\cdot\frac{1}{16}}+\dots+\frac{1}{n}.

Primjećujemo da su u prvoj grupi oba člana veća od \frac{1}{4} pa je stoga njihov zbroj veći od \frac{1}{2}. Slično, u drugoj grupi je svaki od članova veći od \frac{1}{8} pa je i njihov zbroj veći od \frac{1}{2}. Na isti način vidimo da je svaka daljnja grupa od 2^{n} članova veća od \frac{1}{2}. Dakle, ako H_{n} sadrži k takvih grupa, slijedi H_{n} \gt 1+ \frac{k}{2}. S obzirom da k može biti po volji velik, niz harmonijskih brojeva nije omeđen odozgo, odnosno raste prema beskonačnosti.

Kao što smo već opazili, taj rast je vrlo polagan, da bismo došli do sume 10, trebali bismo zbrojiti preko prvih 12000 članova! Zanima nas kako konkretno možemo predočiti taj rast, to jest možemo li taj rast opisati nekom poznatom funkcijom. Time ćemo se baviti u sljedećem poglavlju.

Uz harmonijske brojeve se blisko veže i jedna zagonetna matematička konstantna o kojoj se još uvijek malo toga zna. Radi se o Euler-Macheronijevoj konstanti koju označavamo s \gamma. Njenu vezu s harmonijskim brojevima objasnit ćemo u trećem poglavlju.

Zatim će nas zanimati kako brzo i lako možemo izračunati n-ti harmonijski broj bez uzastopnog zbrajanja članova niza, odnosno njegovu aproksimaciju. U tu svrhu ćemo prikazati zanimljive formule za približno računanje harmonijskih brojeva.

U posljednjem poglavlju navodimo neke popularne probleme u kojima se prirodno pojavljuju harmonijski brojevi.

2Brzina rasta harmonijskih brojeva

Zaključili smo da niz harmonijskih brojeva sporo raste i divergentan je. Pokazat ćemo da se ta brzina rasta može dobro opisati logaritamskom funkcijom, naime vrijedi sljedeća ocjena

(1)
\ln(n+1)\lt H_{n} \le \ln n+1.

Za dokaz prethodne nejednakosti koristimo se površinom ispod grafa funkcije f(x)=\frac{1}{x} i njenim aproksimacijama danim sumama površina odgovarajućih pravokutnika na segmentu [1, n + 1], odnosno [1, n].

 
Slika 1:


 

Najprije segment [1, n + 1] podijelimo na n jednakih podsegmenata duljine 1. Površina ipod grafa funkcije f(x) = \frac{1}{x} na segmentu [1, n + 1] manja je od sume površina n pravokutnika čija je širina 1, a visina 1, \frac{1}{2}, \frac{1}{3}, \dots, \frac{1}{n}, redom (vidi Sliku 1). Zaista, budući je funkcija f(x) = \frac{1}{x} padajuća, vrijedi f(x)\le \frac{1}{k} za svaki x\in [k, k + 1], i 1\le k \le n. Još kažemo da smo na ovaj način načinili jednu aproksimaciju odozgo. Suma površina ovih n pravokutnika je jedna gornja Darbouxova suma, a nama je zanimljiva jer upravo predstavlja n-ti harmonijski broj H_{n}. S druge strane površina ispod grafa funkcije f(x) =\frac{1}{x} na segmentu [1, n + 1] jednaka je određenom (ili Riemannovom) integralu funkcije f od 1 do n + 1. Korištenjem Newton-Leibnitzove formule dobivamo

\int_{1}^{n+1} \frac{1}{x} \,dx = \ln x \bigg|_{1}^{n+1} = \ln (n+1) - \ln 1 = \ln (n+1),

i time smo pokazali nejednakosti \ln(n+1)\lt H_{n} u (1).

 
Slika 2:


 

Slično, površinu ipod grafa funkcije f(x) = \frac{1}{x} na segmentu [1, n] aproksimiramo odozdo sumom površina n-1 pravokutnika čija je širina 1, a visina \frac{1}{2}, \frac{1}{3}, \dots, \frac{1}{n}, redom (vidi Sliku 2). Ta suma predstavlja jednu donju Darbouxovu sumu i očito je jednaka H_{n}-1. Vrijedi

H_{n}-1 \le\int_{1}^{n} \frac{1}{x}\, dx =\ln n

pa smo opravdali i drugu nejednakost u (1).


3Euler-Mascheronijeva konstanta

Pogledajmo ponovno Sliku 1. Iznad krivulje y=\frac{1}{x} do pune površine pravokutnika nalaze se tamno sjenčani "viškovi" koji postaju sve manji. Primjerice, prvi višak iznosi 1-\ln2=0.307, deseti višak je 0.005, a pedeseti je već 0.0001. Zbrojimo li prvih 50 viškova dobijemo 0.567, a zbroj prvih 1000 viškova je približno 0.577. Pokazat ćemo da njihov zbroj, odnosno niz H_{n}-\ln n doista konvergira prema konstanti koja ima približnu vrijednost 0.5772.

Pokažimo prvo da je taj niz monoton. Razlika dva susjedna člana toga niza

(H_{n} - \ln n) - (H_{n+1} - \ln(n + 1)) = \ln(n + 1) - \ln n - \frac{1}{n + 1}

jednaka je određenom integralu funkcije f(x)=\frac{1}{x}-\frac{1}{n+1} na segmentu [n,n+1], a budući je ta funkcija pozitivna na danom segmentu, njen određeni integral je također pozitivan. Dakle, niz H_{n}-\ln n je padajući. On je i omeđen odozdo s nulom jer vrijedi

H_{n} -\ln n \gt \ln(n + 1) - \ln n \gt 0.

Prvo smo koristili da je H_{n}\gt \ln(n+1) prema (1), a zatim činjenicu da je logaritamska funkcija s bazom e rastuća.

Budući je monoton i omeđen niz realnih brojeva konvergentan, definirat ćemo Euler-Mascheronijevu konstantu \gamma kao limes toga niza

(2)
\gamma = \lim_{n\to\infty} (H_{n} - \ln n ).

Klasifikacija Euler-Mascheronijeve konstante spada među poznatije otvorene probleme u matematici. Naime, još nije pokazano je li \gamma algebarski broj (poput \sqrt{2}, odnosno korijen polinoma s cjelobrojnim koeficijentima) ili transcedentan (poput \pi i e). Štoviše, zanimljivo je da se ne zna ni je li \gamma racionalan ili iracionalan broj! U slučaju da je racionalan, poznato je da bi mu nazivnik bio veći od 10^{242080}, za detalje vidi npr. [6]. Za kraj napišimo precizniju vrijednost te konstante na prvih 50 decimala

\gamma=0.57721566490153286060651209008240243104215933593992...\dots



4Aproksimacije harmonijskih brojeva

Veza (2) nam omogućava da lako odredimo približnu vrijednost n-tog harmonijskog broja bez da moramo redom zbrajati n racionalnih pribrojnika, tj. vrijedi

(3)
H_{n} \approx \gamma+\ln n.

Formula je naravno točnija što je n veći. Primjerice, H_{10}=2.93, a formula nam daje H_{10}\approx 2.88, H_{100}=5.187, a formulom dobijemo H_{100}\approx 5.182, dok je za H_{1000} je još preciznija. No, htjeli bismo ipak bolju točnost, pogotovo za manje harmonijske brojeve. Postoje različita poboljšanja navedene formule, od kojih je najjednostavnija, a pritom i prilično točnija sljedeća:

(4)
H_{n} \approx \gamma+\ln (n+\tfrac{1}{2}).

Još bolja točnost se može dobiti dodavanjem još jednog člana u logaritamsku funkciju

(5)
H_{n} \approx \gamma+\ln (n+\tfrac{1}{2}+\tfrac{1}{24n}).

Dokazano je da vrijedi i sljedeća aproksimacija logaritmom kvadratne funkcije

(6)
H_{n} \approx \gamma+\frac{1}{2}\ln (n^{2}+n+\tfrac{1}{3}),

a nedavno su izvedene i aproksimacije logaritmom nekih racionalnih funkcija koje dodatno poboljšavaju točnost, npr.

(7)
H_{n} \approx \gamma+\ln \frac{n^{3} + \frac{3}{2} n^{2} + \frac{227}{240} n + \frac{107}{480}}{n^{2} + n + \frac{97}{240}}.

U sljedećoj tablici ćemo prikazati usporedbu točnosti navedenih formula na deset decimala. Svaki redak odgovora redom gornjim formulama, dok je u zadnjem retku točna vrijednost n-tog harmonijskog broja. U stupcima su različite vrijednosti broja n.



Formula n=10 n=50 n=100 n=1000
(3) 2.8798007579 4.489238670 5.182385851 7.484970944
(4) 2.9285909221 4.499189001 5.187373392 7.485470819
(5) 2.9289876687 4.499205503 5.187377538 7.485470861
(6) 2.9289687083 4.499205339 5.187377518 7.485470861
(7) 2.9289682521 4.499205338 5.187377518 7.485470861
H_{n} 2.9289682539 4.499205338 5.187377518 7.485470861


Za detalje o ovim formulama i njihovim izvodima, kao i ostale najnovije formule za aproksimaciju harmonijskih brojeva, koje zahtijevaju malo složeniju matematičku analizu i poznavanje asimptotike, pogledajte [1].

5Zanimljivosti i primjene

Za kraj navedimo neke od zanimljivih primjena i problema povezanih s harmonijskim brojevima.

Analiza obaranja rekorda. Primjerice, u meteorologiji nas zanima koliko će puta u nizu od n godina biti oboren temperaturni rekord ili najveća količina padalina. Uz pretpostavku da su vremenski uvjeti slučajni i neovisni o prethodnim godinama, broj oborenih rekorda u n godina je upravo jednak harmonijskom broju H_{n}. Npr. u 100 godina, H_{100}\approx 5.19 puta će biti oboren temperaturni rekord ljeti ili rekordna količina snježnih padalina zimi. Detaljnije o ovom problemu može se saznati u [4].

Problem sakupljanja kupona. Pretpostavimo da želimo sakupiti sve sličice za album Životinjskog carstva ili sve sličice nogometaša za aktualni album svjetskog prvenstva. Definirajmo slučajnu varijablu X kao broj kupljenih kupona kojima smo popunili cijeli album od n sličicu te neka slučajna varijabla X_{i} predstavlja broj kupnji kojima smo dobili novu sličicu nakon što smo već sakupili i-1 sličica, i=1,...n. Budući slučajna varijabla X_{i} mjeri broj ponavljanja slučajnog pokusa do prve realizacije povoljnog događaja, ona ima geometrijsku razdiobu s vjerojatnosti p_{i}=\frac{n-(i-1)}{n} čije je očekivanje E(X_{i})=\frac{1}{p_{i}}, vidi npr. [3]. Zbog linearnosti očekivanja slijedi

E(X)=E(X_{1})+\dots+E(X_{n})=\frac{n}{n}+\frac{n}{n-1}+\dots+\frac{n}{1}=n\left(\frac{1}{n}+\frac{1}{n-1}+\dots+1\right),

odnosno očekivani broj kupnji da bismo sakupili sve sličice jednak je n\,H_{n}. Primjerice, za popuniti album od 50 sličica, u prosjeku ćemo morati kupiti 50\, H_{50}\approx 225 kupona ili čokoladica sa sličicama.

Crvić na gumenoj traci. Crvić puzi konstantnom brzinom od 1 centimetar po minuti s jednog kraja trake na drugi, no gumena traka duga 1 metar se svake minute rastegne za još 1 metar. Preciznije, nakon prve minute crvić je prešao 1 cm, tj. 1/100 dio trake, no budući se ona rastegnula na 2 metra, ostalo mu je još 198 cm. U drugoj minuti je prešao 1/200 dio trake, tj. ukupno 3 cm, no nakon rastezanja nalazi se 4.5 cm od početka, odnosno treba puzati još 295.5 cm. Pitanje je hoće li na taj način crvić ikada dopuzati do kraja trake? Crvićev put nakon n minuta jednak je

\frac{1}{100}+\frac{1}{200}+\dots+\frac{1}{100n}=\frac{H_{n}}{100}

te zbog neomeđenosti niza harmonijskih brojeva, H_{n} može biti dovoljno velik tako da crvić doista dođe do kraja trake, ali će mu trebati jako puno vremena. Za detalje o ovom zanimljivom problemu pogledajte [8].

Problem postavljanja pločica. Radi se o matematičko-fizičkom problemu postavljanja n istih pločica (ili n knjiga istih dimenzija i mase) na rub stola na način da je svaka pločica pomaknuta malo dalje preko ruba stola od prethodne, a tako da se cijela konstrukcija ne sruši (vidi Sliku 3). Takva konstrukcija će ostati stabilna ako se težište sistema od n postavljenih pločica nalazi najviše do ruba stola, inače će se srušiti. U [5] je objašnjen ovaj problem i pokazano je da maksimalna udaljenost od ruba stola za n pločica duljine 2 cm iznosi upravo H_{n}. Zbog neomeđenosti niza harmonijskih brojeva, H_{n} može biti po volji velik, odnosno pločice se mogu poslagati jedna na drugu po volji daleko preko ruba stola, a tako da cijela konstrukcija ne padne sa stola!

 
Slika 3:


 

Bibliografija
[1] T. Burić, N. Elezović, Approximants of the Euler-Mascheroni constant and harmonic numbers, Applied Mathematics and Computation 222 (2013), 604-611.
[2] N. Elezović, Gama funkcija i Bernoullijevi brojevi, skripta iz kolegija Kompleksna analiza, FER, Zagreb, http://www.fer.unizg.hr/_download/repository/Elezovic_-_skripta3.pdf
[3] N. Elezović, Vjerojatnost i statistika, Diskretna vjerojatnost, Element, Zagreb, 2007.
[4] F.G. Foster, A. Stuart, Distribution-free Tests in Time-Series Based on the Breaking of Records, Journal of the Royal Statistical Society 16 (1954), 1-22.
[5] Ž. Hanjš, Statika stupca domina i harmonijski brojevi, Matematičko-fizički list LIV, 2003./04.
[6] J. Havil, Gamma: Exploring Euler's Constant, Princeton University Press, 2003.
[7] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison Wesley Publishing Company, 1995.
[8] D. Žubrinić, Harmonijski brojevi, Matematičko-fizički list LII, 2001./02.
 

 

  • Share this

Matrice s Fibonaccijevim brojevima

Blaženka Bakula,
Magistra edukacije matematike, zaposlena u Srednjoj školi A.B.Šimića, Grude, BiH, [email protected]		 Zrinka Franušić
Docentica na PMF-Matematičkom odsjeku u Zagrebu, [email protected]
 

U prostranstvu cjelobrojnih nizova Fibonaccijev niz ne gubi svoj sjaj već više od osam stoljeća, točnije od kad se pojavio u knjizi Liber Abaci talijanskog matematičara Leonarda Bonaccija1 poznatog i kao Leonardo Pisano, a najpoznatijeg kao Fibonacci. Bez pretjerivanja, riječ je o jednom od najpoznatijih nizova koji privlači i fascinira kako profesionalce tako i potpune amatere. Nadalje, neprestano iznenađuje sa svojom prisutnošću u očekivanim, ali i potpuno neočekivanim situacijama. O Fibonaccijevim brojevima postoji vrlo velika količina informacija, mnoštvo publikacija, knjiga, te internetskih sadržaja. U ovom radu pokazat ćemo i dokazati neke zanimljive identitete vezane uz Fibonaccijeve brojeve koristeći jednostavnu algebru matrica i determinanti. Između ostalog, pokazujemo i poznati Cassinijev2 identitet koji se se može povezati s problemom popločavanja. Zbog mlađeg čitateljstva navest ćemo osnovna svojstva Fibonaccijevog niza, te osnovne pojmove iz linearne algebre.

1Fibonaccijevi brojevi

Fibonaccijev niz je niz brojeva

1,1,2,3,5,8,13,21,34,55,\ldots.

Niz bi s lakoćom nastavili članom 89 koji je zbroj prethodna dva. Iskažimo njegovu matematičku definiciju.

Definicija 1. Neka je F_{1}=1 i F_{2}=1. Niz (F_{n}) definiran rekurzivnom relacijom
(1)
F_{n}=F_{n-1}+F_{n-2},
za n\geq 3 naziva se Fibonaccijev niz. Član niza F_{n} zove se n-ti Fibonaccijev broj.

Napomenimo da se ponekad za početne vrijednosti niza uzimaju vrijednosti F_{0}=0 i F_{1}=1.

U već spomenutoj knjizi Liber Abaci taj niz predstavlja rješenje problema o razmnožavanju zečeva. Pretpostavimo da 1. siječnja raspolažemo s jednim parom zečeva. Taj par dobiva po jedan par mladih zečeva svakog prvog dana u mjesecu, počevši od 1. ožujka. Svaki novi par dobiva po jedan par zečeva svakog prvog dana u mjesecu, ali tek nakon navršena dva mjeseca života. Problem je koliko će parova zečeva biti nakon n mjeseci. Odgovor je upravo n-ti Fibonaccijev broj F_{n}.



Slika 1: Razmnožavanje zečeva (crveni zeko označava par novorođenih, a zeleni par star bar jedan mjesec)


Eksplicitno, Fibonaccijeve brojeve možemo izračunati pomoću formule

F_{n}=\frac{1}{\sqrt{5}}(\alpha^{n}-\beta^{n}),

pri čemu su \alpha i \beta korijeni takozvane zlatne jednadžbe

x^{2}-x-1=0,

to jest

\alpha=\frac{1+\sqrt{5}}{2},\ \beta=\frac{1-\sqrt{5}}{2}.

Konstanta \alpha poznatija je pod nazivom zlatni rez.

Uz Fibonaccijev niz često se veže i Lucasov3 niz (L_{n}) koji je definiran istom rekurzijom (1).

Definicija 2. Neka je L_{0}=2 i L_{1}=1. Niz (L_{n}) definiran rekurzivnom relacijom
(2)
L_{n}=L_{n-1}+L_{n-2},
za n\geq 2 naziva se Lucasov niz.

Predodžbe radi, prvih nekoliko članova Lucasova niza su

2,1,3, 4, 7, 11, 18, \ldots .

Eksplicitno ih računamo pomoću formule

L_{n}=\alpha^{n}+\beta^{n}.

Fibonaccijevi i Lucasovi brojevi zadovoljavaju različite algebarske identitete. Budući da su generirani rekurzivnim relacijama (1) i (2), prirodno je takve identitete dokazivati pomoću principa matematičke indukcije. Prisjetimo ga se. Ako je neka tvrdnja točna za broj 1 i ako iz pretpostavke da tvrdnja vrijedi za prirodni broj n slijedi da je ispravna i za sljedeći broj n+1, tada ona vrijedi za svaki prirodni broj n.

Kao primjer navodimo osnovnu relaciju koja povezuje Fibonaccijeve i Lucasove brojevi, to jest

(3)
L_{n}=F_{n-1}+F_{n+1},

za n\geq 1. Jednakost pokazujemo pomoću principa matematičke indukcije. Za n=1 jednakost vrijedi jer je

F_{0}+F_{2}=1=L_{1}.

Pretpostavimo sada da jednakost vrijedi za n=k, odnosno L_{k}=F_{k-1}+F_{k+1}. Za n=k+1 imamo

\begin{align*} F_{k}+F_{k+2}=&F_{k-1}+F_{k-2}+F_{k+1}+F_{k} =(F_{k-1} + F_{k+1} + (F_{k-2} + F_{k}) =L_{k}+L_{k-1} =L_{k+1}, \end{align*}

što je i trebalo pokazati.
U onom što slijedi pokazat ćemo kako možemo dokazati i izvesti još identiteta s Fibonaccijevim i Lucasovim brojevima koristeći elementarna svojstva matrica.



2Matrice i determinante reda 2

Matrica reda 2 je kvadratna shema koja se sastoji od 4 elementa posložena u 2 retka i 2 stupca. Simbolički ju zapisujemo kao

A=\left( \begin{array}{rr} a_{11} &a_{12} \\\ a_{21} &a_{22} \end{array} \right).

Elementi matrice a_{11}, a_{12}, a_{21}, a_{22} su najčešće realni brojevi, pa takvu matricu nazivamo realnom. Elementi matrice su indeksirani tako da nas upućuju na kojoj se poziciji u matrici nalaze. Tako se element a_{21} nalazi na presjeku drugog retka i prvog stupce. Na skupu svih matrica reda 2 jednostavno uvodimo dvije operacije, zbrajanje matrica i množenje matrica skalarom (realnim brojem). Te se operacije izvršavaju prirodno, 'po elementima'. Dakle,

A+B=\left( \begin{array}{rr} a_{11} &a_{12} \\\ a_{21} &a_{22} \end{array} \right)+\left( \begin{array}{rr} b_{11} &b_{12} \\\ b_{21} &b_{22} \end{array} \right)=\left( \begin{array}{rr} a_{11}+b_{11} &a_{12}+b_{12} \\\ a_{21}+b_{21} &a_{22}+b_{22} \end{array} \right),
\alpha\cdot A=\alpha\left( \begin{array}{rr} a_{11} &a_{12} \\\ a_{21} &a_{22} \end{array} \right)=\left( \begin{array}{rr} \alpha a_{11} &\alpha a_{12} \\\ \alpha a_{21} &\alpha a_{22} \end{array} \right).

Na primjer,

\left(\begin{array}{rr} 1 &2 \\\ 3 &4 \end{array} \right)+\left( \begin{array}{rr} -4 &-3 \\\ -2 &-1 \end{array} \right)=\left( \begin{array}{rr} -3 &-1 \\\ 1 &3 \end{array} \right),
3\left( \begin{array}{rr} 1 &2 \\\ -1 &0 \end{array} \right)=\left( \begin{array}{rr} 3 &6 \\\ -3 &0 \end{array} \right).

Množenje matrica ne ćemo definirati po analogiji i to je prilično neočekivano. Umnožak ili produkt dviju matrica definiramo na sljedeći način

A\cdot B=\left( \begin{array}{rr} a_{11} &a_{12} \\\ a_{21} &a_{22} \end{array} \right)\cdot\left( \begin{array}{rr} b_{11} &b_{12} \\\ b_{21} &b_{22} \end{array} \right)= \left(\begin{array}{rr} a_{11}b_{11}+a_{12}b_{21} &a_{11}b_{12}+a_{12}b_{22} \\\ a_{21}b_{11}+a_{22}b_{21} &a_{21}b_{12}+a_{22}b_{22} \end{array}\right).

Na primjer,

\left(\begin{array}{rr} 1 &2 \\\ 3 &4 \end{array} \right)\cdot\left( \begin{array}{rr} -4 &-3 \\\ -2 &-1 \end{array} \right)=\left( \begin{array}{rr} -8 &-5 \\\ -20 &-13 \end{array}\right).

Zbog ovakve 'neobične' definicije i množenje matrica imat će neka 'neobična' svojstva. Na primjer, općenito ne će vrijediti svojstvo komutativnosti.

Uz matricu reda 2 često vežemo i pojam determinante. To je broj koji pridružujemo matrici, a definiramo ga kao

\det A=|A|= a_{11} a_{22}-a_{12}a_{21}.

Zahvaljući 'neobično' definiranom množenju matrica vrijedit će sljedeće važno svojstvo, u matematici poznatije kao Binet-Cauchyjev teorem,

|A\cdot B|=|A|\cdot|B|.

Provjerimo to na gornjem primjeru,

\left|\begin{array}{rr} 1 &2 \\\ 3 &4 \end{array} \right|=-2,\ \left| \begin{array}{rr} -4 &-3 \\\ -2 &-1 \end{array} \right|= -2,\left| \begin{array}{rr} -8 &-5 \\\ -20 &-13 \end{array}\right|=4.


3Identiteti s Fibonaccijevim i Lucasovim brojevima

Matricu Q definirat ćemo kao

Q=\left( \begin{array}{rr} 1 &1 \\\ 1 &0 \end{array} \right).

Primijetimo da je determinanta matrice Q jednaka |Q| =-1. Nadalje, vrijedi

Q^{2}= \left( \begin{array}{rr} 1 &1 \\\ 1 &0 \end{array} \right) \left( \begin{array}{rr} 1 &1 \\\ 1 &0 \end{array} \right) = \left( \begin{array}{rr} 2 &1 \\\ 1 &1 \end{array} \right),
Q^{3}=\left( \begin{array}{rr} 1 &1 \\\ 1 &0 \end{array} \right) \left( \begin{array}{rr} 2 &1 \\\ 1 &1 \end{array} \right)= \left( \begin{array}{rr} 3 &2 \\\ 2 &1 \end{array} \right),
Q^{4}= \left( \begin{array}{rr} 1 &1 \\\ 1 &0 \end{array} \right) \left( \begin{array}{rr} 3 &2 \\\ 2 &1 \end{array} \right)=\left( \begin{array}{rr} 5 &3 \\\ 3 &2 \end{array} \right).

Uočimo da se u matricama Q^{2}, Q^{3}, Q^{4} pojavljuju Fibonaccijevi brojevi. Nije teško pretpostaviti kako će izgledati matrica Q^{n}.

Teorem 3. Neka je n\geq1. Tada
(4)
Q^{n}=\left( \begin{array}{rr} F_{n+1} &F_{n} \\\ F_{n} &F_{n-1} \end{array} \right).

Dokaz 4. Neka je n=1.
Q^{1}=\left( \begin{array}{rr} F_{2} &F_{1} \\\ F_{1} &F_{0} \end{array} \right)\left( \begin{array}{rr} 1 &1 \\\ 1 &0 \end{array} \right)=Q.
Pretpostavimo da (4) vrijedi za n=k\geq1. Želimo pokazati da (4) vrijedi za n=k+1. Zaista,
Q^{k+1}=Q^{k} Q^{1}=\left( \begin{array}{rr} F_{k+1} &F_{k} \\\ F_{k} &F_{k-1} \end{array} \right) \left( \begin{array}{rr} 1 &1 \\\ 1 &0 \end{array} \right)= \left( \begin{array}{rr} F_{k+1}+F_{k} &F_{k+1} \\\ F_{k} + F_{k-1} &F_{k} \end{array} \right) = \left( \begin{array}{rr} F_{k+2} &F_{k+1} \\\ F_{k+1} &F_{k} \end{array} \right).
Prema principu matematičke indukcije slijedi da formula (4) vrijedi za svaki n\in\mathbb{N}.


Pomoću Teorema 3 dokazujemo poznatu Cassinijevu formulu za Fibonaccijeve brojeve.

Korolar 5.[Cassinijeva formula] Neka je n\geq 1. Tada je
(5)
F_{n-1}F_{n+1}-F_{n}^{2}=(-1)^{n}.

Dokaz 6. Budući da je |Q| =-1, prema Binet-Cauchyjevom teoremu slijedi da je |Q^{n}| =(-1)^{n}. Iz Teorema 3 slijedi da je |Q^{n}|=F_{n-1}F_{n+1}-F_{n}^{2}, pa je
F_{n-1}F_{n+1}-F_{n}^{2}=(-1)^{n}.


Kombinatorni dokaz i interpretaciju jednakosti (5) dat ćemo u sljedećem poglavlju. Nadalje, kao posljedicu Teorema 3 imamo i sljedeće četiri jednakosti:

Korolar 7. Vrijedi
(6)
\begin{eqnarray} && F_{m+n+1}=F_{m+1}F_{n+1} +F_{m} F_{n},\\\ && F_{m+n}=F_{m+1} F_{n} + F_{m} F_{n-1},\\\ && F_{m+n}=F_{m} F_{n+1} + F_{m-1}F_{n},\\\ && F_{m+n-1}=F_{m} F_{n}+F_{m-1}F_{n-1} \end{eqnarray}
za sve m,n\geq1.

Dokaz 8. Budući da je Q^{m} Q^{n}=Q^{m+n}, imamo
\left( \begin{array}{rr} F_{m+1} &F_{m} \\\ F_{m} &F_{m-1} \end{array} \right) \left( \begin{array}{rr} F_{n+1} &F_{n} \\\ F_{n} &F_{n-1} \end{array} \right) = \left( \begin{array}{rr} F_{m+n+1} &F_{m+n} \\\ F_{m+n} &F_{m+n-1} \end{array} \right).
Množenjem matrica dobivamo
\left( \begin{array}{rr} F_{m+1}F_{n+1}+F_{m}F_{n} &F_{m+1}F_{n}+F_{m}F_{n-1} \\\ F_{m}F_{n+1}+F_{m-1}F_{n} &F_{m}F_{n}+F_{m-1}F_{n-1} \end{array} \right) = \left( \begin{array}{rr} F_{m+n+1} &F_{m+n} \\\ F_{m+n} &F_{m+n-1} \end{array} \right)
odkuda slijede tražene jednakosti.


Neka je m=n. Tada jednakost (6) daje formulu za računanje Fibonaccijevih brojeva s neparnim indeksom

F_{n}^{2} +F_{n+1}^{2} =F_{2n+1},

a jednakost (6) formulu za računanje Fibonaccijevih brojeva s parnim indeksom

F_{2n}=F_{n+1} F_{n} + F_{n} F_{n-1}=F_{n} (F_{n+1}+F_{n-1}),

odnosno

F_{2n}=F_{n}L_{n}.


Korolar 9. Vrijedi
F_{m+1}L_{n}+F_{m}L_{n-1}=L_{m+n}
za m\geq0, n\geq1. \end {cor}

Dokaz 10. Zbrajanjem jednakosti (6) i jednakosti F_{m+n-1} = F_{m+1}F_{n-1} + F_{m}F_{n-2} koju smo dobili zamjenom n s n-1 u (6), dobivamo
F_{m+1}(F_{n+1} + F_{n-1}) + F_{m}(F_{n} + F_{n-2}) = F_{m+n+1} + F_{m+n-1}.
Primjenom jednakosti (3) slijedi
F_{m+1}L_{n} + F_{m}L_{n-1} = L_{m+m},
što je i trebalo dokazati.


Evo još jedne jednakosti koji povezuje Fibonaccijeve i Lucasove brojeve.

Korolar 11. Vrijedi
(7)
2F_{m+n}=F_{m}L_{n}+F_{n}L_{m}
za m,\,n\geq0. \end {cor}

Dokaz 12. Zbrajanjem jednakosti (6) i (6) dobivamo
2F_{m+n}=F_{m}(F_{n-1}+ F_{n+1}) + F_{n} ( F_{m+1}+F_{m-1})=F_{m}L_{n}+F_{n}L_{m} .

Teorem 13. Vrijedi
Q^{n}\left( \begin{array}{rr} 1 &2 \\\ 2 &-1 \end{array} \right)=\left( \begin{array}{ll} L_{n+1} &L_{n} \\\ L_{n} &L_{n-1} \end{array} \right).

Dokaz 14.
Q^{n}\left( \begin{array}{rr} 1 &2 \\\ 2 &-1 \end{array} \right)= \left( \begin{array}{ll} F_{n+1} &F_{n} \\\ F_{n} &F_{n-1} \end{array} \right)\left( \begin{array}{rr} 1 &2 \\\ 2 &-1 \end{array} \right)=\left(\begin{array}{rr} F_{n+1}+2F_{n} &2F_{n+1}-F_{n} \\\ F_{n}+2F_{n-1} &2F_{n}-F_{n-1} \end{array} \right).
Primjenom jednakosti (3) dobivamo traženu jednakost. Na primjer,
F_{n+1}+2F_{n}=F_{n+1}+F_{n}+F_{n}=F_{n+2}+F_{n}=L_{n+1}.

Korolar 15. Vrijedi
(8)
L_{n-1}L_{n+1}-L_{n}^{2}=5(-1)^{n+1}.

Dokaz 16. Prema Teoremu 13 i Binet-Cauchyjevom teoremu slijedi
\left| \begin{array}{rr} F_{n+1} &F_{n} \\\ F_{n} &F_{n-1} \end{array} \right|\left| \begin{array}{rr} 1 &2 \\\ 2 &-1 \end{array} \right|=\left| \begin{array}{rr} L_{n+1} &L_{n} \\\ L_{n} &L_{n-1} \end{array} \right|.
Dakle
(F_{n+1}F_{n-1}-F_{n}^{2})(-5)=L_{n+1}L_{n-1}-L_{n}^{2},
pa primjenom Cassinijeve formule (5) dobivamo traženi identitet.

4Cassinijeva formula i domino

Na kraju dajemo još jednu zanimljivu interpretaciju Fibonaccijevih brojeva pomoću koje se može pokazati Cassinijeva formula (5). Radi se o popločavanju ploče dimenzije 2\times n pomoću domino pločica dimenzije 1\times 2 koje možemo postaviti vertikalno (crvena pločica) ili horizontalno (bijela pločica). Označimo s T_{n} broj načina na koji se može izvesti.


Slika 2: Popločavanje može započeti na točno ova dva načina (uokvireno plavo)


Budući da popločavanje možemo započeti ili s jednom vertikalno postavljenom pločicom ili s dvije horizontalno postavljene (vidi Sliku 2) slijedi da je
T_{n}=T_{n-1}+T_{n-2}.
Kako je T_{1}=1 i T_{2}=2, zaključujemo da je T_{n}=F_{n-1} jer imamo istu rekurziju kao za Fibonaccijeve brojeve, samo su početni (pa onda i svi ostali) članovi niza pomaknuti za jedno mjesto. Sada ćemo proučiti popločavanje dviju ploča istih dimenzija. Broj načina na koji možemo popločati te dvije ploče je T_{n}^{2}. Zbog jednostavnosti umjesto ploče dimenzije 2\times n koju popločavamo pločicama dimenzije 1\times 2 možemo promatrati ploču dimenzije 1\times n koju popločavamo pločicama dimenzije 1\times 1 i 1\times 2 (Slika 3). Uočimo da dva popločavanja na Slici 3 upravo odgovaraju dvama popločavanjima na Slici 2.


Slika 3: Popločavanje pločicama dimenzije 1\times 1 i 1\times 2


Slika 4: Pomaknute ploče dimenzije 1\times n s istaknutim crtama loma

Sada donju ploču pomaknimo za jedno mjesto udesno i pogledajmo na koliko mjesta možemo 'prelomiti' i gornju i donju ploču istovremeno, a da pritom ne lomimo domino pločice. Na primjeru sa Slike 4 to se može učiniti na točno 3 mjesta. Reći ćemo da u ovom slučaju imamo 3 crte loma. Posljednju crtu loma označili smo plavom bojom. Sada zamijenimo dijelove ploče ('repove') koje se nalaze s desnih strana plave crte (Slika 5). Na taj način se gornja ploča povećala za točno jedno mjesto, a donja smanjila za jedno. Uočimo da se broj crta loma se nije promijenio. Općenito možemo zaključiti da postoji bijekcija između skupa svih mogućih popločavanja dviju ploča iste dimenzije 1\times n i skupa svih mogućih popločavanja dviju ploča dimenzija 1\times (n+1) i 1\times (n-1) uz pretpostavku da su to popločavanja s barem jednom crtom loma.


Slika 5: Ploče dimenzije 1\times (n+1) i 1\times (n-1) nastale nakon zamjene 'repova'


Sada nam preostaje prebrojati načine popločavanja u kojima se ne pojavljuje prijelom. Ukoliko je n paran pojavit će se točno jedno takvo popločavanje dviju ploča iste dimenzije 1\times n, dok svako popločavanje dviju ploča dimenzija 1\times (n+1) i 1\times (n-1) uvijek ima crtu loma jer je broj polja na pločama neparan (pa u popločavanje moramo uključiti pločicu dimenzije 1\times 1). Točno obratno se dešava ako je n neparan (Slika 6, 7). Stoga smo opravdali formulu
T_{n}^{2}-T_{n-1}\cdot T_{n+1}=(-1)^{n},
što uz T_{n}=F_{n-1} upravo predstavlja Cassinijevu formulu (5).


Slika 6: Popločavanje ploča dimenzije 1\times n, n paran, koje nema crte loma


Slika 7: Popločavanje ploča dimenzije 1\times (n+1) i 1\times (n-1), n neparan, koje nema crte loma
Bibliografija
[1] B. Bakula, Fibonaccijeve matrice i determinante, diplomski rad, PMF - Matemački odsjek, Sveučilište u Zagrebu, 2013.
[2] A. Dujella, Fibonaccijevi brojevi, HMD, Zagreb, 2000.
[3] T. Koshy, Fibonacci and Lucas numbers with applications, John Wiley \& Sons, 2001.
[4] Cassini's Identity, dostupno na http://www.cut-the-knot.org/arithmetic/algebra/CassinisIdentity.shtml
[5] Fibonacci Tilings, dostupno na http://www.cut-the-knot.org/arithmetic/combinatorics/FibonacciTilings.sh...
 
1najtalentiraniji europski matematičar srednjeg vijeka (1170.-1250.)
2Giovanni Domenico Cassini, talijanski matematičar, astronom, inženjer (1625.-1712.)
3François Édouard Anatole Lucas, francuski matematičar (1842.-1891.)

 

  • Share this

Fibonaccijev brojevni sustav

 
Ljerka Jukić
asistentica Odjela za matematiku
Sveučilišta u Osijeku
[email protected]		 Helena Velić
studentica Odjela za matematiku
Sveučilišta u Osijeku
[email protected]

 

Sažetak
U ovom članku prikazujemo kako pomoću Fibonaccijevih brojeva izgraditi brojevni sustav.

1Uvod

Najveći matematičar srednjeg vijeka, Leonardo iz Pise, poznatiji kao Fibonacci, otkrio je neobičan matematički niz koji danas nosi njegovo ime. Fibonaccijev niz čine brojevi 1,\, 1,\, 2,\, 3,\, 5,\, 8,\, 13,\, 21,\ldots pri čemu se svaki sljedeći broj računa kao zbroj prethodnih dvaju u nizu. Elementi Fibonaccijeva niza nazivaju se i Fibonaccijevi brojevi. Fibonacci je do tog otkrića došao promatrajući razmnožavanje zečeva u prirodi, te pokušavajući predvidjeti koliko će parova zečića podignuti jedan par zečjih roditelja u jednoj godini. Očito, navedeni niz možemo definirati i rekurzivnom relacijom F_{n}=F_{n-1}+F_{n-2},\,\, F_{1}=1,\, F_{2}=1.
Zanimljivu primjenu Fibonaccijevih brojeva nalazimo pri njihovu korištenju kao baze za prikazivanje prirodnih brojeva. U toj se bazi prirodni brojevi prikazuju kao sume nekoliko Fibonaccijevih brojeva, no postoje određene prepreke koje najprije valja ukloniti kako bi prikaz bio jedinstven.

Fibonaccijev brojevni sustav povezuje razne grane matematike, kao što su kombinatorika i teorija brojeva, s određenim dijelovima teorijskog računarstva poput kriptografije i algoritama za pretraživanje podataka. U računarstvu se osobito pokazao korisnim za sustave u kojima se podaci serijski pohranjuju i traže [1]. Također, prilikom kompresija digitalnih fotografija pokazuje znatne prednosti nad klasičnom LBS metodom koja koristi se binarnim brojevnim sustavom [6]. Osim toga, prikazivanje prirodnih brojeva u Fibonaccijevoj bazi omogućilo je jednostavno kodiranje podataka stvaranjem nizova u kojima se brzo može utvrditi gdje jedan podatak završava, a drugi počinje. Prirodnim proširivanjem Fibonaccijeva brojevnog sustava dobiveni su novi sustavi koji svoju ulogu također pronalaze u računarstvu, jer uz određene uvjete ponovno imaju značajne prednosti kod izvođenja osnovnih aritmetičkih operacija u odnosu na klasični binarni brojevni sustav.

2Fibonaccijev brojevni sustav

U matematici se za prikaz prirodnih brojeva koriste različiti brojevni sustavi. Najpoznatiji su binarni i dekadski. U binarnom sustavu prirodne brojeve prikazujemo kao sumu potencija broja 2 koje množimo znamenkama 0 i 1, dok u dekadskom brojeve prikazujemo kao sumu potencija broja 10 koje množimo znamenkama 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9.

Fibonaccijev brojevni sustav je onaj u kojem brojeve prikazujemo kao sumu Fibonaccijevih brojeva. Dakle, neki prirodni broj N možemo prikazati kao
N=a_{n-1}F_{n+1}+\ldots+a_{2}F_{4}+a_{1}F_{3}+a_{0}F_{2},
gdje je su F_{i} brojevi Fibonaccijeva niza koji zadovoljavaju relaciju F_{i}=F_{i-1}+F_{i-2},\,\, F_{2}=1=F_{2}, te je a_{i}\in \lbrace 0,1\rbrace. Ovaj sustav sličan je binarnom brojevnom sustavu, jer se koristi samo znamenkama 0 i 1, ali za razliku od binarnog brojevnog sustava, čija je baza broj 2, u ovom sustavu baza su Fibonaccijevi brojevi.

Primjer 1.Prikažimo broj 8 u Fibonaccijevu brojevnom sustavu.
8=F_{6}=F_{5}+F_{4}=F_{5}+F_{3}+F_{2}=F_{5}+F_{3}+F_{1}
Kao što vidimo, broj 8 možemo prikazati na nekoliko načina s pomoću Fibonaccijevih brojeva. Bolji pregled daje nam sljedeća tablica.



F_{i}  F_{6} F_{5} F_{4} F_{3} F_{2} F_{1}
Vrijednost  8 5 4 3 2 1
a_{i}  1 0 0 0 0 0
  0 1 1 0 0 0
  0 1 0 1 1 0
  0 1 0 1 0 1

Za prikaz broja 8 u Fibonaccijevoj bazi uzeli smo četiri Fibonaccijeva broja, a pojavilo se nekoliko prikaza. To nam govori da za prirodne brojeve u Fibonaccijevoj bazi nećemo dobiti jedinstven prikaz broja jer postoji više od jednog načina kako bismo prikazali taj broj. Kako možemo urediti novi brojevni sustav u kojem će prikazi prirodnih brojeva biti jedinstveni?



Do nejedinstvenosti dolazi zbog dva razloga:
(1) F_{2}=F_{1}=1
Ovaj problem rješavamo tako da odlučimo koji ćemo od ta dva broja upotrijebiti u prikazu.
(2) F_{i}=F_{i-1}+F_{i-2}

U prikazu možemo izabrati F_{i} ili F_{i-1}+F_{i-2}. Na ovaj način dobivamo najkraći ili najdulji mogući prikaz. Prirodno je odabrati najkraći prikaz.
Sljedeća dva teorema pokazuju nam kako zaista dobivamo brojevni sustav s jedinstvenim prikazom brojeva ako napravimo ova dva izbora [3].

Teorem 2. (Zeckendorf)Svaki prirodan broj N može se prikazati kao zbroj različitih Fibonaccijevih brojeva
N=F_{i_{1}}+F_{i_{2}}+\ldots+F_{i_{r}}
tako da je pritom i_{k+1}\leq i_{k}-2 za k=1, 2, \ldots,r-1 te je i_{r}\geq 2.

Dokaz.Dokaz teorema provodimo matematičkom indukcijom. Za N=1 tvrdnja je točna jer je F_{2}=1. Pretpostavimo da je N\geq 2 prirodan broj te da je tvrdnja točna za sve brojeve manje od N. Sada preostaje dokazati korak indukcije. Odaberimo n \in \mathbb{N} tako da je F_{n}\leq N\lt F_{n+1}. Ako je N=F_{n}, tada je tvrdnja točna. Pretpostavimo da je N\gt F_{n}. Očito je N-F_{n}\lt N, pa na broj N-F_{n} možemo primijeniti pretpostavku indukcije te dobivamo N-F_{n}=F_{i_{1}}+\ldots+F_{i_{r}}. Odatle je N=F_{n}+(N-F_{n})=F_{n}+F_{i_{1}}+\ldots+F_{i_{r}} te još treba provjeriti da je i_{1}\leq n-2.
Ova tvrdnja slijedi direktno iz F_{i_{1}}\leq N-F_{n}\lt F_{n+1}-F_{n}=F_{n-1}.
\ \blacksquare

Edouard Zeckendorf, belgijski zaljubljenik u matematiku, izveo je svoj teorem 1939. Otprilike 20 godina poslije, David E. Daykin pokazao je u vrlo netrivijalnom radu [2] da je Fibonaccijev niz jedini koji zadovoljava prethodni teorem, odnosno da je Zeckendorfovim teoremom dano definirajuće svojstvo Fibonaccijeva niza. Prikaz prirodnog broja kojim smo se koristili u Zeckendorfovu teoremu nazivamo kanonski prikaz. Idući rezultat pokazuje kako kanonski prikaz prirodnog broja u Fibonaccijevu brojevnom sustavu doista ima traženo svojstvo.

Teorem 3. (Lekkerkerker)Kanonski prikaz je jedinstven.

Dokaz. Dokaz se ponovno provodi matematičkom indukcijom. Kao i u prethodnom teoremu, neka je N\geq 2 te pretpostavimo da svi brojevi manji od N imaju jedinstven prikaz. Dokažimo sad korak indukcije. Odaberimo n \in \mathbb{N} tako da je F_{n}\leq N\lt F_{n+1}. Dokazat ćemo da se u kanonskom prikazu broja N mora pojaviti broj F_{n}.

Kada se F_{n} ne bi pojavio kanonskom prikazu, imali bismo F_{i_{1}}\leq F_{n-1}, F_{i_{2}}\leq F_{n-3},\ldots Ako je n paran, zapišimo ga u obliku n=2i, te dobivamo N\leq F_{2i-1}+F_{2i-3}+\ldots+F_{3}=F_{2i}-F_{2}=F_{n}-1. Slično, ako je n neparan, možemo ga zapisati u obliku n=2i+1, te dobivamo
N\leq F_{2i}+F_{2i-2}+\ldots+F_{2}=F_{2i+1}-F_{1}=F_{n}-1.
U oba slučaja dobili smo kontradikciju, pa slijedi da F_{n} mora biti dio kanonskog prikaza prirodnog broja N.

Dakle, broj N prikazali smo kao N=F_{n}+m. Zašto nam pojavljivanje broja F_{n} garantira jedinstvenost prikaza? Pretpostavimo da postoje dva različita prikaza broja N. Tada bi postojala i dva različita prikaza od m, što je u kontradikciji s pretpostavkom indukcije, jer je m\lt N.
\ \blacksquare

Dakle, broj 8 iz našeg primjera na jedinstven način u Fibonaccijevu sustavu prikazujemo kao
8=F_{6}=1F_{6}+0F_{5}+0F_{4}+0F_{3}+0F_{2}=1000_{Fib}.

Algoritam
Iz prethodnih dvaju teorema proizlazi jednostavan algoritam za pronalaženje kanonskog prikaza broja prirodnog broja N:
i_{1}=\max\lbrace i\in \mathbb{N}: F_{i}\leq N\rbrace,
i_{2}=\max\lbrace i\in \mathbb{N}: F_{i}\leq N-F_{i_{1}}\rbrace,
i_{3}=\max\lbrace i\in \mathbb{N}: F_{i}\leq N-F_{i_{1}}-F_{i_{2}}\rbrace,
\vdots

Zadatak 4.Koristeći se gornjim algoritamom prikažite prirodne brojeve 16, 33 i 57 u kanonskom prikazu Fibonaccijeva sustava.



3Fibonaccijevi kodovi

Fibonaccijev brojevni sustav od velike je važnosti za kriptografiju jer prirodne brojeve prikazane u Fibonaccijevu sustavu možemo na jednostavan način pretvoriti u kodove. Fibonaccijevi kodovi atraktivniji su u odnosu na ostale univerzalne kodove, jer omogućuju lako određivanje polaznih podataka i jednostavnu, zahvalnu manipulaciju. Zbog tog zanimljivog svojstva, Fibonaccijevi kodovi često nalaze svoju primjenu u programiranju i analizi tržišta kapitala.

U binarnom sustavu svaki niz znamenki 0 i 1 predstavlja neki broj. Pogreška bilo koje vrste, poput nedostatka neke znamenke, opet daje valjani prikaz nekog drugog broja, stoga lako može proći neopaženo. Fibonaccijev sustav pretvara brojeve u nizove znamenki nula i jedinica, u kojem se nikada dvije jednice ne mogu pojaviti zajedno u slijedu. Kada je god 0 koja slijedi ili prethodi 1, slučajno zamijenjena s 1, takva se pogreška lako uočava. Ovo svojstvo Fibonaccijeva sustava daje Fibonaccijevu kodu veliku prednost u odnosu na druge postojeće kodove. Oštećeni niz podataka ne postaje beskoristan, nego se tijekom procesa dekodiranja gube najviše tri znamenke.

Pogledajmo kako na jednostavan način možemo dobiti Fibonaccijeve kodove:

Prikažimo broj 18 u Fibonaccijevoj bazi:
\begin{align*} 18&=13+5=F_{7}+F_{5}\\ &=1 F_{7}+0 F_{6}+1 F_{5}+0F_{4}+0F_{3}+0F_{2}=101000_{Fib}. \end{align*}
Fibonaccijev kod za prirodan broj N definira se kao Fib(N)=a_{0}a_{1}a_{2}\ldots {a_{n-1}} gdje su a_{0},a_{1},\ldots,a_{n-1} znamenke u prikazu prirodnog broja N=a_{n-1}F_{n+1}+\ldots+a_{2}F_{4}+a_{1}F_{3}+a_{0}F_{2} u Fibonaccijevoj bazi. Fibonaccijev kod je obratan od uobičajenog zapisa brojeva u bazi, u kojem je krajnja lijeva znamenka ona koja u prikazu broja stoji uz najveću potenciju baze. U našem slučaju, uz najveći Fibonaccijev broj. Dakle, ako je 101000_{Fib} prikaz broja 18 u Fibonaccijevoj bazi, tada je Fibonaccijev kod tog broja Fib(18)=000101.
Na isti način prikažimo brojeve 33 i 6:
\begin{align*} 33&=21+8+3+1=1F_{8}+0F_{7} +1F_{6}+0 F_{5}+1 F_{4}+0 F_{3}+1F_{2}\\ &=1010101_{Fib}\\ 6&=5+1=1 F_{5}+0 F_{4}+0F_{3}+1 F_{2}=1001_{Fib} \end{align*}
Dobivamo Fib(33)=1010101 i Fib(6)=1001.

Kada bismo dane brojeve zapisali u binarnoj bazi, dobili bismo također niz nula i jedinica koje predstavljaju binarnu inačicu broja. Pogledajmo kako tada zapis glasi:

33= {10001}_{2}
18=01001_{2}
6=011_{2}.

Napravimo li redom konkatenaciju brojeva 33, 18 i 6 zapisanih u binarnom sustavu (tj. zapišemo li odgovarajuće binarne prikaze jednog za drugim), dobivamo niz nula i jedinica 1000101001011. Budući da smo unaprijed zadali brojeve, znamo od kojih je brojeva ovaj niz sastavljen. Međutim, ako bismo pred sobom imali isti niz nula i jedinica 1000101001011 bez prethodnog saznanja od kojih brojeva je on sastavljen, ne bismo ga znali dešifrirati, jer ne bismo znali gdje jedan broj počinje ili završava.

Na isti problem naišli bismo kada bismo napravili konkatenaciju Fibonaccijevih kodova za prirodne brojeve 33, 18 i 6, odnosno Fib(33)Fib(18)Fib(6). Dobili bismo niz nula i jedinica 10101010001011001. Međutim, kod brojeva u Fibonaccijevu brojevnom sustavu taj problem možemo lako riješiti. U zapisu svakog koda, iza zadnje znamenke stavimo dodatnu jedinicu:

Fib(33)=1010101\quad 1
Fib(18)=000101\quad 1
Fib(6)=1001 \quad 1

Sada lako možemo odrediti gdje neki broj počinje, a drugi završava. Kad god naiđemo na dvije susjedne jedinice, znamo da smo došli na kraj niza koji prikazuje određeni broj. Moramo voditi računa o tome da imamo jednu jedinicu viška koja nam služi isključivo za odvajanje i ne koristi se pri pretvorbi u polazni broj. Zeckendorfov teorem osigurava nam nepostojanje susjednih jedinica u zapisu prirodnog broja u Fibonaccijevoj bazi te je ovo dodavanje jedinice moguće.
Napravimo sada konkatenaciju brojeva u Fibonaccijevoj bazi čijem smo zapisu dodali jedinicu
Fib(33)Fib(18)Fib(6)=10101011000101110011.
Jednostavnim rastavom možemo pronaći brojeve koji izgrađuju dani niz nula i jedinica
\overbrace{101010\underline{1}}^{33}\underline{1}\overbrace{00010\underline{1}}^{18}\underline{1}\overbrace{100\underline{1}}^{6}\underline{1}


Zadatak 5.Odredite prirodne brojeve čiji se Fibonaccijev kod nalazi u nizu 1001010011100011101011.



4Proširenja Fibonaccijeva sustava

Fibonaccijev brojevni sustav može se na jednostavan način proširiti do drugih brojevnih sustava, u kojima prirodne brojeve prikazujemo kao sume takozvanih proširenih Fibonaccijevih brojeva. Neki od predstavnika tih sustava su tribonaccijev brojevni sustav, zatim brojevni sustav koji je definirao S. T. Klein [5] te direktna generalizacija Fibonacccijeva sustava, koju nazivamo m-bonaccijev brojevni sustav. Ovi brojevni sustavi imaju važnu ulogu u teorijskom računarstvu, gdje se zbog mnogobrojnih zanimljivih svojstava koriste za konačne automate. Mi nećemo proučavati svojstva tih sustava, već ćemo ukratko dati opis prikaza priro- dnih brojeva u nekima od tih sustava.

4.1Tribonaccijev brojevni sustav

Proširivanjem Fibonaccijevih brojeva dobivamo tribonaccijeve brojeve koji su definirani rekurzijom
F_{i}=F_{i-1}+F_{i-2}+F_{i-3}
uz uvjet F_{3}=2, F_{2}=1, F_{1}=1. Dok se svaki sljedeći Fibonaccijev broj dobiva zbrajanjem prethodnih dvaju, svaki tribonaccijev broj dobivamo zbrajanjem prethodnih triju, pa su
1, 1, 2, 4, 7, 13, 24, 44, 81, 149 \ldots
neki od prvih članova tribonaccijeva niza.
Na prirodan način možemo proširiti Fibonaccijev brojevni sustav do tribonaccijeva brojevnog sustava. U ovom sustavu prirodan broj N može se prikazati kao
N=a_{n-1}F_{n+1}+\ldots+a_{2}F_{4}+a_{1}F_{3}+a_{0}F_{2},
gdje je
F_{i}=F_{i-1}+F_{i-2}+F_{i-3},\quad F_{4}=2^{2}, F_{3}=2^{1}, F_{2}=2^{0}.
U tribonaccijevu sustavu prirodne brojeve također možemo prikazati na više načina. A. S. Fraenkel pokazao je 1985. [4] kako će, ako u prikazu uklonimo grupe u kojima se pojavljuju tri ili više uzastopnih jedinica, prikazi brojeva u tribonaccijevu sustavu biti jedinstveni.
Pogledamo li odgovarajući zapis broja 7, imamo dvije mogućnosti:
(1)
7=F_{5}=1F_{5}+0 F_{4} +0 F_{3}+0 F_{2}
i
(2)
7=4+2+1=0 F_{5}+1F_{4}+1F_{3}+1F_{2}.
Odbacujemo onaj zapis u kojem se pojavljuje tri ili više jedinica, odnosno (2). Dobivamo prikaz 7=1000_{Trib}.

Zadatak 6.Prirodne brojeve 4, 8 i 14 zapišite u tribonaccijevu brojevnom sustavu.

4.2Brojevni sustav srodan Fibonaccijevom

Drugo proširenje Fibonaccijeva sustava je brojevni sustav koji je definirao S. T. Klein, u kojem prirodne brojeve prikazujemo u obliku
N=a_{n-1}F_{n+1}+\ldots+a_{2}F_{4}+a_{1}F_{3}+a_{0}F_{2}
gdje je
F_{i}=F_{i-1}+F_{i-m},\,\, \text{za}\,\, i\gt m+1
F_{i}=i-1,\,\, \text{za}\,\, 1\leq i\leq m+1,\,\, \text{uz uvjet}\, \,m\geq 2.
Kao i prethodni sustavi, ovaj sustav u sebi također sadržava višestruke prikaze. Jedinstvenost u prikazu prirodnog broja kao n-torke koja se sastoji od nula i jedinica možemo postići uz uvjet da se između svakog para jedinica nalazi najmanje m-1 nula [5].

Za m=2, ovaj sustav odgovara Fibonaccijevu sustavu. Promotrimo slučaj m=3. Baza je tada definirana s F_{i}=F_{i-1}+F_{i-3} te F_{4}=3, F_{3}=2 i F_{2}=1. Primjerice, prvih pet prirodnih brojeva u novoj bazi možemo prikazati kao N=a_{3}F_{5}+a_{2}F_{4}+a_{1}F_{3}+a_{0}F_{2}, tj. N=a_{3}4+a_{2}3+a_{1}2+a_{0}. Zbog gore navedenog uvjeta, odbacujemo one prikaze u kojima se između jedinica pojavljuje manje od m-1 nula. U sljedećoj tablici označili smo prikaze koje odbacujemo jer ne zadovoljavaju traženo svojstvo.



a_{3} a_{2} a_{1} a_{0} N
 
0 0 0 1 1
0 0 1 0 2
0 0 1 1 3 \leftarrow odbacujemo
0 1 0 0 3
0 1 0 1 4 \leftarrow odbacujemo
1 0 0 0 4
0 1 1 0 5 \leftarrow odbacujemo
1 0 0 1 5

4.3m-naccijev brojevni sustav

Pogledajmo ukratko i treće proširenje Fibonaccijeva brojevnog sustava, poznato pod nazivom m-naccijev brojevni sustav. Prirodan broj u ovom sustavu možemo prikazati kao
N=a_{n-1}F_{n+1}+\ldots+a_{2}F_{4}+a_{1}F_{3}+a_{0}F_{2},

gdje je baza dana s
F_{i}=mF_{i-1}-F_{i-2},\,\,\text{za}\,\, i\gt 3\,\, \text{i}\,\, F_{3}=m, F_{2}=1,
a znamenke a_{i} s 0, 1, 2, \ldots, m-1 za m\geq 3. Prethodna tri sustava imala su samo dvije znamenke, 0 i 1, dok m–naccijev sustav ima onoliko znamenki koliki m odaberemo, uz uvjet da je m barem 3. Odaberemo li m=3, dobivamo m–naccijev brojevni sustav s tri znamenke 0,1,2. Broj 5 u takvom sustavu možemo prikazati u obliku   5=3+2=F_{3}+2F_{2} tj. 5=12_{m_{3}}.

Budući da i u ovom brojevnom sustavu postoji više mogućnosti za prikaz prirodnih brojeva, jedinstvenost možemo postići uz neke restrikcije. U radu [5] je S. T. Klein pokazao kako jedinstvenost prikaza brojeva u m-naccijevom sustavu dobivamo ako se između svakih dvaju pojavljivanja broja m-1 nalazi najmanje jedan i takav da i\in\lbrace 0,1,\ldots,m-3\rbrace .

Zapišemo li u m-naccijevu sustavu s tri znamenke broj 8, dobit ćemo dva prikaza
(3)
8=2+6=0F_{4}+2F_{3}+2F_{2}
i
(4)
8=F_{4}+0F_{3}+0F_{2}.
Prema gornjem uvjetu, odbacujemo prikaz (3) i prihvaćamo (4) kao jedinstveni prikaz broja 8= 100_{m_{3}} u ovoj bazi.

Zadatak 7. Prirodne brojeve 9, 11 i 17 zapišite u m-naccijevu brojevnom sustavu, gdje je m=3.


Bibliografija
[1] J. T. Butler \& T. Sasao, Redundant Multiple-Valued Number Systems, The Proc. of the Japan Research Group on Multiple-Valued Logic, 20, 1997, pp. 141–148.
[2] D. E. Daykin, Representation of natural numbers as sums of generalised Fibonacci numbers, J. London Math. Soc., 35 (1960), pp. 143–160.
[3] A. Dujella, Fibonaccijevi brojevi, HMD, Zagreb, 2000.
[4] A. S. Fraenkel, Systems of numeration, Amer. Math. Monthly, 92 (1985), pp. 105–114.
[5] S. T. Klein, Combinatorial representation of generalized Fibonacci numbers, Fibonacci Quart. 29 (1991), pp. 124–131. 2008, pp. 534–550.
[6] D. De Luca Picione, F. Battisti, M. Carli, J. Astola \& K. Egiazarian, A Fibonacci LSB Data Hiding Techique, 14th European Signal Processing Conference (EUSIPCO 2006), Florence, Italy, 2006.
  • Share this