Proving that $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$, where $\alpha$ is the golden ratio I got stuck on this exercise. It is Theorem 1.15 on page 14 of Robbins' Beginning Number Theory, 2nd edition.

Theorem 1.15. $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$.
Proof: Exercise.

(image of relevant page)
 A: If you check the inequality when $n=1$ and $n=2$, you can argue inductively, since the powers of $\alpha$ satisfy the same order two recursion as do the fibonacci numbers.
That is, assume the statement holds for each of $n$ and $n+1$, then just add up the inequalities; you'll use e.g. $\alpha^{n-2}+\alpha^{n-1}=\alpha^n$, which follows from the relation $1+\alpha=\alpha^2$ on multiplying by $\alpha^{n-2}$. The right sides work the same way.
A: I'll give you a hint (two, actually): use strong induction, and note that 
$$ \alpha^2 = \alpha + 1$$
See if you can get somewhere from there :) 
A: Okay, we want to prove that $$\alpha^{n-2}\leq F_n \leq \alpha^{n-1}.$$
For this all we need is weak mathematical induction.  For our base case, pick $n=1$, and we have $$\alpha^{-1}=\frac{2}{1+\sqrt{5}}< 1 \leq \alpha^0=1.$$  Check.  Now let's proceed with the inductive step.  By inductive hypothesis, $$\alpha^{n-3}\leq F_{n-1} \leq \alpha^{n-2}$$ and $$\alpha^{n-4}\leq F_{n-2} \leq \alpha^{n-3}$$ so, since $F_{n}=F_{n-1}+F_{n-2}$, $$\alpha^{n-3}+\alpha^{n-4}\leq F_{n} \leq \alpha^{n-2}+\alpha^{n-3}$$
So we see it suffices to show that $$\alpha^{m-2}+\alpha^{m-1}=\alpha^{m}.$$
To prove this part, let's do a little subinduction on $m$.  (This could just have easily been proven in a lemma.)  Note that it is indeed true that $$\alpha^2=\frac{3+ \sqrt{5}}{2}=\alpha+1.$$ So now, by induction on $m$, $$\begin{eqnarray*}\alpha^{m-1}+\alpha^{m}&=&\alpha\left(\alpha^{m-2}+\alpha^{m-1}\right)\\&=&\alpha(\alpha^m)=\alpha^{m+1}.\end{eqnarray*}$$ And we're done.
A: Using Binet's Fibonacci Number Formula,
$\alpha+\beta=1,\alpha\beta=-1$ and $\beta<0$
\begin{align}
F_n-\alpha^{n-1}=
&
\frac{\alpha^n-\beta^n}{\alpha-\beta}-\alpha^{n-1}
\\
=
&
\frac{\alpha^n-\beta^n-(\alpha-\beta)\alpha^{n-1}}{\alpha-\beta}
\\
=
&
\beta\frac{(\alpha^{n-1}-\beta^{n-1})}{\alpha-\beta}
\\
=
&
\beta\cdot F_{n-1}\le 0 
\end{align}
 if $n\ge 1$.
\begin{align}
F_n-\alpha^{n-1}=
&
\frac{\alpha^n-\beta^n}{\alpha-\beta}-\alpha^{n-2}
\\
=
&
\frac{\alpha^{n-1}\cdot \alpha-\beta^n-\alpha^{n-1}+\beta\cdot \alpha^{n-2}}{\alpha-\beta}
\\
=
&
\frac{\alpha^{n-1}\cdot (1-\beta)-\beta^n-\alpha^{n-1}+\beta\cdot \alpha^{n-2}}{\alpha-\beta}
\\
=
&
\frac{\beta(\alpha^{n-2}-\alpha^{n-1})-\beta^n}{\alpha-\beta}
\\
=
&\frac{\beta\cdot \alpha^{n-2}(1-\alpha)-\beta^n}{\alpha-\beta}
\\
=
&
\frac{\beta\cdot \alpha^{n-2}(\beta)-\beta^n}{\alpha-\beta}
\\
=
&
\beta^2\frac{\alpha^{n-2}-\beta^{n-2}}{\alpha-\beta}
\\
=
&
\beta^2F_{n-2}\ge 0
\end{align}
if $n\ge 1$.
