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.

-
What have you tried? Where are you stuck? Have you ever heard of strong induction? –  JavaMan Jan 3 '13 at 3:17

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.

-

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 :)

-

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.

-
Why do you say at the start that "For this all we need is weak induction", but later use strong mathematical induction to prove the statement? IN fact, the later part doesn't need strong mathematical induction, since you can just multiply throughout by $\alpha ^{m-2}$. –  Calvin Lin Jan 3 '13 at 4:00
I used weak induction to prove the part about $F_n$ being between the $\alpha$'s and proved the lemma about the $\alpha$'s with strong induction. It doesn't really matter which one you use, anyway. EDIT: Actually you're right, the $\alpha$ lemma is fine just using weak. –  Alexander Gruber Jan 3 '13 at 4:02

$\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$.

-