# Fibonacci Number Proof

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 1:15

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

-
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
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
@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

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.

-