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 "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=\\\\\n2^{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

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS