Thursday, August 27, 2009

Convergent Sequences

I'm going to explain the math from last night's calculus class here. It shouldn't be too ridiculously hard to follow, if you're interested. I was impressed by our professor's finding of ways to explain it that made a lot of sense, because this is the kind of thing that, if I were reading it in a textbook, I would balk at.

So, a sequence is just some set of numbers that happen in a particular order, for instance, the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, ...

It's not just a set of numbers, because the order matters. The 4th number of the Fibonacci sequence is 3. You could say f(4) = 3 if you wanted to talk about the sequence as a function. You could calculate the nth term of the sequence for any n.

The simple, intuitive definition of what it means for a sequence to "converge" on some value, a, is that, as the sequence goes on, it gets closer and closer to a. But there are a couple of problems that keep this from being a usable definition:

1. Consider a sequence like this:
2, 3/2, 4/3, 5/4, 6/5, 7/6, 8/7, 9/8, 10/9, ...
It seems like it's converging to 1. It's certainly getting closer and closer to 1 as it goes on. But it's also, technically, getting closer and closer to 0. So it's not enough that it gets closer and closer - it also has to get close. This series looks like it's going to get arbitrarily close to 1, which it's not going to do with 0.

2. Consider a sequence like this:
2, 1, -1.9, 1, 1.8, 1, -1.7, 1, 1.6, 1, -1.5, 1, 1.4, 1, -1.3, 1, ...

Again, this sequence is converging to 1, but it doesn't seem like it's getting "closer and closer" to 1. It's oscillating around 1, with the oscillations getting smaller and smaller, but at any given point it might be moving away from 1.

So, let's move towards a more formal definition. If we consider the terms of the sequence as successive approximations of the value to which it is converging, then the question is this - can we get the approximation as good as we want?

That is, for some acceptable level of error (ε), can we find an N such that anything past the Nth term of the sequence is within ε of our value, a? If so, then the series converges to a.

It can't just be proving that some term or other is within ε of a. We might be running a computer program that provides these successive approximations, and we certainly don't want to get a worse estimate if we let the computer run too long.

And we have to be able to do this for any ε someone gives us, as long as it's greater than 0. If you say you want something with 0.00001 of a, I have to be able to say, well, anything past the 2000th value will be that close.

So there you go: convergent sequences with ε (δ comes later).

2 comments:

Edward said...

For the "oscillating" sequence, it looks like, for terms 7, 11, 15...,

f(n)=f(n-4)+0.2

and for terms 5, 9, 13...,

f(n)=f(n-4)-0.2

which diverges. Continuing the sequence, you get:

...-1.3, 1, 1.2, 1, -1.1, 1, 1, 1, -0.9, 1, 0.8, 1, -0.7, 1, 0.6, 1...

The odd terms wind up with arbitrarily high absolute values.

Tam said...

Yeah, that's what I get for just eyeballing the sequence. I mean for them to oscillate but get closer to 1 on both sides as they do, I just didn't bother to come up with a formula to produce that.