5

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

  • 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 01:15

2 Answers2

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

Old John
  • 19,569
  • 3
  • 59
  • 113
  • 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? –  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) –  Sep 24 '12 at 23:17
  • @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}$) –  Sep 24 '12 at 23:19
  • 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? –  Sep 24 '12 at 23:24
  • @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... –  Sep 24 '12 at 23:32
  • @BillDubuque I cannot seriously contemplate that someone with reputation over 81000 is unable to fill in the steps of the proof I outlined :) – Old John Sep 24 '12 at 23:34
  • @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. – Bill Dubuque Sep 24 '12 at 23:40
  • I stand by my previous comment – Old John Sep 24 '12 at 23:42
  • @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. – Bill Dubuque Sep 24 '12 at 23:59
  • 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 :) – Old John Sep 25 '12 at 00:11
  • 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 02:36
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.

Bill Dubuque
  • 272,048