Answer to Question #120775 in Wolfram Mathematica for Nina

Question #120775
Is the Fibonnaci sequence rising faster than the exponential function?
1
Expert's answer
2020-06-08T16:43:05-0400

Let fnf_n be the nthn^{th} Fibonacci number.

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

Base case:

f0=0<20,f_0=0<2^0, f1=1<21.f_1=1<2^1.

Induction step:

Assume fk<2kf_k<2^k for all knk\leq n, then

fk+1=fk+fk1<2k+2k1<22k=2k+1f_{k+1}=f_k+f_{k-1}<2^k+2^{k-1}<2\cdot2^k=2^{k+1}

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

Hence

fn+1fn=fn1<2n1<2n=2n+12n<en(e1)=en+1en.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.


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment