# Prove that $F_n < 2^n$ for every $n \geq 0$ - Mathematical induction

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?

• what you have written is correct. You have proved that $F_n < 2^n$ for $n\ge 2$. Why do you feel that the usual definition is something different? – Emanuele Paolini Nov 7 '15 at 19:24
• In my own experience, I usually fixe an $n \in \mathbb{N}$ and prove the case $n+1$. It is different because I usually do not use values smaller than $n$. – user230283 Nov 7 '15 at 19:27
• Proving $P(n)\Rightarrow P(n+1)$ for all $n\ge 1$ is the same as proving $P(n-1)\Rightarrow P(n)$ for all $n\ge 2$. – Emanuele Paolini Nov 7 '15 at 19:31
• Maybe duplicate of this question: math.stackexchange.com/questions/894743/… ? – Martin Sleziak Nov 7 '15 at 19:55

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