<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] First note the following (this will show the relevance of Antoine's comment):
$$
\left(\frac{1+\sqrt{5}}{2}\right)^n > \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n > \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n.
$$
The explicit formula for Fibonacci numbers that Antoine's comment is presumably referring to is Binet's formula, which states that, for every $n\geq 0$, that
$$
F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right],
$$ 
where $F_n$ is the $n$th Fibonacci number. Hence, if you can prove Binet's formula, then you will have certainly proven what you set out to prove because
$$
\left(\frac{1+\sqrt{5}}{2}\right)^n > \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right] = F_n.
$$
Thus, let's prove Binet's formula using induction, and your result will follow as a "trivial" consequence, as Antoine's comment notes.

For every $n\geq 0$, let $A(n)$ denote the statement
$$
A(n) : F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right].
$$
Base step: When $n=0$, the expression on the right-hand side of $A(n)$ is $0$, which is $F_0$. For $n=1$, it is also not difficult to check that each side of $A(n)$ is $1$. 
Inductive step ($[A(k-1)\land A(k)]\to A(k+1)$): Suppose that for some fixed $k$, that $A(k-1)$ and $A(k)$ are true. Calculating, (where the second equality below follows from $A(k-1)$ and $A(k)$),
\begin{align}
F_{k+1} &= F_{k-1}+F_k\\[1em]
&= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k}-\left(\frac{1-\sqrt{5}}{2}\right)^{k}\right]\\[1em]
&= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(1+\frac{1+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(1+\frac{1-\sqrt{5}}{2}\right)\right]\\[1em]
&= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(\frac{3+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(\frac{3-\sqrt{5}}{2}\right)\right]\\[1em]
&= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(\frac{1-\sqrt{5}}{2}\right)^2\right]\\[1em]
&= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}\right],
\end{align}
so $A(k+1)$ is also true, completing the inductive step.
By mathematical induction, for each $n\geq 0, A(n)$ is true. 
Your own claim follows as a result.
</s>