Could anyone check if my proof is correct? Thanks!
Statement:The Fibonacci number are defined by $f_{1}=1,f_{2}=1 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$
Proof: I shall do this by induction.
Firstly we check the base cases $n=1,2$
For $n=1$,
$1<2$
For $n=2$,
$1<4$
We then consider some $n=k$ and assume that for $n=k-1$ and $n=k-2$ the relation holds. Then for $n=k$,
$f_{k}=f_{k-1}+f_{k-2}<2^{k-1}+2^{k-2}=\frac{3}{4}2^k$
$f_{k}<\frac{3}{4}2^k\Rightarrow f_{k}<2^k$
By this, we have proved that if the relation holds for $n=k-1$ and $n=k-2$, then it will hold for $n=k$. Since we have checked if $n=1,2$ holds and they do, it holds for all $n\in\Bbb{N}$.