Skip to content
Topos Uranos

Monotonic sequences and the number e

Summary

This lesson proves the monotone convergence theorem: every monotonic and bounded sequence converges, and its limit is the supremum or the infimum of the set of its terms; unbounded monotonic sequences tend to infinity or to minus infinity. It is the first face of the completeness axiom in this unit: it guarantees that a limit exists without knowing its value in advance. With it, the sequences with which Algebra and Geometry I defined the number ee as a supremum, (1+1n)n\left(1 + \frac{1}{n}\right)^n and the sums ∑k=0n1k!\sum_{k=0}^{n} \frac{1}{k!}, converge to ee, with explicit error bounds, and the limit obtained in Calculus I becomes a consistent check. The second half studies recurrences an+1=f(an)a_{n + 1} = f(a_n): if ff is continuous and the sequence converges, its limit is a fixed point of ff; if ff is increasing, the sequence is monotonic, and the theorem decides whether it converges. They are applied to nested roots, to the arithmetic-geometric mean and to the iterates of the Newton-Raphson method, whose convergence turns out to be a case of the theorem.

Learning objectives

  1. Prove the monotone convergence theorem from the completeness axiom, pointing out what the NN depends on, and deduce that a monotonic sequence converges if and only if it is bounded.
  2. Obtain the limits of (1+1n)n\left(1 + \frac{1}{n}\right)^n, of (1+1n)n+1\left(1 + \frac{1}{n}\right)^{n + 1} and of the sums ∑k=0n1k!\sum_{k=0}^{n} \frac{1}{k!} from what Algebra and Geometry I proved about the number ee, with explicit error bounds.
  3. Prove that the limit of a recurrence an+1=f(an)a_{n + 1} = f(a_n) with ff continuous is a fixed point of ff, and that the recurrence is monotonic if ff is increasing.
  4. Study the convergence of specific recurrences according to their initial term, including those given by a decreasing function and those that have no finite limit.

Monotonic sequences

The lesson on sequences and their limit obtained limits by knowing their value in advance: the definition compares each term with the number LL. But many sequences are defined without their limit being known, such as the approximations of the Newton-Raphson method or the sums with which Algebra and Geometry I approximated the number ee. For them a criterion is needed that guarantees convergence without naming the limit. Calculus I already used the completeness axiom in this way: Bolzano’s theorem, Weierstrass’s theorem and the monotone convergence of the Newton-Raphson method obtained a number as the supremum or the infimum of a set. This lesson turns that device into a theorem about sequences.

DefinitionMonotonic sequence

A sequence (an)(a_n) is increasing if an≤an+1a_n \leq a_{n + 1} for every nn, and strictly increasing if an<an+1a_n < a_{n + 1} for every nn; it is decreasing if an≥an+1a_n \geq a_{n + 1} for every nn, and strictly decreasing if an>an+1a_n > a_{n + 1} for every nn. It is monotonic if it is increasing or decreasing.

If (an)(a_n) is increasing, then an≤ama_n \leq a_m whenever n≤mn \leq m: by induction on mm, starting from m=nm = n, because an≤ama_n \leq a_m and am≤am+1a_m \leq a_{m + 1} give an≤am+1a_n \leq a_{m + 1}. Likewise, a decreasing sequence satisfies an≥ama_n \geq a_m if n≤mn \leq m. For example, nn+1\frac{n}{n + 1} is strictly increasing, 1n\frac{1}{n} is strictly decreasing, a constant sequence is both increasing and decreasing, and (−1)n(-1)^n is not monotonic. An increasing sequence is bounded below by its first term, and a decreasing one, above; the question is whether it is bounded on the other side.

TheoremMonotone convergence

If (an)(a_n) is increasing and bounded above, it converges, and its limit is the supremum of the set of its terms. If it is decreasing and bounded below, it converges, and its limit is the infimum of that set.

lim⁡n→∞an=sup⁡{an:n∈N},lim⁡n→∞an=inf⁡{an:n∈N}\lim_{n \to \infty} a_n = \sup\left\{a_n : n \in \mathbb{N}\right\}, \qquad \lim_{n \to \infty} a_n = \inf\left\{a_n : n \in \mathbb{N}\right\}

