Fibonacci Rules: \begin{align*} F_0 = 0 && F_1 = 1 && F_{n+2} = F_n + F_{n+1} \end{align*}
The first ten terms of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
If you pull out a calculator and compute ratios of consecutive Fibonacci numbers, you'll find that the ratio tends toward 1.6180339.... This number is the golden ratio, denoted $\boldsymbol{\varphi}$ (the Greek letter phi). Its exact value is $\varphi = \frac{1+\sqrt{5}}{2}$, and $\varphi$ is the positive solution to the quadratic equation $x^2 = 1 + x$.
Prove, by induction, that $\varphi^{n+1} = \varphi \cdot F_{n+1} + F_n$ for all natural numbers $n$.
While you can solve this problem by substituting $\varphi = \frac{1+\sqrt{5}}{2}$ and doing a bunch of algebra, you might find it more useful to use the fact that $\varphi$ is a solution to the equation $x^2 = x + 1$
My Working:
P(n) = $\varphi^{n+1}$ is equal to $\varphi * F_{n+1} + F_n$
My base case:
P(0):
$\varphi^1$ = $\varphi * F_1 + F_0$ = $\frac{1+\sqrt{5}}{2}$
I assume P(k) is true so I can prove P(k+1)
P(k+1):
$\varphi^{k+2}$ = $\varphi * F_{k+2} + F_{k+1}$
This is where my problem main starts: I can't simplify this further to prove it because I don't understand how $\varphi$ being the solution to $x^2 = 1 + x$ is suppose to help me solve the problem. Can someone please explain me that? I'm only asking for an explanation and hints, if possible please don't write the entire solution to the proof.
If $\varphi^{k+1}=\varphi F_{k+1}+F_{k}$ then:
$$\varphi^{k+2}=\varphi\varphi^{k+1}=\varphi^2F_{k+1}+\varphi F_{k}\\ =(\varphi+1)F_{k+1}+\varphi F_k=\varphi(F_{k+1}+F_k)+F_{k+1}\\ =\varphi F_{k+2}+F_{k+1}$$