Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
2  
Since you are new, I want to give you some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people are much more willing to help you if you show that you've tried the problem yourself. If this is homework, please add the [homework] tag; people will still help, so don't worry. –  Zev Chonoles Jan 3 '13 at 3:12
1  
What have you tried? Where are you stuck? Have you ever heard of strong induction? –  JavaMan Jan 3 '13 at 3:17

4 Answers 4

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.