For this problem, Fibonacci sequence is defined such that
F1 = 1
F2 = 2
F3 = 3
F4 = 5
etc.
And Fn = F(n-1) + F(n-2)
An = Fn/F(n-1)
I have to prove that for all n >= 2, An <= 2
So far, I solved the base case.. 2/1 <= 2
But now, I'm completely lost. I'm hoping somebody can point me in the right direction.
F1 = 1
F2 = 2
F3 = 3
F4 = 5
etc.
And Fn = F(n-1) + F(n-2)
An = Fn/F(n-1)
I have to prove that for all n >= 2, An <= 2
So far, I solved the base case.. 2/1 <= 2
But now, I'm completely lost. I'm hoping somebody can point me in the right direction.
-
Fn = F(n-1) + F(n-2) now divide by F(n-1)
Fn/F(n-1) = 1 + F(n-2)/F(n-1)
Fn/F(n-1) = An so that
An = 1 + F(n-2)/F(n-1)
An - 1 = F(n-2)/F(n-1)
F(n-2)/F(n-1) must always < 1
Therefore
An - 1 < 1
An < 2
Fn/F(n-1) = 1 + F(n-2)/F(n-1)
Fn/F(n-1) = An so that
An = 1 + F(n-2)/F(n-1)
An - 1 = F(n-2)/F(n-1)
F(n-2)/F(n-1) must always < 1
Therefore
An - 1 < 1
An < 2