What is the Convergence of the Fibonacci Sequence?

[al-mahed]

Hi,

I would like some help in this problem:

given the fibonacci sequence 1,2,3,5,8,13...

we know that a_n/a_(n-1) --> phi when n --> \infty

I have tried a new proof in these terms:

My goal is to prove that when n --> \infty, a_n/a_(n-1) = a_(n+1)/a_n in the limit

I have notice that a_n^2= a_(n-1)*a_(n+1) \pm 1 for some values

Dividing both sides of the equation by a_n*a_(n-1)

\frac{a_n}{a_n_-_1} = \frac{a_n_+_1}{a_n}\pm \frac{1}{a_n*a_n_-_1}

I want to find the limits, because the second term in the right side of the equation --> 0 when n --> \infty

But I don't know if the equation above is valid for all n, so I'll prove this by induction as follows:

supose that the expression above is valid for some n

by definition a_(n+1)=a_n + a_(n-1)

a_n^2= a_(n-1)*[a_n + a_(n-1)] \pm 1 ==> a_n^2 - a_(n-1)^2= a_(n-1)*a_n \pm 1 ==>

==> [a_n + a_(n-1)]*[a_n - a_(n-1)] = a_(n-1)*a_n \pm 1

by definition a_n - a_(n-1)= a_(n-2) ==>

==> [a_n - a_(n-1)]* a_(n-2) = a_(n-1)*a_n \pm 1

by definition a_n = a_(n-1) + a_(n-2) ==>

==> [a_n - a_(n-1)]* a_(n-2) = a_(n-1)*[a_(n-1) + a_(n-2)] \pm 1 ==>

==> a_(n-2)*a_n + a_(n-1)*a_(n-2) = a_(n-1)^2 + a_(n-1)*a_(n-2) \pm 1 ==>

==> a_(n-1)^2 = a_(n-2)*a_n \pm 1

compare the two expressions

a_n^2= a_(n-1)*a_(n+1) \pm 1

a_(n-1)^2 = a_(n-2)*a_n \pm 1

most generally we have

\{a}{_i}{^2}} = \{a_i_-_1*a_i_+_1}} \pm 1, with i=2,3,4,5,6...,n

proving by induction (sorry about the english and notation)

Hence,


Lim\{_n_-_>_i_n_f_i_n_i_t_y}\frac{a_n}{a_n_-_1}} = Lim\{_n_-_>_i_n_f_i_n_i_t_y}\frac{a_n_+_1}{a_n}\pm \frac{1}{a_n*a_n_-_1}}


Lim\{_n_-_>_i_n_f_i_n_i_t_y}\pm \frac{1}{a_n*a_n_-_1}} = 0

in the limit \frac{a_n}{a_n_-_1} = \frac{a_n_+_1}{a_n}

Why this do not prove the convergence?

 

[BoTemp]

I'm not sure what you're trying to prove. When you say convergence, are you trying to prove that in the \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = 1?

That would imply that the sequence of numbers goes to some final value, although the sum of those numbers would still diverge since that number isn't 0.

The sequence grows uniformly, a_n+1 > a_n, so a_n+1/a_n > 1 always. What you've done is prove that

\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = constant

With further math you'll be able to solve for that constant as phi, the golden ratio. You can set up a quadratic equation, solve for it, and get phi.

Starter:
a_{n+1} = a_n + a_{n-1} divide both sides by a_n

\frac{ a_{n+1} }{a_n} = 1 + \frac{ a_{n-1} }{a_n} }

Take the limit as n goes to infinity, define
\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = x, and go.

 

[al-mahed]

BoTemp, I am not so good in english. What I'm trying to prove is that the sequence of the terms a_n/a_(n-1), ... is convergent to a value, not the sum of these ratios (not series, like 1 + 1/2 + 1/3 + ...).

I know the formulas to find the golden ratio (1 + 5^1/2)/2, I would like to know if that proof is correct, if I could conclude that there is a limit or not.

thanks

 

[HallsofIvy]

