Question

Prove by induction, that the n'th Fibonacci number can be found by the formula фт — фт Fr _ n V5 1-5 whereD

Answer 1

The Fibonacci sequence $F_{n}$ is given by ,

and

Now we will use induction on n to prove that ,

В1 Ф" — Ф" Fn У5

Where , $\Phi = \frac{1+\sqrt5}{2} , \phi = \frac{1-\sqrt5}{2}$

Base step : For n =1

$\frac{\Phi^{1} - \phi^{1}}{\sqrt5}$

$=\frac{\frac{1 +\sqrt5}{2}- \frac{1- \sqrt5}{2}}{\sqrt5}$

$=\frac{\sqrt5}{\sqrt5}$

So the formula is true for n =1 .

Induction hypothesis : Suppose the formupa is true for all $n \leq m$ i.e., $F_{m} = \frac{\Phi^m - \phi^{m}}{\sqrt5} , F_{m-1} = \frac{\Phi^{m-1}-\phi^{m-1}}{\sqrt5}$

Induction steps : For n = m+1

$F_{m+1}$

$=\frac{\Phi^m - \phi^{m}}{\sqrt5} +\frac{\Phi^{m-1}-\phi^{m-1}}{\sqrt5}$

$=\frac{1}{\sqrt5}[ \Phi^{m-1} (\Phi +1) - \phi^{m-1}(\phi +1)]$

$=\frac{1}{\sqrt5}[ \Phi^{m-1} (\frac{1+\sqrt5}{2}+1) -\phi^{m-1}(\frac{1-\sqrt5}{2}+1)]$

$=\frac{1}{\sqrt5}[ \Phi^{m-1} (\frac{3+\sqrt5}{2}) -\phi^{m-1}(\frac{3-\sqrt5}{2})]$

:(Фт-1ф2 — фт-12? 5

$=\frac{1}{\sqrt5}[ \Phi^{m+1} - \phi^{m+1}]$

So the formula is true for n=m+1 if we assume it is true for $n \leq m$ also it id true for n=1 . Hence by induction on n the formula is true for all natural number n . Hence ,

В1 Ф" — Ф" Fn У5

.

.

.

.

If you any doubt or need more clarication at any step please comment.