<s>[INST] Proving that for Fibonacci numbers $a_n \lt (\frac {1 + \sqrt 5} 2)^n$ for $n \ge 1$ I'd like to prove that for Fibonacci numbers $a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n$ for $n \ge 1$. I suppose it needs induction so, after verifying the trivial case $n=1$, the inductive step needs to be justified: $$a_{n+1} \lt \left(\frac {1 + \sqrt 5} 2\right)^{n+1}.$$
Assume $$a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n.$$
I can only think of multiplying both sides by $\left(\frac {1 + \sqrt 5} 2\right)$, which yields $$a_n\left(\frac {1 + \sqrt 5} 2\right) \lt \left(\frac {1 + \sqrt 5} 2\right)^{n+1}$$
and then somehow show that $a_{n+1} \lt a_n\left(\frac {1 + \sqrt 5} 2\right)$.
I tried using the fact that $a_{n+1}=a_n + a_{n-1}$ but wasn't able to conclude anything useful. Can you suggest me a way to prove it?
 [/INST] Let $a_n=F_n$ and $b_n=\left(\frac{1+\sqrt{5}}{2}\right)^n$. Since $\frac{1+\sqrt{5}}{2}$ is a root of the polynomial $t^2-t-1$, we have:
$$ a_{n+2} = a_{n+1}+a_{n}\quad\text{as well as}\quad b_{n+2}=b_{n+1}+b_n, \tag{1}$$
hence in order to prove that
$$ a_n < b_n \tag{2}$$
holds for every $n\geq 1$ it is enough to check that $(2)$ holds for $n=1,2,$ then apply induction exploiting $(1)$.
</s>