Convergence theorems and computational techniques

Recurrent sequences and comparative growth rates

Recurrent sequences u_(n+1) = f(u_n)

Many sequences are defined by a recurrence relation and a continuous function f. If (u_n) converges to l and if f is continuous at l, then by taking the limit as u_(n+1) = f(u_n), we obtain l = f(l): l is a fixed point of f.

Example

Let $u_0 = 1$ and $u_{n+1} = \sqrt{2 + u_n}$ . We show by recurrence that the sequence $(u_n)$ is increasing and bounded above by 2, so it converges to a limit l ≥ 0 such that l = √(2 + l), that is, l² = 2 + l, which implies l² − l − 2 = 0, or (l − 2)(l + 1) = 0. Since l ≥ 0, we conclude that l = 2.

A classic pitfall

Finding a candidate fixed point is not sufficient to prove convergence: one must first establish that the sequence converges (monotonicity and boundedness, or some other argument), and only then identify $l$ via the fixed-point equation. Without prior proof of convergence, the equation l = f(l) may have solutions that are not the actual limit, or indeed there may be no limit at all.

Comparing growth rates

To compare the rates at which sequences tend towards infinity, we use the following hierarchy (a > 0, k an integer):

Sequence	Growth rate
ln(n)^k	slowest
n^a	intermediate
a^n (a > 1)	fast
n!	very fast
n^n	extremely fast

Specifically: ln(n)/n → 0, n^a/a^n → 0 (a > 1), a^n/n! → 0, n!/n^n → 0.

Example of application