Prove $F(n) < 2^n$ Consider the Fibonacci function $\large{F(n)}$, which is deﬁned such
that $F(1) = 1, F(2) = 1$, and $F(n) = F(n−2)+F(n−1)$ for $n > 2$ 
I know that I should do it using mathematical induction but I don't know how to approach it.
Can anyone help me prove  $F(n) < 2^n$.
Thank so much
 A: 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$
A: 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}$.
A: 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.
