I'm trying to prove $f_n \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{n-1}$ with induction, and I'm stuck in the induction step.
Basis: n = 2
$f_{2} \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{2-1} \Rightarrow
f_{2} \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{1} \Rightarrow 1 \leq \approx 1.68$
Base case is true
Ind Hyp.
Prove $n= k$ holds for 2 up to k
Ind Step
Consider $k+1$, let $\varphi = \left(\frac{1 + \sqrt{5}}{2}\right)$
LHS: $f_{k+1}=f_{k} + f_{k-1}$
$f_{k} \leq \varphi^{k-1}$ and $f_{k-1} \leq \varphi^{k-2}$
$f_{k+1} = \frac{\varphi^{k}}{\varphi} + \frac{\varphi}{\varphi^{2}}$
$f_{k+1} = \varphi^{k}\left(\frac{1}{\varphi} + \frac{1}{\varphi^{2}}\right)$
Here is where I'm stuck, I'm not sure if this was the right direction to take, but I believe I need to prove the following to continue:
$f_{k+1}< \varphi^{(k+1)-1}$
Could some one shed some light on my problem or show me a direction I can take?
Best Answer
From $f_k\le\varphi^{k-1}$ and $f_{k-1}\le\varphi^{k-2}$ you get $f_{k+1}\le\varphi^{k-1}+\varphi^{k-2}$, not $f_{k+1}=\varphi^{k-1}+\varphi^{k-2}$. Then
$$f_{k+1}\le\varphi^{k-1}+\varphi^{k-2}=\varphi^k\left(\frac1\varphi+\frac1{\varphi^2}\right)=\varphi^k\left(\frac{\varphi+1}{\varphi^2}\right)\;,$$
and you’re done as soon as you show that $\varphi+1=\varphi^2$. You can do this either by direct computation or by using the fact that $\varphi$ is a solution of the quadratic $x^2-x-1=0$.