Binetova formula

Binetova formula je izraz za računanje [math]\displaystyle{ n }[/math]-tog Fibonaccijevog broja kojeg označavamo s [math]\displaystyle{ F_n }[/math], počevši od [math]\displaystyle{ F_1 = 1. }[/math]

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 [math]\displaystyle{ \alpha, \beta }[/math] označimo [math]\displaystyle{ \alpha = \frac{1 + \sqrt{5}}{2}, \beta = \frac{1 - \sqrt{5}}{2}, }[/math] tada formula glasi [math]\displaystyle{ F_n = \frac{1}{\sqrt{5}}({\alpha}^n - {\beta}^n). }[/math]

Uočimo da su [math]\displaystyle{ \alpha, \beta }[/math] oba rješenja zlatne jednadžbe [math]\displaystyle{ x^2 = x + 1. }[/math] 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 [math]\displaystyle{ x }[/math]: [math]\displaystyle{ x^2 = x + 1 }[/math]

[math]\displaystyle{ x^3 = 2x + 1, }[/math]

[math]\displaystyle{ x^4 = 3x + 2, }[/math]

[math]\displaystyle{ x^5 = 5x + 3, ... }[/math]

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

Pretpostavimo sada da tvrdnja vrijedi za neki [math]\displaystyle{ k \in \mathbb{N}, }[/math] tj. da je [math]\displaystyle{ x^k = F_kx + F_{k - 1}. }[/math]

Iz pretpostavke slijedi [math]\displaystyle{ x^{k + 1} = x \cdot x^k = x(F_kx + F_{k - 1}) }[/math] što daje [math]\displaystyle{ F_kx^2 + F_{k - 1}x. }[/math]

Sada iz temeljne jednakosti [math]\displaystyle{ x^2 = x + 1 }[/math] zamjenom slijedi [math]\displaystyle{ x^{k + 1} = F_k(x + 1) + F_{k - 1}x, }[/math] iz čega je [math]\displaystyle{ x^{k + 1} = F_kx + F_k + F_{k - 1}x, }[/math] odnosno [math]\displaystyle{ x^{k + 1} = F_{k + 1}x + F_k, }[/math] što je i trebalo dokazati.

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

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