Fibonaccijev broj

U matematici, Fibonaccijevi brojevi oblikuju niz definisan sljedećom rekurzivnom relacijom:

${\displaystyle F(n):={\begin{cases}0&{\mbox{ako je }}n=0;\\1&{\mbox{ako je }}n=1;\\F(n-1)+F(n-2)&{\mbox{ako je }}n>1.\\\end{cases}}}$

Popločanje s kvadratima čije su stranice po dužini sukcesivni Fibonaccijevi brojevi

To jest, nakon dvije početne vrijedosti, svaki sljedeći broj je zbroj dvaju prethodnika. Prvi Fibonaccijevi brojevi (niz A000045 u OEIS) , također označeni kao F_n, za n = 0, 1, … , su:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514299, 832040...

Ponekad se za ovaj niz smatra da počinje na F₁ = 1, ali uobičajenije je uključiti F₀ = 0.

Fibonaccijevi brojevi su imenovani po Leonardu od Pise, poznatom kao Fibonacci, iako su ranije opisani u Indiji.^[1][2]

Ako znamo Fibonaccijeve brojeve ${\displaystyle F_{m}}$ i ${\displaystyle F_{n}}$ onda možemo naći broj ${\displaystyle F_{m+n}}$ po formuli

${\displaystyle F_{m+n}=F_{(m-1)}F_{n}+F_{m}F_{n+1}}$

Također imamo

${\displaystyle F_{2n}=F_{n}(F_{n+1}+F_{n-1})}$

${\displaystyle F_{3n}=F_{n+1}^{3}+F_{n}^{3}+F_{n-1}^{3}}$

Uopšteno

${\displaystyle F_{mn}=\textstyle \sum _{k=1}^{m}{{\binom {m}{k}}(F_{n}^{k}(F_{n-1}^{m-k}}}$

Binetova formula

Binetova formula je eksplicitno izražavanje vrijednosti ${\displaystyle F_{n}}$ kao funkcije od ${\displaystyle n}$

${\displaystyle F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\varphi -(-\varphi )^{-1}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}},}$

gdje je ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ zlatni presjek. U tom slučaju ${\displaystyle \varphi }$ и ${\displaystyle (-\varphi )^{-1}=1-\varphi }$ su rješenja jednačine ${\displaystyle x^{2}-x-1=0}$.

Iz Binetove formule za sve ${\displaystyle n\geqslant 0}$, slijedi da je ${\displaystyle F_{n}}$ za ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$ najbliže cijelom broju tj. ${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil }$

Za ${\displaystyle n\to \infty }$ je ${\displaystyle F_{n}\sim {\frac {\varphi ^{n}}{\sqrt {5}}}}$.

Formula se može analitiči prikazati na sljedeći način

${\displaystyle F_{z}={\frac {1}{\sqrt {5}}}\left(\varphi ^{z}-{\frac {\cos {\pi z}}{\varphi ^{z}}}\right).}$

pri tome ${\displaystyle F_{z+2}=F_{z+1}+F_{z}}$ vrijedi za svaki kompleksni broj

Odnos prema zlatnom odnosu

U teoriji brojeva veliku ulogu igra broj ${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}}$ koji je korjen jednačine ${\displaystyle x^{2}-x-1=0}$ i

${\displaystyle x^{n}-x^{n-1}+x^{n-2}=0}$

Iz Binetove formule

${\displaystyle {\frac {1}{\sqrt {5}}}(\phi ^{n}-(-\phi )^{-n})={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}}$

Gdje je

${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\cdots }$

