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

Question

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!

Answer 1

Hint $$2^{n-1}+2^n < 2^n+2^n=2^{n+1}$$

Answer 2

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

Answer 3

It is easily verified that the sequence never doubles between subsequent terms, except trivially. This is sufficient to show it never on average exceeds doubling between its subsequent terms.