Proof or Counter-example

x_n - x_(n-1) = 1/n
x_1 = 1

Then lim(x_n - x_(n-1), n -> inf) == 0.
We can write x_n as

x_n = sum(1/k, k=1..n)

However, lim(x_n, n -> inf) = infinity.


I would prove the original assignment by demonstrating that 1 <= F_(n+1) / F_n < 2, which is easy to do.

fibbonacci numbers are defined as F_n = F_n-1 + F_n-2

then you have |F_n - F_n-1| = |F_n-2|
as all Fibbonacci numbers are positives, F_n > F_n-1 > F_n-2 > ... > 1
as that is true for all n-2 >= 2
lim (n->infinity) |F_n - F_n-1| > 1 > 0...

the limit does not exists...

Quote:

Original post by Mawww fibbonacci numbers are defined as F_n = F_n-1 + F_n-2 then you have |F_n - F_n-1| = |F_n-2| as all Fibbonacci numbers are positives, F_n > F_n-1 > F_n-2 > ... > 1 as that is true for all n-2 >= 2 lim (n->infinity) |F_n - F_n-1| > 1 > 0... the limit does not exists...

Yes, but what is asked is the limit of F_(n+1) / F_n, not F_(n+1) - F_n.

oh sorry. I red to fast.

Try proving that a <= F_(n+1)/F_(n) <= b, for some a,b.

F_(n+1)/F_(n) =
(F_(n)+F_(n-1))/F_(n) =
F_(n)/F_(n)+F_(n-1)/F_(n) =
1+F_(n-1)/F_(n).

It is clear that 0 < F_(n-1)/F_(n) <= 1 since F_(n-1)<=F_(n), so we also know that 1 <= 1+F_(n-1)/F_(n) <= 2. Thus, F_(n+1)/F_(n) is bounded from above and below, and the limit exists (you may want to mention that the sequence converges).

Quote:

Original post by Nychold Yes, this is for a homework assignment, so I'll be upfront about it. I'm not looking for an answer. The assignment is to prove the limit as n goes to infinity of F_(n+1) / F_n exists (where F_n is the nth Fibonacci number.) I already have a proof for this, which depends on my hypothesis that: The limit as n goes to infinity of x_n exists if the limit as n approaches infinity of |x_n - x_(n-1)| = 0, and x_n is bounded (above and below).

This is not generally true. The following is a counterexample:

x_n = sin(1+1/2+1/3+...+1/n).

This sequence is bounded by 1 and -1, the difference between terms tends to 0, but the sequence is divergent.

proving bounds is not quite enough, you also need to prove it is strictly increasing or strictly decreasing through the bounds you prove. elusive nailed it though, nice one.

Tim

Quote:

Original post by eleusive Try proving that a <= F_(n+1)/F_(n) <= b, for some a,b. F_(n+1)/F_(n) = (F_(n)+F_(n-1))/F_(n) = F_(n)/F_(n)+F_(n-1)/F_(n) = 1+F_(n-1)/F_(n). It is clear that 0 < F_(n-1)/F_(n) <= 1 since F_(n-1)<=F_(n), so we also know that 1 <= 1+F_(n-1)/F_(n) <= 2. Thus, F_(n+1)/F_(n) is bounded from above and below, and the limit exists (you may want to mention that the sequence converges).

Yeah, but that's the problem. Just because something's bounded does not mean it converges. The converse is true though. And it does not increase nor decrease. In fact, it oscillates around 1.6180... And I already have this in my proof, but I still need to figure out how to prove it converges.

EDIT: Also, the professor said it was almost impossible to do this without using the fact that F_(n+1) * F_(n-1) = (F_n)^2 + (-1)^(n+1), and if you take two the difference of consecutive terms of the sequence:

                                  2 F         F       F   * F    - F  n+1       n       n-1   n+1    n------ - ------ = ------------------  F       F            F  * F   n       n-1          n    n-1

And it looks like this is the route to persue. Still, I agree with NotAnAnonymousPoster. My hypothesis doesn't work at all. Which leaves me even more confused.

Hi,

this is not a proof, but I think it is pretty [smile]

You want to find the limit of F_n+1/F_n as n approaches infinity. Suppose that limit exists and call it L. Suppose that 0 < L < infinity.

We can write F_n+1/F_n as 1 + F_n-1/F_n. But the limit of F_n-1/F_n as n approaches infinity will be 1/L. So we get the following equation

L = 1 + 1/L

or

L² - L - 1 = 0.

The roots of this equation are

L = (1 ± sqrt(5)) / 2

Since, L > 0,

L = (1 + sqrt(5)) / 2,

which is also the golden ratio.


-Josh

Hopefully this isn't giving too much away, but if you take the sequence of even terms and the sequence of odd terms seperately, you can show that one of these sequences is monotonically increasing and one of the sequences is monotonically decreasing. As you stated, the sequence is bounded both below and above, so both these subsequences are convergent. This in itself is not enough to prove that the original sequence is convergent though.

First you must show that each of these subsequences converge to the same limit (This is necissary, but not sufficient for convergence). Next if you show that the 'upper' sequence is always >= the 'lower' sequence, you can use the squeeze principal to show convergence of the original sequence.

As stated by another poster, the limit is indeed the golden ratio.

Quote:

Original post by Krumble First you must show that each of these subsequences converge to the same limit (This is necissary, but not sufficient for convergence).

It is necessary and sufficient. Any sequence consisting of two subsequences convergent with a common limit also converges to that limit.

ETA: Nychold, if you haven't solved this problem yet, you are at least on the right track. The identity given to you by your professor combined with the identity you provided allows you to show that the even and odd subsequences are monotonic, and it will also allow you to show that they have a common limit. If you need to prove the identity given by your professor, use mathematical induction.

