The Fibonacci sequence $0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, ... is defined as a sequence whose two first terms are $F_0=0$, $F_1=1$ and each subsequent term is the sum of the two previous ones: $F_n = F_{n-1} + F_{n-2}$ (for $n \geq 2$). Prove that $F_n < 2^n$ for every $n \geq 0$.
My solution:
Basic step: $F_2=1 < 2^2$
Inductive step: Suppose $F_i<2^i$ for $i \leq n$. Show that $F_{n+1} < 2^{n+1}$.
$F_{n+1}=F_{n} + F_{n-1} < 2^n + 2^{n-1}<2^{n} + 2^{n} = 2^{n+1}$.
Do I have the right to use mathematical induction that way in the proof? If so, can you explain why compared to the usual definition of induction?
Take $n=0$ AND $n=1$ as base case. Assume the truth for $n-1$ AND $n$ and then prove the claim for $n+1$.
I do not think it is correct to use $P(n)$ and $P(n-1)$ if the base case only covers $P(2)$.