Thread: Rate of convergence

When dealing with series, is there any sense of 'rate of change' or 'rate of convergence/divergence'? I know different series converge or diverge at different rates (for example, it can be said that the harmonic series converges very very slowly), so I'm just wondering if there's a way to kind of put a number on how quickly it does so.

If you have a convergent series, s is the sum of the series, and s_N is the Nth partial sum, then you can try to find a good bound for the error |s-s_N|. The techniques for doing so include comparing the error to an integral, using patterns in the signs of the terms of the series, or exactly evaluating the series. So, for example, you could ask how fast the series



converges. You can bound the error by the integral



So the function 1/N gives you an idea how fast this converges.

This sort of reasoning also works for series that diverge. Here, however, you hope to find a function asymptotic to your series--namely, you want to find a nice function f(N) so that |s_N-f(N)| grows smaller than f(N) does. For example, you spoke of the harmonic series



We can approximate the partial sums by certain integrals. For example, we have the inequalities



and



So we see that ln(N) ≤ ln(N+1) ≤ s_N ≤ 1+ln(N), and we have |s_N-ln(N)| ≤ 1 for all values of N. Thus s_N grows like ln(N).

Interesting... I don't think I understand the work in your last example, but I think I get the idea of s_N growing like ln(N), and in your first example, that 1/N describes how the series converges. So considering the graph of 1/x, can it be said that the series converges more slowly as n approaches infinity?

Would the the sum from 1 to infinity of n (1+2+3+...+) grow like x²/2 by any chance?

Originally Posted by Chemboy

Interesting... I don't think I understand the work in your last example

Yeah, I left out details. The basic idea is this. For the lower bound on 1+...+1/N, look at the function f(x) = 1/x on the interval from 1 to N+1. You can break it up into N disjoint subintervals of length 1, each having integer endpoints. On the interval from m to m+1, 1 ≤ m ≤ N, we have that 1/m is bigger than f(x), and so the integral from m to m+1 of 1/x is less than 1/m. Adding up these inequalities, we obtain the lower bound. The upper bound is similar--we break up the interval from 1 to N into N-1 disjoint subintervals of length 1. On the interval from m-1 to m, 2 ≤ m ≤ N, we have that 1/x is greater than 1/m. Adding up the inequalities, we have that 1/2+1/3+...+1/N is less than the integral from 1 to N. Adding one to both sides gives us the upper bound.

in your first example, that 1/N describes how the series converges. So considering the graph of 1/x, can it be said that the series converges more slowly as n approaches infinity?

Yes, the series does converge more slowly as n approach infinity, but this will have to be true for any convergent series. So this isn't really a useful mathematical fact. What is useful is comparing rates of convergence. So I can think of 1/n as being a certain rate of convergence, 1/n² as being faster, 1/ln(n) as being slower, etc.

Would the the sum from 1 to infinity of n (1+2+3+...+) grow like x²/2 by any chance?

Indeed. You can show this via integrals as I do for the harmonic series, or you can in fact show this by an exact formula. Indeed, we have:

1+2+3+...+N = N(N+1)/2 = (N²+N)/2

This differs from your estimate by N/2, but N/2 gets really small with respect to N²/2 as N goes to infinity, so we may as well ignore it if we're looking for the "main term" of this sequence's growth.

To see the above equality, we can use induction. It's true for N = 1. If it's true for some N, then:

1+2+...+N+(N+1) = N(N+1)/2+(N+1) = (N+1)(N/2+1) = (N+1)(N+2)/2

And this is precisely the statement for N+1.

There is a whole host of stuff you can talk about w.r.t the convergence rate of sequences - do you know anything about big O notation Chem?