"My goal is to prove that when n --> , a_n/a_(n-1) = a_(n+1)/a_n in the limit"

That's simply adjusting the indices. Let j= n-1. Then a_n-1= a_j and a_n= a_j+1. The sequence a_n/a_n-1 is exactly the same as a_j+1/a_j which is, in turn, exactly the same as a_n+1/a_n just labled differently. In the limit as n goes to infinity, j also goes to infinity and the two sequences have the same limit.

 

[al-mahed]

a_n/a_(n-1) \neq a_(n+1)/a_n for all n that you can test by yourself, is quite different to say
\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \frac{a_n}{a_{n-1}}

 

[EnumaElish]

I may be misunderstanding, but the limit value cannot include subscripts "n" or "n-1."

 

[al-mahed]

I may be misunderstanding, but the limit value cannot include subscripts "n" or "n-1."

what you mean EnumaElish?

 

[EnumaElish]

In your statement

\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \frac{a_n}{a_{n-1}}

the right-hand side cannot have a_n or a_{n-1}. The limit must be independent of n.

Did you mean \lim_{n \rightarrow \infty} \left({a_{n+1}}\left/{a_n}\right.\right) = \lim_{n \rightarrow \infty} \left({a_n}\left/{a_{n-1}}\right.\right)? [1]

If so, [1] does not prove convergence because it presumes that a limit exists in the first place. If there is no limit then [1] has no meaning.

 

[al-mahed]

I meant [1] as you said, sorry my mistake.

I see what you mean, my dificult is:

if [1] does not prove the convergence, why the procedure below do?

\frac{ a_{n+1} }{a_n} = 1 + \frac{ a_{n-1} }{a_n} } ==>

==> phi = 1 + 1/phi ==> phi = (1 + 5^1/2)/2

Here I'm suposing that there is a limit like the other solution, right?

Thanks for your help!

 

[EnumaElish]

Since a(n) > 0 for all n > 0 and a(n+1) = a(n) + a(n-1), {a(n)} is an increasing sequence for all n > 1.

Let r(n+1) = a(n+1)/a(n), then r(n+1) > 1 for all n > 1.

Suppose lim r(n) = infinity. Then lim 1/r(n) = 0. But since lim r(n+1) = 1 + lim 1/r(n), this implies infinity = 1, a contradiction. Therefore I can conclude that lim r(n) = L < infinity.

Then you can solve L = 1 + 1/L.

 

[al-mahed]

"Therefore I can conclude that lim r(n) = L < infinity."

as 0 < a(n-1)/a_n < 1 ==> 1 < a(n-1)/a_n + 1 < 2 ==> 1 < a(n+1)/a_n < 2

and if the values oscillate between 1 and 2? you prove that the limit do not diverges to infinity, but this not implies that there is a limit, am I right?

f(x) = sen(x), lim sen(x) is not infinite when x --> infinity, but there is no limit, the function oscillate between -1 and 1

 

[EnumaElish]

Yes, you are right; which makes it clear that one cannot presume a limit exists.

 

[al-mahed]

I see, you're right...

We could prove convergence starting with this fact: 1 < a(n+1)/a_n < 2 , showing (I presume) that the sequence is bounded

to prove that it is monotonic, we should work with \frac{a_n}{a_n_-_1} = \frac{a_n_+_1}{a_n}\pm \frac{1}{a_n*a_n_-_1}

for n even \frac{a_n}{a_n_-_1} = \frac{a_n_+_1}{a_n} - \frac{1}{a_n*a_n_-_1}

for n odd \frac{a_n}{a_n_-_1} = \frac{a_n_+_1}{a_n} + \frac{1}{a_n*a_n_-_1}

a_n < a_(n+1) < a_(n+2) < a_(n+3) < ... ==> \frac{1}{a_n*a_n_-_1} --> 0 ==> the sequence \frac{a_n}{a_n_-_1} increase in monotonic fashion, bounded above for n odd and decrease in monotonic fashion, bounded below for n even