prove by induction Fibonacci sequence: $\forall n \geq 1, F_n \varphi+F_{n-1}=\varphi^n: \varphi \equiv \frac{1+\sqrt{5}}{2}$ ,conclude $\varphi^{10}$

Question

I have this Fibonacci sequence

$F_i=i, i \in\{0,1\}, F_n=F_{n-1}+F_{n-2}, n \geq 2$

and have to prove by induction that:

$\forall n \geq 1, F_n \varphi+F_{n-1}=\varphi^n: \varphi \equiv \frac{1+\sqrt{5}}{2}$

and conclude $\varphi^{10}$

I've started the solution but I've not been able to finish :(

$\\ 1) ~ \text {prove for } n=1 \\ F_1=1, F_0=0 \\ F_1 \varphi+F_0=\varphi+0=\varphi=\varphi^1 \Rightarrow \mathrm{~OK } \\ ~ \\ 2) - \text {suppose that the equation is correct for } n \\ F_n \varphi+F_{n-1}=\varphi^n \\~\\ 3) ~ \text{prove for } n+1 \\ F_{n+1} \varphi+F_n=\varphi^{n+1} \\~\\ \text{ but from the question: } \\ F_n=F_{n-1}+F_{n-2} \\ \Rightarrow F_{n+1}=F_{n+1-1}+F_{n+1-2} \\ \Rightarrow F_{n+1}=F_n+F_{n-1} \\~ \\ F_{n+1} \varphi+F_n=\varphi^{n+1} \\ =\left(F_n+F_{n-1}\right) \varphi+F_n \\ =F_n \varphi+F_{n-1} \varphi+F_n \\ =F_n (\varphi+1) +F_{n-1}\varphi$

here I've stoped and not known how to complete help me please

Answer 1

You are very, very close. You've made a mistake in the last line: it should read $$F_n \varphi + F_{n-1} \varphi + F_n = F_n (\varphi + 1) + F_{n-1} \color{red}{\varphi}.$$ Then, you should observe that $$\varphi + 1 = \varphi^2,$$ because $\varphi$ is a root of the quadratic polynomial $$x^2 - x - 1 = 0.$$ Therefore, $$F_n (\varphi + 1) + F_{n-1} \varphi = F_n \varphi^2 + F_{n-1} \varphi = \varphi (F_n \varphi + F_{n-1}) = \varphi \varphi^n = \varphi^{n+1}.$$