2
$\begingroup$

I have fibonacci numbers defined as such:

$$ f(n) = f(n-1) + f(n-2)$$with$$ f(0) = 0 $$$$f(1) = 1$$

I have to prove that $$ F(n) \geq 1.5^{n-1}, n \geq 6$$

Base Case:

$$ f(6) = 8 \geq (1.5)^5 = 7.6 $$ Base holds

Inductive hypothesis $$ k \geq 6 $$$$ f(k) \geq (1.5)^{k-1} $$

Inductive Step

Here is how I have started, any hints or pointers on how to continue are appreciated

$$ f(k-1) \geq (1.5)^{k+1-1}$$ $$ f(k) + f(k-1) = (1.5)^{k-1} + (1.5)^{k-2}$$ now I think where I want to go from here is to expand the right side of this equation out, but I am unsure how to do this.

$\endgroup$
2
  • $\begingroup$ The base case should include $f(7)=13$, then you can apply the recursion. Just remember $2.5\gt2.25$. $\endgroup$ Commented Mar 30, 2014 at 23:52
  • $\begingroup$ Hint: $1.5 + 1 \ge 1.5^2$. $\endgroup$ Commented Mar 30, 2014 at 23:54

1 Answer 1

Reset to default
2
$\begingroup$

It's actually easier to use two base cases (corresponding to $n = 6,7$), and then use the previous two results to induct: Notice that if both $$f(k - 1) \ge (1.5)^{ k - 2}$$ and $$f(k) \ge (1.5)^{k - 1}$$

then we have

\begin{align*} f(k+1) &= f(k) + f(k - 1) \\ &\ge (1.5)^{k - 1} + (1.5)^{k - 2} \\ &= (1.5)^{k - 2}\Big(1.5 + 1\Big) \\ &> (1.5)^{k - 2} \cdot (1.5)^2 \end{align*} since $1.5^2 = 2.25 < 2.5$.

$\endgroup$
1
  • $\begingroup$ Thanks! Now it seems so obvious! $\endgroup$ Commented Mar 31, 2014 at 0:13

You must log in to answer this question.