# Using induction to prove an exponential lower bound for the Fibonacci sequence

The Fibonacci sequence $$F_0, F_1, F_2,...,$$ is 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?

## 3 Answers

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!

• 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
• You are welcome. That's what MSE is about. – André Nicolas Oct 1 '13 at 7:30

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

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