Fibonaccijev broj

mini|desno|150px|Popločanje s kvadratima čije su stranice po dužini sukcesivni Fibonaccijevi brojevi
U matematici, **Fibonaccijevi brojevi** oblikuju niz definisan sljedećom rekurzivnom relacijom:
: 
  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}
 
To jest, nakon dvije početne vrijedosti, svaki sljedeći broj je zbroj dvaju prethodnika. Prvi Fibonaccijevi brojevi , također označeni kao *Fn*, za *n*&nbsp;=&nbsp;0,&nbsp;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 = 1, ali uobičajenije je uključiti *F*0 = 0.

Fibonaccijevi brojevi su imenovani po Leonardu od Pise, poznatom kao Fibonacci, iako su ranije opisani u Indiji.

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

F_{m+n}=F_{(m-1)}F_n+F_mF_{n+1}

Također imamo

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

F_{3n}= F_{n+1}^3+ F_n^3+F_{n-1}^3

Uopšteno

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  F_n kao funkcije  od n

: 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 \varphi=\frac{1 + \sqrt{5}}{2}  zlatni presjek. U tom slučaju \varphi и (-\varphi )^{-1}=1-\varphi su rješenja jednačine x^2-x-1=0.

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

Za n\to\infty je F_n\sim \frac{\varphi^n}{\sqrt{5}}.

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

: F_z = \frac{1}{\sqrt{5}} \left( \varphi^z - \frac{\cos{\pi z}}{\varphi^z} \right).

pri tome  F_{z+2} = F_{z+1} + F_z  vrijedi za svaki kompleksni broj

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

x^n-x^{n-1}+x^{n-2}=0

Iz Binetove formule

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

Gdje je
:\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots

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

Dalje imamo

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

i

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

Za sve vrijednosti a , b definišimo niz

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

Zadovoljena je i relaciija

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 a i b izabrani tako da je U_0=0 i U_1=1onda dobijeni niz mora biti Fibonaccijev niz.

Brojevi a i b zafovoljavaju relaciju

a+b=0

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

Odnosno imamo

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

Uzimajući U_0 i U_1 kao početne varijable imamo

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

Odnosno

: a=\frac{U_1-U_0\varphi^{-1}}{\sqrt 5}
: b=\frac{U_0\varphi-U_1}{\sqrt 5}.

Posmatrajmo sada

:\left|\frac{(\varphi^{-1})^{n}}{\sqrt 5}\right| 

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

:F_n=\left[\frac{\varphi^n}{\sqrt 5}\right],\ n \geq 0,

ili

: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.

:n(F) = \bigg\lfloor \log_\varphi \left(F\cdot\sqrt{5} + \frac{1}{2}\right) \bigg\rfloor,

gdje se \log_\varphi(x) može izračunati korištenjem logaritma druge baze

Primjer

\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

F_m je djeljiv sa F_n ako i samo ako je m djeljivo sa n( bez n=2)
*F_m je djeljivo sa F_3=2 samo ako je m=3k
*F_m je djeljivo sa F_4=3 samo ako je m=4k
*F_m je djeljivo sa F_5=5 samo ako je m=5k
F_m je prost ako je m prost broj sa isključenjem m=4
:F_{13} =233

Obratno ne važi tj ako je m prost broj F_m ne mora biti prost
:F{19}=4181=37*113

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

\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
F_{0}=0^{2}=0, F_{1}=1^{2}=1, F_{2}=1^{2}=1, F_{12}=12^{2}=144

**Generirajuća** funkcija niza fibonaccijevih brojeva je  
x + x^2 + 2 x^3 + 3 x^4 + 5 x^5 + \dots = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}

## Fibonnaccijev niz brojeva 
Prvih 21 Fibonaccijevih brojeva F_n za n = 0,1,2,3,....20

Ovaj niz brojeva može se proširiti i na negativne brojeve.
:F_{n-2} = F_n - F_{n-1},

:F_{-n} = (-1)^{n+1} F_n.

Niz brojeva F_n za n=-8,-7,....0,1,2,....8 

## Identiteti 
* F_1+F_2+F_3+\dots+F_n=F_{n+2}-1
* F_1+F_3+F_5+\dots+F_{2n-1}=F_{2n}
* F_2+F_4+F_6+\dots+F_{2n}=F_{2n+1}-1
* F_{n+1}F_{n+2}^{}-F_nF_{n+3}=(-1)^{n}
* F_1^2+F_2^2+F_3^2+\dots+F_{n}^2=F_nF_{n+1} (см. рис.)
* F_n^2+F_{n+1}^2=F_{2n+1}
* F_{2n}=F_{n+1}^2-F_{n-1}^2
* F_{3n}=F_{n+1}^3+F_n^3-F_{n-1}^3
* F_{5n}=25F_{n}^5+25(-1)^{n}F_n^3+5F_{n}

Opšte formule

* 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}
* F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_nF_{kn+1}
* F_n^{}=F_lF_{n-l+1}+F_{l-1}F_{n-l}

:: 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 \ 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 n\times n, *i*  je imaginarna jedinica.

* Fibonaccijeve brojeve možemo izraziti preko Chebyshevih polinoma
: F_{n+1} = (-i)^n U_n\left(\frac{-i}{2}\right),
: F_{2n+2} = U_n\left(\frac{3}{2}\right).

Za bilo koji n

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

Posljedica

(-1)^n = F_{n+1} F_{n-1} - F_n^2.

Formula za ponovno dobijanje Fibonaccijevih brojeva je

::  F_{n+1}=\frac {F_n+\sqrt{5F_n^2\pm4}}{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 sljedeć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:

# 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.
# Nautilus (glavonožac), u svojoj konstrukciji ima spirale. Kada bi izračunali odnos svakog spiralnog promjera prema sljedećem dobili bi broj fi.
# Sjeme suncokreta raste u suprotnim spiralama. Međusobni odnosi promjera rotacije je broj fi.
# 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
## Reference