Prove $F(n) < 2^n$

Question

The Fibonacci sequence is defined as $$F(1) = 1, F(2) = 1, F(n) = F(n−2)+F(n−1) \text{for } n > 2$$

I need to prove $$F(n) < 2^n$$

Answer 1

you can do this problem using $\color{red}{\textbf{strong}}$ mathematical induction as you said.

First you have to examine the base case.

Base case $n=1,2$

Clearly $F(1) = 1 < 2^1=2$ and $F(2) = 1 < 2^2=4$

Now you assume that the claim works $\textbf{up to a}$ positive integer $k$. i.e $$F(k) < 2^{k}$$

Now you want to prove that $F(k+1) < 2^{k+1}$

We already know that $F(k+1) =F (k) + F(k-1)$

By our assumption we know that $F(k) < 2^{k}$ and $F(k-1) < 2^{k-1}$

because we used strong mathematical induction and not just regular induction.

And so we have that $F(k+1) < 2^k + 2^{k-1} < 2^k + 2^k = 2(2^k) =2^{k+1}$ and you are done $\square$

Answer 2

Use induction.

For $n=0,1$ the statement $F(n) < 2^n$ is true (since $0<1$ and $1<2$).

Assume the statement is true for $n - 1$ and $n$. Then, for $n + 1$:

$F(n + 1) = F(n) + F(n - 1) < 2^n + 2^{n-1} < 2^n + 2^n = 2 \cdot 2^n = 2^{n+1}$

So, the statement is true for all $n \in \mathbb{N}$.

Answer 3

You can use a proof by induction to show this. It is clear that $$ \begin{align*} F(1) = 1 &< 2 = 2^1 \; , \\ F(2) = 2 &< 4 = 2^2 \; . \end{align*}$$ Now assume that the proposition is true for $n, n-1 \in \Bbb N$, i.e. $F(n) < 2^n$ and $F(n-1) < 2^{n-1}$. Show that $$ F(n+1) < 2^{n+1} $$ by using these assumptions.