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.

How can I prove this statement? Would I use induction?

"Given $n \geq 11$, show that $a_n > (3/2)^{n}$. $a_n$ is the $n$th Fibonacci number."

share|improve this question
    
Since $\sqrt[n]{a_n} \to \phi=(1+\sqrt5)/2 \approx 1.618$, there is not much improvement you can make to $3/2$. The proof given by Old John proves that $a_n> t^n$ for all $t$ such that $t+1>t^2$. The hard part is the base case for the induction. The closer $t$ gets to $\phi$, the larger the base case. For instance, for $t=1.6$ you need $n\ge72$. –  lhf Sep 25 '12 at 1:15
add comment

2 Answers

up vote 6 down vote accepted

Yes, induction is the way to go. Assume the result is true for two consecutive integers $n$ and $n+1$ and then deduce that it must be true for $n+2$. The rest should be easy, after you find 2 consecutive values for which it is definitely true.

To explain a bit more:

Assume the result is true for $n$ and for $n+1$, i.e. assume we have $a_n > (3/2)^n$ and $a_{n+1} > (3/2)^{n+1}$.

Adding these two, we get $a_{n+2} = a_{n+1} + a_n > (3/2)^{n+1} + (3/2)^n = (3/2)^n(3/2 + 1) = (3/2)^n(5/2) > (3/2)^{n+2}$

at the last step we use the fact that $5/2 > 9/4 = (3/2)^2$

Now we know that if the result is true for $n$ and $n+1$, then it follows that it is true for $n+1$ and $n+2$.

share|improve this answer
    
So should I select n = 11 and n+1 = 12? My friend mentioned something about choosing n = 11 and n-1 = 10, since the definition of Fibonacci number is F(n+1) = F(n) + F(n-1). Would this also work, or is the first option easier? –  user41419 Sep 24 '12 at 23:03
1  
For the induction step you do not need to specify the values of $n$ and $n+1$ at all. For the "starting values" you just need to select the smallest value of $n$ for which $F(n)>(3/2)^n$ and $F(n+1)>(3/2)^{n+1}$ –  Old John Sep 24 '12 at 23:06
    
@OldJohn I think you should say more about what type of induction you have in mind. I cannot infer anything about the specific proof that you have in mind from what little you have written in your two-sentence answer. –  Bill Dubuque Sep 24 '12 at 23:16
    
So my base case would be n = 11 and n+1 = 12, and that's all I would need to test, correct? Then how would I go about the induction step given this information? (Sorry, I've never done a problem with strong induction before) –  user41419 Sep 24 '12 at 23:17
1  
@OldJohn It would be impossible for anyone but a mindreader to indubitably infer what proof was intended from those two sentences. In any case, I am glad to see that you did elaborate. But, alas, I'm puzzled by the tone of your comments. –  Bill Dubuque Sep 25 '12 at 2:36
show 8 more comments

Hint $\ $ The second order recurrence for $\rm\:f(n)\:$ yields one for $\rm\:f(n)-c^n,\:$ namely, more generally, $$\begin{eqnarray}\rm &&\rm f(n\!+\!2) &=&\rm\ a\ f(n\!+\!1)\ +\ b\ f(n)\\ \Rightarrow\ &&\rm f(n\!+\!2)-c^{n+2} &=&\rm\ a\,(f(n\!+\!1)-c^{n+1}\!)\ +\ b\,(f(n)-c^n)\ -\ c^n(\color{#C00}{c^2 - a\,c -b})\end{eqnarray}$$

So we can inductively infer positivity of the LHS from positivity of the $3\,$ summands on the RHS, which follows if $\rm\:a,b,c > 0\:$ and $\rm\:\color{#C00}{f(c)} < 0\:$ for the characteristic polynomial $\rm\:\color{#C00}{f(x)\, =\, x^2 - a\,x - b}.$

In your case $\rm\:a,b,c\, =\, 1,1,3/2\, >\, 0,\:$ and $\rm\:\color{#C00}{f(c)} = (3/2)^2\!-3/2-1 =\, \color{#C00}{-1/4} < 0,\:$ so it succeeds.

share|improve this answer
add comment

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.