Binetova formula

Binetova formula je izraz za računanje $n$-tog Fibonaccijevog broja kojeg označavamo s $F_{n}$, počevši od $F_{1}=1.$

Formula je nazvana po francuskom matematičaru Jacquesu Philippeu Binetu, iako je poznato da je za nju, stoljeće prije njega, znao Abraham de Moivre.

Ako s $\alpha ,\beta$ označimo $\alpha ={\frac {1+{\sqrt {5}}}{2}},\beta ={\frac {1-{\sqrt {5}}}{2}},$ tada formula glasi $F_{n}={\frac {1}{\sqrt {5}}}({\alpha }^{n}-{\beta }^{n}).$

Uočimo da su $\alpha ,\beta$ oba rješenja zlatne jednadžbe $x^{2}=x+1.$ Dokaz Binetove formule će zbog toga biti skriven upravo u toj jednadžbi.

Dokaz

Binetovu formulu ćemo dokazati metodom matematičke indukcije.

Uočimo što ćemo dobiti uzastopnim množenjem zlatne jednadžbe s $x$: $x^{2}=x+1$

$x^{3}=2x+1,$

$x^{4}=3x+2,$

$x^{5}=5x+3,...$

Uočavamo da su koeficijenti uz $x$ i $1$ uzastopni Fibonaccijevi brojevi pa naslućujemo da vrijedi $x^{n}=F_{n}x+F_{n-1}$ uz dodatak $F_{0}=0.$ Gore smo pokazali da tvrdnja vrijedi za $n\leq 5.$

Pretpostavimo sada da tvrdnja vrijedi za neki $k\in \mathbb {N} ,$ tj. da je $x^{k}=F_{k}x+F_{k-1}.$

Iz pretpostavke slijedi $x^{k+1}=x\cdot x^{k}=x(F_{k}x+F_{k-1})$ što daje $F_{k}x^{2}+F_{k-1}x.$

Sada iz temeljne jednakosti $x^{2}=x+1$ zamjenom slijedi $x^{k+1}=F_{k}(x+1)+F_{k-1}x,$ iz čega je $x^{k+1}=F_{k}x+F_{k}+F_{k-1}x,$ odnosno $x^{k+1}=F_{k+1}x+F_{k},$ što je i trebalo dokazati.

Znamo da su $\alpha ,\beta$ rješenja jednadžbe $x^{2}=x+1,$ pa također zadovoljavaju i jednakosti $x^{n}=F_{n}x+F_{n-1}.$ Zato možemo pisati $\alpha ^{n}=F_{n}\alpha +F_{n-1},\beta ^{n}=F_{n}\beta +F_{n-1}.$

Oduzimanjem ove dvije jednadžbe slijedi $\alpha ^{n}-\beta ^{n}=F_{n}(\alpha -\beta ),$ a kako je $\alpha -\beta ={\frac {1+{\sqrt {5}}}{2}}-{\frac {1-{\sqrt {5}}}{2}}={\sqrt {5}},$ konačno dobivamo $F_{n}={\frac {1}{\sqrt {5}}}({\alpha }^{n}-{\beta }^{n}).$