Answer to Question #120775 in Wolfram Mathematica for Nina

Question

Is the Fibonnaci sequence rising faster than the exponential function?

Answer 1

Let $f_n$ be the $n^{th}$ Fibonacci number.

We will prove by strong mathematical induction that $2^n>f_n.$

Base case:

$f_0=0<2^0,$ $f_1=1<2^1.$

Induction step:

Assume $f_k<2^k$ for all $k\leq n$, then

$f_{k+1}=f_k+f_{k-1}<2^k+2^{k-1}<2\cdot2^k=2^{k+1}$

So, the inequality $f_n<2^n$ is true for $n=k+1$, thus, by strong mathematical induction $f_n<2^n$ for all $n\geq0$ and $f_n<2^n<e^n.$

Hence

$f_{n+1}-f_n=f_{n-1}<2^{n-1}<2^n=\\ 2^{n+1}-2^n<e^n(e-1)=e^{n+1}-e^n.$