Prove $\phi^n = \phi F_n + \text{(another Fibonacci number)}$ using mathematical induction.

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.

Solution 1:

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$.

Solution 2:

Hint:

Assuming the conjecture true, compute $\phi^n-\phi F_n$ for increasing $n$:

$$\phi^1-\phi F_1=\phi-\phi=0,\\ \phi^2-\phi F_2=\phi^2-\phi=1,\\ \phi^3-\phi F_3=\phi^3-2\phi=\phi^3-\phi^2+\phi^2-2\phi=\phi^2-\phi=1,\\ \phi^4-\phi F_4=\phi^4-3\phi=\phi^4-\phi^3+\phi^3-\phi^2+\phi^2-3\phi=2\phi^2-2\phi=2,\\ \cdots $$

and the pattern seems to be

$$\phi^n=\phi F_n+F_{n-1}.$$

Then sum the equality for $n$ and $n+1$, giving

$$\phi^{n+1}+\phi^{n}=\phi^{n+2}=\phi(F_{n+1}+F_n)+(F_n+F_{n-1}).$$

You can conclude now.