Binet Formula for Fibonacci Number

Posted on July 9, 2017 by Sumant Sumant

While there are many ways to derive the recursive formula of Fibonacci Sequence. The formula to find the nth term of a Fibonacci sequence is a beautiful formula. We are not going to derive here but prove the formula using mathematical Induction.
We use Strong Induction to prove the Binet Formula because we will be invoking the recursive formula of fibonacci sequence to prove the $n+1$ case.

The Binet formula is \frac{\phi^n-\alpha^n}{\sqrt{5}}
\phi = \frac{1+\sqrt{5}}{2} and \alpha = \frac{1-\sqrt{5}}{2}.
Verify the base cases:
for n = 1 we have
\frac{\phi-\alpha}{\sqrt{5}}= 1
Similarly
for n = 2 we have
\frac{\phi^2-\alpha^2}{\sqrt{5}}
\Rightarrow \frac{(\phi-1)-(\alpha-1)}{\sqrt{5}}
\Rightarrow \frac{\phi-\alpha}{\sqrt{5}}
which we know from first statement is true
To prove the last step we realize that F_{n+1}=F_n+F_{n-1}
Thus we have
\Rightarrow F_{n+1}= \frac{\phi^n-\alpha^n}{\sqrt{5}}+\frac{\phi^{n-1}-\alpha^{n-1}}{\sqrt{5}}
\Rightarrow F_{n+1}= \frac{\phi^n+\phi^{n-1}-\alpha^n-\alpha^{n-1}}{\sqrt{5}}
\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi+1)-\alpha^{n-1}(\alpha+1)}{\sqrt{5}}
\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi^2)-\alpha^{n-1}(\alpha^2)}{\sqrt{5}}
\Rightarrow F_{n+1}= \frac{\phi^{n+1}-\alpha^{n+1}}{\sqrt{5}}
Hence Proved

About Sumant Sumant

I love Math and I am always looking forward to collaborate with fellow learners. If you need help learning math then please do contact me.
This entry was posted in Mathematical Induction, Number Theory, Proof and tagged , , . Bookmark the permalink.

Leave a comment