I have to prove the following equation by induction for $$x = \phi$$ I am stuck and I don't know how to proceed.
This is the equation
$$
\phi ^n = f_n\phi + f_{n-1}
$$
where $f_n$ is the nth term of the Fibonacci sequence and $f_{n-1}$ is the (n-1)st term.
Best Answer
One of the neat properties of $\phi$ is that $\phi^2=\phi+1$. We will use this fact later. The base step is: $\phi^1=1\times \phi+0$ where $f_1=1$ and $f_0=0$. For the inductive step, assume that $\phi^n=f_n\phi+f_{n-1}.$ Then $$\phi^{n+1}=\phi^n\phi=(f_n\phi+f_{n-1})\phi=f_n\phi^2+f_{n-1}\phi=f_n\phi+f_n+f_{n-1}\phi=(f_n+f_{n-1})\phi+f_n\\=f_{n+1}\phi+f_n.$$