Strong Induction for Fibonacci

Question

I'm a little lost of how to use strong induction to prove the following for the Fibonacci sequence:

$F_n < 2^n$ for all natural numbers

Any help would be very much appreciated!!

Answer 1

Hint:

To prove the statement for $n$: $F_n<2^n$

It would help to have as hypotheses the statement for $n-1$: $F_{n-1}<2^{n-1}$

and also the statement for $n-2$: $F_{n-2}<2^{n-2}$. Then, you could add the inequalities...

Answer 2

Hint: $F_0=0<2^0$, $F_1=1<2^1$. If the statement holds for every $m<n$, where $n\ge2$, then $$ F_n=F_{n-1}+F_{n-2} $$ and $n-1<n$, $n-2<n$, so…

Answer 3

I assume that your definition of Fibonacci numbers is the following: $F_1=1$, $F_2=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\geq 3$.

---

You want to prove that $F_n< 2^n$ for all $n\geq 1$. The property holds for $F_1$ and $F_2$. Then suppose $n\geq 2$ and that $F_k<2^k$ holds for $1\leq k\leq n$, then $$ F_{n+1} = F_n + F_{n-1} < 2^n + 2^{n-1} < 2^{n+1}, $$ and you are done.

Answer 4

Note that $F_1=1<2^1$ and $F_2=1<2^2$, so $F_n<2^n$ is true for $n=1$ and $n=2$.

Now, suppose that $F_n<2^n$ for some $n$.

Then $F_{n+1} = F_n+F_{n-1}\le 2\cdot F_n < 2\cdot 2^n = 2^{n+1}$.

So, by induction, $F_n<2^n$ for all $n\in\mathbb{N}$.