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\le 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).$