If $F(n)$ is the Fibonacci Sequence, defined in the following way:
$$
F(0)=0 \\
F(1)=1 \\
F(n)=F(n-1)+F(n-2)
$$
I need to prove the following by induction:
$$F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n-1} \quad \forall n \geq 0$$
I know how to prove the base cases and I know that the inductive hypothesis is "assume $F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n-1} \quad \forall n \leq k, k \geq 0$".
For the inductive step, I need to show:
$$F(k+1) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k+1}$$
$F(k) + F(k-1) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^k$ — by the definition of the Fibonacci sequence. $\bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k-1} + \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k-2} \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^k$ — by the inductive hypothesis?
If I could show this last line then I could prove the overall question but I am unsure of how to prove this and that last line may not be correct. Any help would be greatly appreciated!
Best Answer
Hint: Let $\phi = \frac{1 + \sqrt{5}}{2}$. Note that $\phi$ satisfies $$ \phi^2 = \phi + 1 $$ (as you may verify using the quadratic formula, for example) and therefore for all $k$, $\phi^k = \phi^{k-1} + \phi^{k-2}$.