# Showing that the $n$-th Fibonacci number $f_n$ satisfies $f_n < 2^n$

Question: The Fibonacci numbers are $1,1,2,3,5,8,13,21,34,\dotsc$ In general, the Fibonacci numbers are defined by $f_1=1$, $f_2=1$, and $f_n = f_{n-1} + f_{n-2}$ for $n \geq 3$. Prove that the $n$-th Fibonacci number $f_n$ satisfies $f_n < 2^n$.

I know that I am supposed to use induction to prove this. I'm just not sure where to start. I set $n=1$, which made $f_n = f_1 < 2^1$. Therefore, I believe $n=1$ satisfies $f_n < 2^n$. I think I now need to set $n= k + 1$ where $k$ is some integer. I do not know where I should plug this in. Looking for some guidance please!

• Please use Math Jax (Latex code) in the future. Thank you. I edited your question accordingly. – amsmath Aug 28 '18 at 23:15
• That is to say, the sequence less than doubles between terms asymptotically – Jacob Wakem Aug 28 '18 at 23:15
• Possible duplicate of math.stackexchange.com/questions/894743/… – lhf Sep 4 '18 at 10:19

Hint $$2^{n-1}+2^n < 2^n+2^n=2^{n+1}$$
Because $f_n = f_{n-1} + f_{n-2}$ you will need to do a 2 step induction. I.e. show it is true for $f_1$ and $f_2$, then assuming it is true for $n-2$ and $n-1$ show it is also true for $n$.