Sequences and their limits

A sequence is an infinite list of real numbers \(a_1, a_2, a_3, \dots\). Formally it is a function \(a : \mathbb{N} \to \mathbb{R}\), and we write \(a_n\) for its value at \(n\) and \((a_n)\) for the whole sequence. Sequences are the simplest setting for the idea of a limit, and almost every later notion in this course, including continuity, the derivative, series and the integral, can be expressed through limits of sequences. This lesson gives the definition of convergence, proves that limits are unique, and develops the algebraic rules that let us compute limits without returning to epsilons every time.

The definition

Definition. A sequence \((a_n)\) converges to a real number \(L\) if for every \(\varepsilon > 0\) there is a natural number \(N\) such that \(|a_n - L| < \varepsilon\) for all \(n \ge N\). We write \(\lim_{n \to \infty} a_n = L\) or \(a_n \to L\), and call \(L\) the limit. A sequence that converges to some \(L\) is convergent; otherwise it is divergent.

In symbols, \(a_n \to L\) means \(\forall \varepsilon > 0 \; \exists N \in \mathbb{N} \; \forall n \ge N : |a_n - L| < \varepsilon\). The inequality \(|a_n - L| < \varepsilon\) says that \(a_n\) lies in the open interval \((L - \varepsilon, L + \varepsilon)\), called the \(\varepsilon\)-neighborhood of \(L\). So convergence says: every neighborhood of \(L\), however small, contains all but finitely many terms of the sequence.

Negating the definition, as in MATH-228, tells us what it means for \(L\) not to be the limit: there is some \(\varepsilon > 0\) such that for every \(N\) there is an \(n \ge N\) with \(|a_n - L| \ge \varepsilon\). In words, infinitely many terms stay at least \(\varepsilon\) away from \(L\).

Proving limits from the definition

Divergence can also be proved from the definition. The sequence \(a_n = (-1)^n\) does not converge. Suppose it converged to \(L\). Take \(\varepsilon = 1\). Then there is \(N\) with \(|a_n - L| < 1\) for all \(n \ge N\). Taking an even \(n \ge N\) and an odd \(n \ge N\) gives \(|1 - L| < 1\) and \(|-1 - L| < 1\), so by the triangle inequality \(2 = |1 - (-1)| \le |1 - L| + |L - (-1)| < 2\), a contradiction. \(\blacksquare\)

Uniqueness and boundedness

Theorem. A sequence has at most one limit.

Proof. Suppose \(a_n \to L\) and \(a_n \to M\) with \(L \ne M\). Let \(\varepsilon = \frac{|L - M|}{2} > 0\). There are \(N_1\) and \(N_2\) with \(|a_n - L| < \varepsilon\) for \(n \ge N_1\) and \(|a_n - M| < \varepsilon\) for \(n \ge N_2\). For \(n = \max(N_1, N_2)\), \(|L - M| \le |L - a_n| + |a_n - M| < 2\varepsilon = |L - M|\), a contradiction. \(\blacksquare\)

Taking the maximum of several thresholds, as here, is a step you will write constantly. If finitely many conditions each hold from some point on, they all hold from the largest of those points on.

Definition. A sequence is bounded if there is \(M > 0\) with \(|a_n| \le M\) for all \(n\).

Theorem. Every convergent sequence is bounded.

Proof. Let \(a_n \to L\). With \(\varepsilon = 1\) there is \(N\) such that \(|a_n - L| < 1\), and hence \(|a_n| < |L| + 1\), for \(n \ge N\). Only finitely many terms come before \(N\). Let \(M = \max(|a_1|, \dots, |a_{N-1}|, |L| + 1)\). Then \(|a_n| \le M\) for every \(n\). \(\blacksquare\)

The converse is false: \((-1)^n\) is bounded but divergent. Lesson 5 shows that a weaker converse holds: every bounded sequence has a convergent subsequence.

The algebra of limits

Theorem (limit laws). Suppose \(a_n \to a\) and \(b_n \to b\). Then

• \(a_n + b_n \to a + b\);

• \(c\,a_n \to c\,a\) for every constant \(c\);

• \(a_n b_n \to ab\);

• if \(b \ne 0\) and \(b_n \ne 0\) for all \(n\), then \(\frac{a_n}{b_n} \to \frac{a}{b}\).

