I need to prove the following equation using mathematical induction and using the phi values if necessary.
$\phi^n = \phi F_n + \text{(another Fibonacci number)}$
In this proof, it is kind of hard for me to prove this with the part "another Fibonacci number".
Thank you in advance.
Help is much appreciated.
Best Answer
It is easy to show $\phi^n = \phi F_n + F_{n-1}$ by induction.
We have $F_1=1,F_0=0$, so for $n=1$ we have to prove that $\phi=\phi+0$, which is true.
Suppose it is true for $n$. Then we have $\phi^{n+1}=\phi^2 F_n+\phi F_{n-1}$. Using $\phi^2=\phi+1$ the lhs becomes $\phi F_n+F_n+\phi F_{n-1}=\phi(F_n+F_{n-1})+F_n=\phi F_{n+1}+F_n$, so the result is true for $n+1$.