Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
1  
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.

share|cite|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|cite|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|cite|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|cite|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.