Celem tego wpisu jest wyprowadzenie wzoru Bineta na n-tą liczbę ciągu Fibonacciego.
Czym jest ciąg Fibonacciego \((F_n)\) chyba wiemy. A jeżeli nie, to można się tego dowiedzieć np. tutaj.
\[F_n=\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}.\]
Na początek zauważmy, że pierwiastkami równania \[\begin{equation}x^2=x+1\end{equation}\]
są liczby \(\varphi\) oraz \(\tilde{\phi}=\dfrac{1-\sqrt{5}}{2}\).
Najpierw pokażemy, że dla \(x\in\{\varphi, \tilde{\phi}\}\) oraz \(n>1\) prawdziwa jest równość
\[x^n=F_nx+F_{n-1}.\]
Istotnie, dla \(n=2\) jest oczywiście spełniona, gdyż jest to po prostu równanie \(x^2=x+1\). Teraz załóżmy, że jest prawdziwa dla pewnego \(k\geq 1\), tj.
\[x^k=F_kx+F_{k-1}. \]
Wówczas
\[x^{k+1}=x^k\cdot x=F_kx^2+F_{k-1}x=F_k(x+1)+F_{k-1}x=F_{k+1}x+ F_k.\]
Na mocy zasady indukcji zupełnej, otrzymujemy że jest to prawda dla każdego \(n>1\). Ponieważ \(\varphi\) oraz \(\tilde{\phi}\) są pierwiastkami równania \[x^2=x+1,\] to są również pierwiastkami równania
\[x^n=F_nx+F_{n-1}\]
gdyż \(F_nx+F_{n-1}=x^{n-2}\cdot (x+1)\). Mamy więc
\[\varphi^n=F_n\varphi+F_{n-1} \textrm{ oraz } \tilde{\phi}^n=F_n\tilde{\phi}+F_{n-1}.\]
Odejmując stronami, otrzymujemy
\[\varphi^n-\tilde{\phi}^n=F_n\cdot (\varphi-\tilde{\phi}).\]
Czyli
\[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n=F_n\cdot\left(\dfrac{1+\sqrt{5}}{2}-\dfrac{1-\sqrt{5}}{2}\right)=F_n\cdot\sqrt{5}.\]
Dzieląc przez \(\sqrt{5}\) otrzymujemy wzór Bineta.