Proof of the sum rule. Let \(\varepsilon > 0\). Choose \(N_1\) with \(|a_n - a| < \frac{\varepsilon}{2}\) for \(n \ge N_1\), and \(N_2\) with \(|b_n - b| < \frac{\varepsilon}{2}\) for \(n \ge N_2\). For \(n \ge \max(N_1, N_2)\), \(|(a_n + b_n) - (a + b)| \le |a_n - a| + |b_n - b| < \varepsilon\). \(\blacksquare\)

Proof of the product rule. The trick is to add and subtract a cross term:

\[a_n b_n - ab = a_n (b_n - b) + b(a_n - a).\]

Since \((a_n)\) converges it is bounded, say \(|a_n| \le M\) with \(M > 0\). Let \(\varepsilon > 0\). Choose \(N_1\) with \(|b_n - b| < \frac{\varepsilon}{2M}\) for \(n \ge N_1\), and \(N_2\) with \(|a_n - a| < \frac{\varepsilon}{2(|b| + 1)}\) for \(n \ge N_2\). For \(n \ge \max(N_1, N_2)\),

\[|a_n b_n - ab| \le |a_n|\,|b_n - b| + |b|\,|a_n - a| < M \cdot \frac{\varepsilon}{2M} + |b| \cdot \frac{\varepsilon}{2(|b| + 1)} < \varepsilon.\]

We used \(|b| + 1\) rather than \(|b|\) to avoid dividing by zero when \(b = 0\). \(\blacksquare\)

Proof of the quotient rule. It suffices to show \(\frac{1}{b_n} \to \frac{1}{b}\) and then use the product rule. First we keep \(b_n\) away from 0: with \(\varepsilon = \frac{|b|}{2}\) there is \(N_1\) such that \(|b_n - b| < \frac{|b|}{2}\), and hence \(|b_n| > \frac{|b|}{2}\), for \(n \ge N_1\). Then for \(n \ge N_1\),

\[\Big|\frac{1}{b_n} - \frac{1}{b}\Big| = \frac{|b - b_n|}{|b_n|\,|b|} < \frac{2}{|b|^2}\,|b_n - b|.\]

Given \(\varepsilon > 0\) choose \(N_2\) with \(|b_n - b| < \frac{|b|^2 \varepsilon}{2}\) for \(n \ge N_2\), and take \(N = \max(N_1, N_2)\). \(\blacksquare\)

With these rules we can find limits like \(\frac{3n^2 + 1}{n^2 + 2}\) quickly: divide top and bottom by \(n^2\) to get \(\frac{3 + 1/n^2}{1 + 2/n^2}\), and since \(\frac{1}{n^2} \to 0\) the limit is \(\frac{3 + 0}{1 + 0} = 3\). The epsilon proof is still there, hidden inside the limit laws.

Limits and inequalities

Theorem (order limit theorem). Suppose \(a_n \to a\) and \(b_n \to b\). If \(a_n \le b_n\) for all \(n\) (or for all \(n\) from some point on), then \(a \le b\).

Proof. Suppose \(a > b\) and let \(\varepsilon = \frac{a - b}{2}\). For large \(n\), \(a_n > a - \varepsilon = \frac{a + b}{2}\) and \(b_n < b + \varepsilon = \frac{a + b}{2}\), so \(b_n < a_n\), a contradiction. \(\blacksquare\)

Strict inequalities are not preserved: \(\frac{1}{n} > 0\) for every \(n\), but the limit is 0, not positive. In general, if \(a_n < b_n\) for all \(n\), we can conclude only \(a \le b\).

Theorem (squeeze theorem). If \(a_n \le x_n \le b_n\) for all \(n\) and \(a_n \to L\), \(b_n \to L\), then \(x_n \to L\).

Proof. Let \(\varepsilon > 0\). For large \(n\), \(L - \varepsilon < a_n\) and \(b_n < L + \varepsilon\), so \(L - \varepsilon < x_n < L + \varepsilon\). \(\blacksquare\)

Some standard limits

A few limits are used so often that they are worth proving once.

• If \(|r| < 1\) then \(r^n \to 0\). Proof for \(0 < r < 1\): write \(\frac{1}{r} = 1 + h\) with \(h > 0\). By Bernoulli's inequality \((1 + h)^n \ge 1 + nh\), proved by induction in MATH-228, so \(0 < r^n \le \frac{1}{1 + nh} < \frac{1}{nh}\), which tends to 0. For negative \(r\) use \(|r^n| = |r|^n\).

