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.

The Fibonacci sequence $F_0, F_1, F_2,...,$ are defined by the rule $$F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$$ Use induction to prove that $F_n\geq2^{0.5n}$ for $n\geq 6$


So far I have done the basis step plugging in $6$ and getting $8$ in return. Next I do the inductive step now I have $F_{k+1}=F_k+F_{k-1}$ and use the $F_n\geq2^{0.5n}$ they gave me I end up with $$2^{\frac{n}{2}}+2^{\frac{n-1}{2}}$$ at which point I get stuck I try and simplify the expression but what I end up with is different from the solutions. Can someone walk me throught this proof and explain how to do it please?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

It is almost finished. But for the induction to work, we also need to verify the inequality for $n=7$.

After that, all we need to do is to prove that $$2^{\frac{n}{2}}+2^{\frac{n-1}{2}}\gt 2^{\frac{n+1}{2}}.$$ Equivalently, we want to show that $$1+2^{-1/2} \gt 2^{1/2}.$$ Calculator!

share|improve this answer
    
why is the inequality sign flipped? –  notamathwiz Oct 1 '13 at 6:48
    
We want to prove that $F_{n+1} \gt 2^{(n+1)/2}$. We know that $F_n\gt 2^{n/2}$ and $F_{n-1}\gt 2^{(n-1)/2}$. So $F_{n+1}\gt 2^{n/2}+2^{(n-1)/2}$. If we can prove that this sum is $\gt 2^{(n+1)/2}$, we will have the result. –  André Nicolas Oct 1 '13 at 6:52
    
also when i try and verify 7 i dont get the right answer $2^{7/2}$ = 11.31 not 13 as it should –  notamathwiz Oct 1 '13 at 6:56
    
This is consistent with the desired result. We want to prove that $F_n\gt 2^{n/2}$. And indeed $13=F_7\gt 2^{7/2}\approx 11.3$. –  André Nicolas Oct 1 '13 at 6:59
    
thanks, you helped alot –  notamathwiz Oct 1 '13 at 7:26

Hint: $2^{\frac{n}{2}} + 2^{\frac{n-1}{2}} < 2^{\frac{n}{2}} + 2^{\frac{n}{2}}$.

share|improve this answer

Induct on n:

Base case, n=6: $$F_6 >= 2^{0.5n}$$ $$13 >= 2^3$$

Inductive assumptions: $$F_n >= 2^{0.5n}$$ $$F_{n-1} >= 2^{0.5(n - 1)}$$ $$n > 6$$

Recursive case: $$F_{n+1} >= 2^{0.5(n + 1)}$$ $$F_n + F_{n - 1} >= 2^{0.5n} \cdot 2^{0.5}$$ $$\text{by the first inductive assumption, }$$ $$\text{and both factors on the right being no less than 1}$$ $$\text{the above is implied by:}$$ $$F_{n - 1} >= 2^{0.5}$$ $$\text{For } n > 6, 2^{0.5(n - 1)} >= 2^{0.5}$$ $$\text{so the above is implied by}$$ $$F_{n - 1} >= 2^{0.5(n - 1)}$$ $$\text{which is the second inductive assumption. QED.}$$

share|improve this answer

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.