Let's find all the sequences that satisfy Z(n+2)=Z(n+1)+Z(n). We know that multiplying a sequence of that type by a constant yields another sequence of that type, and that the sum of two sequences of that type yields another sequence of that type. The sequences with that property form, therefore, a vector space. You can start with whatever two terms you want, and they determine the whole sequence. Therefore, the sequence that starts with {1,0,...} and the sequence that starts with {0,1,...} form a base of the vector space. If we find two sequences that satisfy the recursive formula and that are not proportional to each other, they too must be a base of this 2-dimensional vector space.

We try with sequences of the form Z(n)=L^n, where L is a real number (for other recursive formulas you might need to do this with complex numbers). Let's see what the recursion formula tells us about L:

Z(n+2)=Z(n+1)+Z(n) => L^(n+2)=L^(n+1)+L^n => L^2=L+1 => L^2-L-1=0

This last equation has two roots: (1+sqrt(5))/2 and (1-sqrt(5))/2. Now we must be able to express Fibonacci as a linear combination of these two sequences, since they form a base. You can do that (you'll get coefficients like +1/sqrt(5) and -1/sqrt(5), I believe). In any case, Fibonacci is the sum of two geometric sequences, one of which goes to zero, which will make the limit of the ratio of two consecutive terms be exactly the "big" L: (1+sqrt(5))/2.

The last few steps are not fully formalized here, but hey, it's your homework. :)

Hmm, this might actually be better considering the path I've already taken:

"We say x_n is a Cauchy sequence if, given any e>0, we can find an N such that, for any m>N and any n>N, |x_m - x_n| < e

...

5.19 Theorem

Every Cauchy sequence converges."

So I guess I was pretty close to being right. I guess all I have to do is prove the sequence is a Cauchy sequence (which hopefully is easy enough to do), and then it converges by the theorem.

But thanks for everyone's help. (And I know I should've read ahead in the book, but he's a stickler for only using what we've talked about.)

Quote:

Original post by alvaro Let's find all the sequences that satisfy Z(n+2)=Z(n+1)+Z(n). We know that multiplying a sequence of that type by a constant yields another sequence of that type, and that the sum of two sequences of that type yields another sequence of that type. The sequences with that property form, therefore, a vector space. You can start with whatever two terms you want, and they determine the whole sequence. Therefore, the sequence that starts with {1,0,...} and the sequence that starts with {0,1,...} form a base of the vector space. If we find two sequences that satisfy the recursive formula and that are not proportional to each other, they too must be a base of this 2-dimensional vector space. We try with sequences of the form Z(n)=L^n, where L is a real number (for other recursive formulas you might need to do this with complex numbers). Let's see what the recursion formula tells us about L: Z(n+2)=Z(n+1)+Z(n) => L^(n+2)=L^(n+1)+L^n => L^2=L+1 => L^2-L-1=0 This last equation has two roots: (1+sqrt(5))/2 and (1-sqrt(5))/2. Now we must be able to express Fibonacci as a linear combination of these two sequences, since they form a base. You can do that (you'll get coefficients like +1/sqrt(5) and -1/sqrt(5), I believe). In any case, Fibonacci is the sum of two geometric sequences, one of which goes to zero, which will make the limit of the ratio of two consecutive terms be exactly the "big" L: (1+sqrt(5))/2. The last few steps are not fully formalized here, but hey, it's your homework. :)

Very cool solution.

Quote:

Original post by NotAnAnonymousPoster Quote: Original post by Krumble First you must show that each of these subsequences converge to the same limit (This is necissary, but not sufficient for convergence). It is necessary and sufficient. Any sequence consisting of two subsequences convergent with a common limit also converges to that limit.

a_n = (-1)^n is divergent. Take the even terms and the odd terms as seperate subsequences. Each of those are convergent to different limits.

Or take the even terms, and the terms that are powers of 2. Each of these sequences converges to the same limit, but the original sequence is divergent.

If you mean two (or more, but finite) subsequences that comprise the entire original sequence at infinite and they all converge to the same limit, I'd believe you :)

Quote:

Original post by Krumble If you mean two (or more, but finite) subsequences that comprise the entire original sequence at infinite and they all converge to the same limit, I'd believe you :)

That is what I meant, and I think that meaning is captured adequately by consisting of. Also check the context. You originally said:

Quote:

Original post by Krumble ...if you take the sequence of even terms and the sequence of odd terms seperately, [...] ...you must show that each of these subsequences converge to the same limit (This is necissary, but not sufficient for convergence)

Here, it certainly is necessary and sufficient for convergence, since the two subsequences are the even and odd subsequences. The rule I gave was a generalisation of this.

Quote:

Original post by Anonymous Poster Since your homework is probably already turned in, I'll post an answer. F(n) = nth fibonacci number. Does limit exist as n->infininty of F(n+1)/F(n)? Let S(n)=F(n+1)/F(n). Then S(n)=F(n+1)/F(n)=(F(n)+F(n-1))/F(n)=1+F(n-1)/F(n)=1+1/(S(n-1)), so (S(n)-1) * S(n-1)=1 for all n. (eq 1) Let x = lim as n->infinity of F(n+1)/F(n), which may be infinity (all F(n)>0 and F(n) increasing ensures x>=1).

Even if you show that F(n+1)/F(n) is bounded, how do you know that the limit x exists? That was the original problem.

Quote:

Taking limit of eq 1 as n->infinity gives (x-1)*x=1, thus the limit exists since x must be finite. In fact, the roots of x^2-x-1 are (the golden mean) (1+sqrt(5))/2 and (1-sqrt(5))/2. Since x>=1, we actually get the (well known) limit to be (1+sqrt(5))/2 Chris Lomont www.lomont.org