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?

  • 3
    $\begingroup$ 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? $\endgroup$ – Emanuele Paolini Nov 7 '15 at 19:24
  • $\begingroup$ 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$. $\endgroup$ – user230283 Nov 7 '15 at 19:27
  • 2
    $\begingroup$ 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$. $\endgroup$ – Emanuele Paolini Nov 7 '15 at 19:31
  • 1
    $\begingroup$ Maybe duplicate of this question: math.stackexchange.com/questions/894743/… ? $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy