The Fibonacci numbers are defined with the recursive formula: F0 =1,F1 =1,Fn =Fn−1+Fn−2 I have tried using induction to show that Fn ≤ 1.7^(n) for all n ≥ 0. However, I got to a point where I was trying to use a limit to show the bounds. I would appreciate it if someone could help me get past this point.
I am also interested to know the answer of this question.
The Fibinacci numbers grow exponentially, not linearly, with their index. So it’s not surprising that it’s not possible to show that they satisfy the bound mentioned.
Just write F_(n+1)=F_n + F_(n-1) along with F_n =F_n and write these two equations in matrix form:
z_(n+1)=A.z_n
where z_n=(F_n,F_(n-1))^T. The matrix A has rows 1,1 and 1,0. So it’s symmetric, can be diagonalized and z_n=A^(n-1)z_1.
Now det A = -1, which means that the product of the eigenvalues is -1. Therefore, in absolute value, one is less, the other is greater than 1. So F_n~λ^n, for n large, where λ is the eigenvalue, whose absolute value is greater than 1.
This is a typical exercise when studying sequences...
Hi,
it is known that lim F_{n+1}/F_n=(1+\sqrt{5})/2=\phi=1.618... (the golden ratio). Hence, you cannot prove that F_n
Evan Gertis In view of the explicit formula
F_n=1/\sqrt{5}(\phi^n-(1-phi)^n)
where \phi=(1+\sqrt{5})/2=1.618...
The general form of the Fibonacci sequence is given in the image . You can also use the formula mentionned by Yuri S Semenov
- Badges
- Science topic
- Similar topics
- Analytical Chemistry
- Extraction