The completeness axiom provides the candidate, the supremum SS; since S−εS - \varepsilon is not an upper bound, some term exceeds it, and by monotonicity so do all the later ones. The figure follows the increasing sequence 2−32(45)n2 - \frac{3}{2}\left(\frac{4}{5}\right)^n, whose supremum is 22, with the challenge ε=310\varepsilon = \frac{3}{10}, which the term of index 88 is the first to exceed; at the end, the decreasing sequence 12+32(45)n\frac{1}{2} + \frac{3}{2}\left(\frac{4}{5}\right)^n, whose infimum is 12\frac{1}{2}.

Proof

  1. A={an:n∈N},S=sup⁡A,an≤S,n∈NA = \left\{a_n : n \in \mathbb{N}\right\}, \qquad S = \sup A, \qquad \dato{cota}{a_n \leq S}, \quad n \in \mathbb{N}

    Let (an)(a_n) be increasing and bounded above. The set AA of its terms is nonempty and bounded above; by the completeness axiom, from the lesson on number systems, it has a supremum SS, which is an upper bound of AA.

  2. (∃N∈N)(aN>S−ε)\dato{N}{(\exists N \in \mathbb{N})\left(a_N > S - \varepsilon\right)}

    Let ε>0\varepsilon > 0. Since SS is the least of the upper bounds, the number S−εS - \varepsilon, smaller than SS, is not an upper bound: some term exceeds it. Its index NN depends on ε\varepsilon and on the sequence, through SS.

  3. n≥N→S−ε<aN≤an≤S→∣an−S∣<εn \geq N \rightarrow S - \varepsilon < a_N \leq a_n \leq S \rightarrow \resaltar{\abs{a_n - S} < \varepsilon}

    If n≥Nn \geq N, monotonicity gives aN≤ana_N \leq a_n, and the bound from the first move of the proof, an≤Sa_n \leq S. The term lies between S−εS - \varepsilon and SS, at a distance from SS less than ε\varepsilon.

  4. −an≤T→an≥−T,m≤an→T≤−m,an→−T=inf⁡A-a_n \leq T \rightarrow a_n \geq -T, \qquad m \leq a_n \rightarrow T \leq -m, \qquad a_n \to -T = \resaltar{\inf A}

    If (an)(a_n) is decreasing and bounded below by KK, the sequence (−an)(-a_n) is increasing and bounded above by −K-K; by what has just been shown, it converges to the supremum TT of its terms. The number −T-T is a lower bound of the ana_n, and it is the greatest: if mm is a lower bound of the ana_n, then −m-m is an upper bound of the −an-a_n, and T≤−mT \leq -m. Therefore, −T-T is the infimum of the ana_n, and by the algebra of limits, an=−(−an)a_n = -(-a_n) tends to −T-T.

The proof does not compute the limit: the completeness axiom delivers it as a supremum. That is why the theorem serves for sequences whose limit is unknown, and in this lesson it will always be used in the same way: first one proves that the sequence converges, and then one identifies its limit by another argument. Neither of the two hypotheses is superfluous: (−1)n(-1)^n is bounded, is not monotonic and diverges; nn is increasing, is not bounded and does not converge either. The lesson on the limit at infinity proved the corollary on monotonic functions at infinity for a function that is increasing and bounded above on an interval (c,∞)\ioo{c}{\infty}; its proof goes through one-sided limits on an interval and does not apply to the domain N\mathbb{N}, which contains no intervals, although the idea is the same.

CorollaryUnbounded monotonic sequences

If (an)(a_n) is increasing and not bounded above, then an→∞a_n \to \infty; if it is decreasing and not bounded below, then an→−∞a_n \to -\infty. Consequently, a monotonic sequence converges if and only if it is bounded. Without an upper bound, every number KK is exceeded by some term, and by monotonicity also by all the later ones.

Proof

  1. n≥N→an≥aN>Kn \geq N \rightarrow a_n \geq a_N > \resaltar{K}

    Let KK be real. Since KK is not an upper bound, there is a natural number NN with aN>Ka_N > K, and for n≥Nn \geq N, monotonicity gives an≥aNa_n \geq a_N. The decreasing case reduces to this one with the sequence (−an)(-a_n), which is increasing and not bounded above.

  2. ∣an∣≤K→(∃L)(an→L),(∃L)(an→L)→∣an∣≤K\abs{a_n} \leq K \rightarrow (\exists L)\left(\resaltar{a_n \to L}\right), \qquad (\exists L)\left(a_n \to L\right) \rightarrow \abs{a_n} \leq K

    If a monotonic sequence is bounded, it converges, by the monotone convergence theorem. If it is not, it does not converge, by the theorem that every convergent sequence is bounded, from the lesson on sequences and their limit.