${\displaystyle \varphi ^{-1}={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\cdots }$

Dalje imamo

${\displaystyle \varphi ^{n}=\varphi ^{n-1}+\varphi ^{n-2}}$

i

${\displaystyle (\varphi ^{-1})^{n}=(\varphi ^{-1})^{n-1}+(\varphi ^{-1})^{n-2}}$

Za sve vrijednosti a , b definišimo niz

${\displaystyle U_{n}=a\varphi ^{n}+b(\varphi ^{-1})^{n}}$

Zadovoljena je i relaciija

${\displaystyle U_{n}=a\varphi ^{n-1}+b(\varphi ^{-1})^{n-1}+a\varphi ^{n-2}+b(\varphi ^{-1})^{n-2}=U_{n-1}+U_{n-2}}$

Neka su ${\displaystyle a}$ i ${\displaystyle b}$ izabrani tako da je ${\displaystyle U_{0}=0}$ i ${\displaystyle U_{1}=1}$onda dobijeni niz mora biti Fibonaccijev niz.

Brojevi ${\displaystyle a}$ i ${\displaystyle b}$ zafovoljavaju relaciju

${\displaystyle a+b=0}$

${\displaystyle a\varphi ^{n}+b(\varphi ^{-1})^{n}=1}$

Odnosno imamo

${\displaystyle a={\frac {1}{\varphi -\varphi ^{-1}}}={\frac {1}{\sqrt {5}}},\,b=-a}$

Uzimajući ${\displaystyle U_{0}}$ i ${\displaystyle U_{1}}$ kao početne varijable imamo

${\displaystyle U_{n}=a\varphi ^{n}+b(\varphi ^{-1})^{n}=1}$

Odnosno

${\displaystyle a={\frac {U_{1}-U_{0}\varphi ^{-1}}{\sqrt {5}}}}$

${\displaystyle b={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}}$.

Posmatrajmo sada

${\displaystyle \left|{\frac {(\varphi ^{-1})^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$

Za ${\displaystyle n\geq 0}$, broj ${\displaystyle F_{n}}$ najbliži cio broj je ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$, koji se može dobiti iz funkcije

${\displaystyle F_{n}=\left[{\frac {\varphi ^{n}}{\sqrt {5}}}\right],\ n\geq 0,}$

ili

${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor ,\ n\geq 0.}$

Slično ako je F>0 Fiboniccijev broj onda možemo odrediti njegov indeks unutar niza.

${\displaystyle n(F)={\bigg \lfloor }\log _{\varphi }\left(F\cdot {\sqrt {5}}+{\frac {1}{2}}\right){\bigg \rfloor },}$

gdje se ${\displaystyle \log _{\varphi }(x)}$ može izračunati korištenjem logaritma druge baze

Primjer

${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}$

Osobine

Najveći zajednički djelitelj dva Fibonaccijeva broja je broj čiji je indeks jednak najvećem zajedničkom delitelju njihovih indeksa

Posljedice

${\displaystyle F_{m}}$ je djeljiv sa ${\displaystyle F_{n}}$ ako i samo ako je ${\displaystyle m}$ djeljivo sa ${\displaystyle n}$( bez ${\displaystyle n=2}$)

• ${\displaystyle F_{m}}$ je djeljivo sa ${\displaystyle F_{3}=2}$ samo ako je ${\displaystyle m=3k}$
• ${\displaystyle F_{m}}$ je djeljivo sa ${\displaystyle F_{4}=3}$ samo ako je ${\displaystyle m=4k}$
• ${\displaystyle F_{m}}$ je djeljivo sa ${\displaystyle F_{5}=5}$ samo ako je ${\displaystyle m=5k}$

${\displaystyle F_{m}}$ je prost ako je ${\displaystyle m}$ prost broj sa isključenjem ${\displaystyle m=4}$

${\displaystyle F_{13}=233}$

Obratno ne važi tj ako je ${\displaystyle m}$ prost broj ${\displaystyle F_{m}}$ ne mora biti prost

${\displaystyle F{19}=4181=37*113}$

Njegov polinom ${\displaystyle x^{2}-x-1}$ ima korjene ${\displaystyle \varphi }$ i ${\displaystyle -\varphi ^{-1}}$

${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$

1964 godine Cochn je dokazao da su u nizu Fibonaccijevih brojeva jedini kvadrati brojevi sa indeksom 0,,1,2,12 ${\displaystyle F_{0}=0^{2}=0}$, ${\displaystyle F_{1}=1^{2}=1}$, ${\displaystyle F_{2}=1^{2}=1}$, ${\displaystyle F_{12}=12^{2}=144}$

Generirajuća funkcija niza fibonaccijevih brojeva je ${\displaystyle x+x^{2}+2x^{3}+3x^{4}+5x^{5}+\dots =\sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}}$

Fibonnaccijev niz brojeva

Prvih 21 Fibonaccijevih brojeva ${\displaystyle F_{n}}$ za ${\displaystyle n=0,1,2,3,....20}$^[3]

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19	F20
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765

Ovaj niz brojeva može se proširiti i na negativne brojeve.

${\displaystyle F_{n-2}=F_{n}-F_{n-1},}$

${\displaystyle F_{-n}=(-1)^{n+1}F_{n}.}$

Niz brojeva ${\displaystyle F_{n}}$ za ${\displaystyle n=-8,-7,....0,1,2,....8}$^[4]

F−8

F−7

F−6

F−5

F−4

F−3

F−2

F−1

F0

F1

F2

F3

F4

F5

F6

F7

F8

−21

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8

13

21

Identiteti

• ${\displaystyle F_{1}+F_{2}+F_{3}+\dots +F_{n}=F_{n+2}-1}$
• ${\displaystyle F_{1}+F_{3}+F_{5}+\dots +F_{2n-1}=F_{2n}}$
• ${\displaystyle F_{2}+F_{4}+F_{6}+\dots +F_{2n}=F_{2n+1}-1}$
• ${\displaystyle F_{n+1}F_{n+2}^{}-F_{n}F_{n+3}=(-1)^{n}}$
• ${\displaystyle F_{1}^{2}+F_{2}^{2}+F_{3}^{2}+\dots +F_{n}^{2}=F_{n}F_{n+1}}$ (см. рис.)
• ${\displaystyle F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}}$
• ${\displaystyle F_{2n}=F_{n+1}^{2}-F_{n-1}^{2}}$
• ${\displaystyle F_{3n}=F_{n+1}^{3}+F_{n}^{3}-F_{n-1}^{3}}$
• ${\displaystyle F_{5n}=25F_{n}^{5}+25(-1)^{n}F_{n}^{3}+5F_{n}}$

Opšte formule

• ${\displaystyle F_{n+m}^{}=F_{n-1}F_{m}+F_{n}F_{m+1}=F_{n+1}F_{m+1}-F_{n-1}F_{m-1}}$
• ${\displaystyle F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_{n}F_{kn+1}}$
• ${\displaystyle F_{n}^{}=F_{l}F_{n-l+1}+F_{l-1}F_{n-l}}$

${\displaystyle F_{n+1}=\det {\begin{pmatrix}1&1&0&\cdots &0\\-1&1&1&\ddots &\vdots \\0&-1&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &1\\0&\cdots &0&-1&1\end{pmatrix}}}$, kao i ${\displaystyle \ F_{n+1}=\det {\begin{pmatrix}1&i&0&\cdots &0\\i&1&i&\ddots &\vdots \\0&i&\ddots &\ddots &0\\\vdots &\ddots &\ddots &\ddots &i\\0&\cdots &0&i&1\end{pmatrix}}}$,

gdje matrice imaju oblik ${\displaystyle n\times n}$, i  je imaginarna jedinica.

• Fibonaccijeve brojeve možemo izraziti preko Chebyshevih polinoma

${\displaystyle F_{n+1}=(-i)^{n}U_{n}\left({\frac {-i}{2}}\right),}$

${\displaystyle F_{2n+2}=U_{n}\left({\frac {3}{2}}\right).}$

Za bilo koji ${\displaystyle n}$

${\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}$

Posljedica

${\displaystyle (-1)^{n}=F_{n+1}F_{n-1}-F_{n}^{2}.}$

Formula za ponovno dobijanje Fibonaccijevih brojeva je

${\displaystyle F_{n+1}={\frac {F_{n}+{\sqrt {5F_{n}^{2}\pm 4}}}{2}}}$

Fibonnacijev niz u prirodi

Fibonaccijev niz se često povezuje i sa brojem fi (phi), ili brojem kojeg mnogi zovu i "Božanskim omjerom". Uzmemo li jedan dio Fibonaccijevog niza, 2, 3, 5, 8, te podijelimo li svaki slijedeći broj s njemu prethodnim, dobit ćemo uvijek broj približan broju 1,618(2/3=1,5; 3/5=1,66; 5/8=1,6). Broj 1,618 jeste broj fi. Odnosi mjera kod biljaka, životinja i ljudi, sa zapanjujućom preciznošću se približava broju fi.

Slijedi nekoliko primjera broja fi i njegove povezanosti sa Fibonaccijem i prirodom:

1. U pčelinjoj zajednici, košnici, uvijek je manji broj mužjaka pčela nego ženki pčela. Kada bi podijelili broj ženki sa brojem mužjaka pčela, uvijek bi dobili broj fi.
2. Nautilus (glavonožac), u svojoj konstrukciji ima spirale. Kada bi izračunali odnos svakog spiralnog promjera prema slijedećem dobili bi broj fi.
3. Sjeme suncokreta raste u suprotnim spiralama. Međusobni odnosi promjera rotacije je broj fi.
4. Izmjerimo li čovječju dužinu od vrha glave do poda, zatim to podijelimo s dužinom od pupka do poda, dobijamo broj fi.

Također pogledajte

• Fibonaccijevi polinomi