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

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