5
$\begingroup$

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

  • 0
    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$.2012-09-25

2 Answers 2

6

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

  • 0
    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?2012-09-24
  • 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}$2012-09-24
  • 0
    @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.2012-09-24
  • 0
    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)2012-09-24
  • 0
    @user41419 simply assume it is true for $k$ and $k+1$, and show that it is true for $k+2$ (in other words prove that $a_{\,k+2}>(3/2)^k+(3/2)^{k+1}$)2012-09-24
  • 0
    So that is my inductive step? Seems simple enough... so my full proof will include showing it's true for n = 11, n+1 = 12, and assuming k, k+1 are true and proving k+2 is true. Correct?2012-09-24
  • 0
    @user41419 Correct. Think about it, if $k+2$ follows from $k$ and $k+1$, then $k+3$ will follow from $k+1$ and $k+2$, and so on...2012-09-24
  • 0
    @BillDubuque I cannot seriously contemplate that someone with reputation over 81000 is unable to fill in the steps of the proof I outlined :)2012-09-24
  • 0
    @OldJohn Of course I know many proofs. But what little you wrote in the first version of your answer gave no clue as to which proof you had in mind. A good hint should give *some* clue.2012-09-24
  • 0
    I stand by my previous comment2012-09-24
  • 0
    @OldJohn The two-sentence first paragraph of the current answer was the complete text of the first version of your answer - the version which prompted my first comment. That initial version seems to be a hint to try to devise an inductive proof using the Fibonacci recurrence relation. But that tells me nothing at all about the *specific* inductive proof that you have in mind, since almost every inductive proof of properties of Fibonacci numbers employs their recurrence. The devil is in the details of *how* to use the recurrence to achieve the induction.2012-09-24
  • 0
    Well, you said that *you* were unable to infer anything about the proof from the hint I provided - I have now elucidated the proof, and assume you can now fill in any remaining gaps :)2012-09-25
  • 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.2012-09-25
2

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.