1

Let $F_{n}$ be a Fibonacci sequence given by $$F_{n}=\begin{cases} 0 & \text{ if } n=0 \\ 1 & \text{ if } n=1 \\ F_{n-1}+F_{n-2} & \text{ if } n\geq 2. \end{cases}$$ I was asked to prove that $(3/2)^{n-1}\leq F_{n}$ holds for all $n\geq 6$. I fail to satisfy the Inductive Step. Assume that it holds for some $n=k$ and I wish to show that it is true for $n=k+1$. We have $$\left ( \frac{3}{2} \right )^{k}=\frac{3}{2}\left ( \frac{3}{2} \right )^{k-1}\leq \frac{3}{2}F_{k}\overset{?}<F_{k+1}.$$ Is there another correct way to show it?

Brian M. Scott
  • 616,228
UnknownW
  • 2,008

1 Answers1

1

Note: As remarked by @ThomasAndrews, it is absolutely essential that the induction start somewhere. In particular, in this case one must check that the desired inequality holds for $F_6$ and $F_7$. This is not difficult (by straight computation), but it has to be done. Worth remarking that the inequality is false below $6$, but happily true for $F_6=8>(\frac 32)^5\sim7.59$. (just to be thorough , $F_7$ passes easily as $F_7=13>(\frac 32)^6\sim 11.39$).

From the recursion (and the induction hypothesis) we have $$F_n=F_{n-1}+F_{n-2}≥\left(\frac 32\right)^{n-2}+\left(\frac 32\right)^{n-3}=\left(\frac 32\right)^{n-3}\left(\frac 32+1\right)$$

All that remains is for you to verify that $$\left(\frac 32+1\right)≥\left(\frac 32\right)^2$$

lulu
  • 70,402
  • 1
    The induction hypothesis, as the OP stated it, is not enough. Worth pointing out that you are assuming the two previous values have the property. (In particular, then, this means you have to prove the cases $n=6$ and $n=7$ separately.) – Thomas Andrews Oct 30 '15 at 19:32
  • @ThomasAndrews True, of course. I had trusted that the OP had covered that. I'll amend the solution accodingly. – lulu Oct 30 '15 at 19:34
  • I have proven the induction start, only for $n=6$ and not above since I was too lazy. But is it an good idea to use the strong induction in this case? I like your idea. – UnknownW Oct 30 '15 at 19:42
  • @AjmalW The recursion goes deeper than one level, so I'd use induction beyond one level. So, I would check $F_7$ as well (just takes a second). You never need more than two levels so I guess it is somewhere in between strong induction and the ordinary form. – lulu Oct 30 '15 at 19:45