• If \(c > 0\) then \(c^{1/n} \to 1\). For \(c > 1\), write \(c^{1/n} = 1 + d_n\) with \(d_n > 0\); Bernoulli gives \(c = (1 + d_n)^n \ge 1 + n d_n\), so \(0 < d_n \le \frac{c - 1}{n}\).

• \(n^{1/n} \to 1\). Write \(n^{1/n} = 1 + d_n\). The binomial theorem gives \(n = (1 + d_n)^n \ge \frac{n(n - 1)}{2} d_n^2\) for \(n \ge 2\), so \(d_n^2 \le \frac{2}{n - 1}\) and \(d_n \to 0\).

• For every fixed \(k\) and every \(r > 1\), \(\frac{n^k}{r^n} \to 0\): exponentials beat polynomials. This follows from the ratio test in lesson 6.

import math

def first_N(a, L, eps, start=1, limit=10**7):
    """Smallest N such that |a(n) - L| < eps for every n from N up to a search bound."""
    last_bad = 0
    for n in range(start, limit):
        if abs(a(n) - L) >= eps:
            last_bad = n
        elif n > 4 * max(last_bad, 1) + 1000:
            break
    return last_bad + 1

seqs = {
    "(3n^2+1)/(n^2+2) -> 3": (lambda n: (3*n*n + 1) / (n*n + 2), 3.0),
    "sqrt(n+1)-sqrt(n) -> 0": (lambda n: math.sqrt(n + 1) - math.sqrt(n), 0.0),
    "n^(1/n) -> 1":           (lambda n: n ** (1 / n), 1.0),
}
for name, (a, L) in seqs.items():
    row = [first_N(a, L, eps) for eps in (0.1, 0.01, 0.001)]
    print(f"{name:26s} N for eps = 0.1, 0.01, 0.001: {row}")

(3n^2+1)/(n^2+2) -> 3      N for eps = 0.1, 0.01, 0.001: [7, 23, 71]
sqrt(n+1)-sqrt(n) -> 0     N for eps = 0.1, 0.01, 0.001: [25, 2500, 250000]
n^(1/n) -> 1               N for eps = 0.1, 0.01, 0.001: [39, 652, 9124]

The table shows how different sequences behave. For \(\frac{3n^2 + 1}{n^2 + 2}\), \(N\) grows like \(\varepsilon^{-1/2}\); for \(\sqrt{n + 1} - \sqrt{n}\) it grows like \(\varepsilon^{-2}\); and \(n^{1/n}\) converges very slowly, so for small \(\varepsilon\) we need enormous \(N\). Our proofs used cruder bounds, such as \(\frac{5}{n}\), that give larger \(N\) than necessary. That is fine: a proof needs some \(N\), not the best one.

Divergence to infinity

Definition. We say \(a_n \to \infty\) if for every \(M\) there is \(N\) with \(a_n > M\) for all \(n \ge N\). Similarly \(a_n \to -\infty\). Such sequences are still called divergent, because \(\infty\) is not a real number, but the notation records how they diverge. For example \(n^2 \to \infty\) and \(\sqrt{n} \to \infty\), while \((-1)^n n\) diverges but does not tend to \(\infty\) or \(-\infty\).

Changing finitely many terms

Convergence depends only on the tail of a sequence. If two sequences \((a_n)\) and \((b_n)\) agree for all \(n \ge K\), then either both converge to the same limit or both diverge. Proof: if \(a_n \to L\) with threshold \(N\) for a given \(\varepsilon\), then \(b_n\) satisfies the same inequality for \(n \ge \max(N, K)\). In particular, changing, inserting or deleting finitely many terms never affects convergence or the value of the limit. This is why we can say 'for \(n\) large enough' in proofs and ignore the first few terms, and why statements such as the order limit theorem only need the inequality to hold from some point on.

A related fact is that shifting the index does not matter: \(a_n \to L\) if and only if \(a_{n+1} \to L\). We used this in lesson 5's recursions, where the limit of \(a_{n+1}\) is needed to take limits on both sides of \(a_{n+1} = f(a_n)\).