Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The base case should include $f(7)=13$, then you can apply the recursion. Just remember $2.5\gt2.25$. –  robjohn Mar 30 at 23:52
    
Hint: $1.5 + 1 \ge 1.5^2$. –  Carsten Schultz Mar 30 at 23:54

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
Thanks! Now it seems so obvious! –  theGuy05 Mar 31 at 0:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.