Chapter IV · Limits of functions of a positive integral variable

Monotone sequences

§§69–70 35 min

An increasing sequence either tends to a limit or to plus infinity, and it tends to a limit exactly when it is bounded above; this proves convergence without knowing the limit.

Why this matters

Every limit proved so far was proved by guessing the limit first and then checking the definition, which mentions ll. But often we cannot guess. Does 1+14+19+⋯+1/n21 + \tfrac14 + \tfrac19 + \dots + 1/n^2 tend to a limit? If so, what is it? §§69–70 gives the first tool that answers the first question without the second: an increasing sequence that is bounded above must converge. Its proof is where the completeness of the real numbers (Dedekind’s theorem of §17) enters the theory of limits, and it is behind ee, log⁡x\log x and much of Chapter VIII.

The idea

An increasing sequence only ever moves up (or stays put). So for each number ξ\xi only two things can happen: either some term reaches ξ\xi, and then every later term stays at or above it; or no term ever reaches ξ\xi. Call the numbers of the first kind LL and those of the second kind RR. Everything in LL lies below everything in RR.

  • If RR is empty, every number is eventually passed for good: the sequence tends to +∞+\infty.
  • If RR is not empty, LL and RR split the real line into a lower and an upper part, a Dedekind section. The section has a dividing number aa, and the terms must crowd up against it.
Explore Reached or never reached

Try this. Start with 1+14+⋯+1/n21 + \tfrac14 + \dots + 1/n^2. Move ξ\xi up slowly and find (roughly) where “reached” turns into “never reached”. Then switch to the harmonic sum 1+12+⋯+1/n1 + \tfrac12 + \dots + 1/n and push ξ\xi to 88, 1010, 1212.

ϕ(n)=∑k=1n1k2\phi(n) = \sum_{k=1}^n \frac{1}{k^2}
nφ(n)
  • ξ (move with the slider)
  • terms ≥ ξ
ξ=1.6\xi = 1.6 is reached: ϕ(22)≥ξ\phi(22) \ge \xi, and since the sequence never decreases, every later term is ≥ξ\ge \xi too. So ξ\xi belongs to the lower class LL. Bounded by 2 (see the exercise), so it converges; nothing in this chapter tells us the limit is π²/6.
What to notice

For a bounded increasing sequence, the change happens at one number aa; only afterwards does the toggle reveal it. You found aa without a formula, which is the point of the theorem. The harmonic sum reaches every ξ\xi you try, but slowly: ξ=10\xi = 10 is first reached at n=12 367n = 12\,367. No picture of finitely many terms could tell you that it is unbounded; that needs a proof (<Sec n={77} />).

Precise statements

Definition Increasing and decreasing sequences Hardy: §69

ϕ(n)\phi(n) increases steadily (is an increasing function of nn) if ϕ(n+1)≥ϕ(n)\phi(n+1) \ge \phi(n) for every nn. It is strictly increasing if ϕ(n+1)>ϕ(n)\phi(n+1) > \phi(n) for every nn. Decreasing and strictly decreasing are defined with the inequalities reversed.

Equal consecutive values are allowed: 2n+(−1)n2n + (-1)^n takes the values 1,5,5,9,9,…1, 5, 5, 9, 9, \dots and increases steadily. Since −ϕ(n)-\phi(n) increases exactly when ϕ(n)\phi(n) decreases, every result for increasing sequences gives one for decreasing sequences by a change of sign.

Theorem Monotone sequences Hardy: Theorem, §69

If ϕ(n)\phi(n) increases steadily, then either ϕ(n)\phi(n) tends to a limit or ϕ(n)→+∞\phi(n) \to +\infty.

So an increasing sequence never oscillates: of the five possible behaviours, only two remain.

Corollary Hardy: Cor. 1, §69

An increasing sequence tends to a limit if there is a number KK with ϕ(n)<K\phi(n) < K for every nn, and tends to +∞+\infty if there is no such KK.

Corollary Hardy: Cor. 2, §69

If ϕ(n)\phi(n) increases steadily and ϕ(n)<K\phi(n) < K for every nn, then ϕ(n)\phi(n) tends to a limit a≤Ka \le K.

Corollary Hardy: Cor. 3, §69

If ϕ(n)\phi(n) increases steadily and tends to a limit aa, then ϕ(n)≤a\phi(n) \le a for every nn.

Theorem Decreasing sequences Hardy: §69

A decreasing sequence tends to a limit or to −∞-\infty; it tends to a limit exactly when it is bounded below, and then every term is at least the limit.

Proofs

Proof Monotone sequences (via Dedekind's theorem)
Strategy

Sort every real number ξ\xi into LL (reached by some term) or RR (never reached). If RR is empty the sequence passes every bound; otherwise (L,R)(L, R) is a section of the reals, and the number aa it defines is the limit.

Define the classes

Put ξ\xi in LL if ϕ(n)≥ξ\phi(n) \ge \xi for some nn, and in RR if ϕ(n)<ξ\phi(n) < \xi for every nn. Each ξ\xi is in exactly one class. Because the sequence increases, if ϕ(m)≥ξ\phi(m) \ge \xi then ϕ(n)≥ξ\phi(n) \ge \xi for every n≥mn \ge m.

If RR is empty: ϕ(n)→+∞\phi(n) \to +\infty

Then every Δ\Delta is in LL (and so is Δ+1\Delta + 1): some ϕ(m)≥Δ+1>Δ\phi(m) \ge \Delta + 1 > \Delta, and then ϕ(n)>Δ\phi(n) > \Delta for all n≥mn \ge m. That is Definition II.

If RR is not empty: a section

LL is not empty either (ϕ(1)∈L\phi(1) \in L). Every member of LL is less than every member of RR: if ξ∈L\xi \in L and η∈R\eta \in R, then ϕ(m)≥ξ\phi(m) \ge \xi for some mm while ϕ(m)<η\phi(m) < \eta. So (L,R)(L, R) is a section of the real numbers, and by Dedekind’s theorem there is a number aa such that every number below aa is in LL and every number above aa is in RR.

The terms are trapped just below aa

Let δ>0\delta > 0. Since a+δ∈Ra + \delta \in R, ϕ(n)<a+δ\phi(n) < a + \delta for every nn; as δ\delta is arbitrary, ϕ(n)≤a\phi(n) \le a for every nn. Since a−12δ∈La - \tfrac12\delta \in L, some ϕ(m)≥a−12δ\phi(m) \ge a - \tfrac12\delta, and then ϕ(n)≥a−12δ>a−δ\phi(n) \ge a - \tfrac12\delta > a - \delta for all n≥mn \ge m.

Conclude

For n≥mn \ge m: a−δ<ϕ(n)≤aa - \delta < \phi(n) \le a, so ∣ϕ(n)−a∣<δ|\phi(n) - a| < \delta. Since δ\delta was arbitrary, ϕ(n)→a\phi(n) \to a.

The corollaries are now short. Cor. 1: if ϕ(n)<K\phi(n) < K for all nn then K∈RK \in R, so RR is not empty and there is a limit; if no such KK exists then RR is empty, so ϕ(n)→+∞\phi(n) \to +\infty. Cor. 3: step 4 showed ϕ(n)≤a\phi(n) \le a for every nn. Cor. 2: K∈RK \in R and every member of RR is at least aa (anything below aa is in LL), so a≤Ka \le K.

Cor. 2 says a≤Ka \le K, not a<Ka < K. The sequence 3−1/n3 - 1/n is below 33 for every nn, and its limit is exactly 33. A strict inequality between the terms and a bound becomes non-strict in the limit; this is a pattern you will see many times. In fact, Hardy notes, the terms of an increasing sequence are all strictly below the limit unless the sequence is eventually constant: if ϕ(m)=a\phi(m) = a then a≤ϕ(n)≤aa \le \phi(n) \le a for all n≥mn \ge m.

Why this matters: convergence without the limit

§70 spells out the gain. The definition of a limit is a test for a given ll: it can confirm ϕ(n)→l\phi(n) \to l, or (by contradiction) show that no ll works, as for (−1)n(-1)^n. It cannot tell us that some unknown ll exists. The monotone theorem can. Hardy’s motivating example is (1+1/n)n(1 + 1/n)^n: it is not at all obvious what its limit should be, but in The limit of (1+1/n)n(1 + 1/n)^n we show it is increasing and below 33, and its limit becomes the definition of the number ee.

Worked examples and exercises

Exercise A sum with an unknown limit ●●○ Hardy: §69

Let ϕ(n)=1+122+132+⋯+1n2\phi(n) = 1 + \dfrac{1}{2^2} + \dfrac{1}{3^2} + \dots + \dfrac{1}{n^2}. Show that ϕ(n)\phi(n) tends to a limit, and that the limit is at most 22.

Hint
For k≥2k \ge 2, 1k2<1k(k−1)=1k−1−1k\dfrac{1}{k^2} < \dfrac{1}{k(k-1)} = \dfrac{1}{k-1} - \dfrac1k.

Solution

ϕ(n+1)−ϕ(n)=1/(n+1)2>0\phi(n+1) - \phi(n) = 1/(n+1)^2 > 0, so the sequence increases. For n≥2n \ge 2,

ϕ(n)<1+∑k=2n(1k−1−1k)=1+(1−1n)=2−1n<2,\phi(n) < 1 + \sum_{k=2}^n \left(\frac{1}{k-1} - \frac1k\right) = 1 + \left(1 - \frac1n\right) = 2 - \frac1n < 2,

because the sum telescopes; and ϕ(1)=1<2\phi(1) = 1 < 2. By Cor. 2 the sequence tends to a limit a≤2a \le 2. (Euler showed that a=π2/6≈1.645a = \pi^2/6 \approx 1.645, but the theorem needs no such knowledge.)

Exercise Nested square roots ●●○ Hardy: §69

Let x1=2x_1 = \sqrt2 and xn+1=2+xnx_{n+1} = \sqrt{2 + x_n}. Show that xnx_n increases and is less than 22, and find its limit.

Hint
Use induction for both claims. For the limit, let n→∞n \to \infty in xn+12=2+xnx_{n+1}^2 = 2 + x_n.

Solution

Bounded: x1<2x_1 < 2, and if xn<2x_n < 2 then xn+1=2+xn<4=2x_{n+1} = \sqrt{2 + x_n} < \sqrt4 = 2. Increasing: xn+12−xn2=2+xn−xn2=(2−xn)(1+xn)>0x_{n+1}^2 - x_n^2 = 2 + x_n - x_n^2 = (2 - x_n)(1 + x_n) > 0, since 0<xn<20 < x_n < 2; both are positive, so xn+1>xnx_{n+1} > x_n. By Cor. 2, xn→lx_n \to l with 2<l≤2\sqrt2 < l \le 2. Now xn+12=2+xnx_{n+1}^2 = 2 + x_n. The left side tends to l2l^2 (a shift of xnx_n, then Theorem II), the right to 2+l2 + l. So l2=l+2l^2 = l + 2, that is (l−2)(l+1)=0(l - 2)(l + 1) = 0, and since l>0l > 0, l=2l = 2.

Exercise Strict and non-strict ●○○ Hardy: §69, Cor. 3

An increasing sequence satisfies ϕ(n)<5\phi(n) < 5 for every nn. Which of these must be true? (a) ϕ(n)\phi(n) tends to a limit; (b) the limit is less than 55; (c) the limit is at most 55; (d) every term is less than the limit.

Solution

(a) Yes, by Cor. 1. (b) No: 5−1/n5 - 1/n has limit 55. (c) Yes, by Cor. 2. (d) Not necessarily: a sequence that is constant from some point on (such as 1,2,3,3,3,…1, 2, 3, 3, 3, \dots) equals its limit there. Hardy’s remark shows that (d) fails only for such sequences; Cor. 3 guarantees ϕ(n)≤a\phi(n) \le a in every case.

Exercise The decreasing case ●○○ Hardy: §69

Prove the theorem on decreasing sequences from the theorem on increasing ones.

Solution

If ϕ\phi decreases, ψ=−ϕ\psi = -\phi increases. So ψ\psi tends to a limit bb or to +∞+\infty, that is, ϕ\phi tends to −b-b or to −∞-\infty. ψ\psi is bounded above by KK exactly when ϕ\phi is bounded below by −K-K, which gives the criterion. And ψ(n)≤b\psi(n) \le b for every nn (Cor. 3) means ϕ(n)≥−b\phi(n) \ge -b.

Exercise Using the definition to rule out a limit ●○○ Hardy: §70

Hardy remarks that the definition can still show indirectly that no limit exists. Show this for ϕ(n)=(−1)n\phi(n) = (-1)^n, and explain why the same idea cannot prove that 1+14+⋯+1/n21 + \tfrac14 + \dots + 1/n^2 has a limit.

Solution

If (−1)n→l(-1)^n \to l, then the even terms show l=1l = 1 and the odd terms show l=−1l = -1 (each subsequence of a convergent sequence has the same limit, or argue with δ=12\delta = \tfrac12 as in Oscillating sequences). Since 1≠−11 \ne -1 there is no limit. For the sum of 1/k21/k^2 we cannot use the definition directly, because we do not know which ll to test; a proof by contradiction can rule out candidates, but not produce one. The monotone theorem fills exactly this gap.

Check yourself

Check yourself True or false?

Every bounded sequence tends to a limit.

Why

False: (−1)n(-1)^n is bounded and oscillates. Boundedness is enough only together with monotonicity (or, as in Chapter IV’s later sections, with something else such as Cauchy’s condition).

Check yourself Choose one

An increasing sequence can:

Why

That is the theorem. An increasing sequence is bounded below by ϕ(1)\phi(1), so it cannot tend to −∞-\infty; and the Dedekind argument shows it cannot oscillate.

Check yourself True or false?

ϕ(n)=[n/2]\phi(n) = [n/2] (the integral part of n/2n/2) increases steadily in Hardy’s sense.

Why

True. Its values are 0,1,1,2,2,3,…0, 1, 1, 2, 2, 3, \dots, so ϕ(n+1)≥ϕ(n)\phi(n+1) \ge \phi(n) always, though not strictly. It is unbounded, so it tends to +∞+\infty.

Check yourself Choose one

The terms of 1+12+⋯+1/n1 + \tfrac12 + \dots + 1/n stay below 1515 for the first million values of nn. What follows?

Why

Boundedness is a statement about all nn. The harmonic sums are in fact unbounded and tend to +∞+\infty (§77), although they are below 1515 for n≤106n \le 10^6 and pass 100100 only after about 104310^{43} terms.

Hardy’s language

The great importance of these theorems lies in the fact that they give us … a means of deciding, in a great many cases, whether a given function of n does or does not tend to a limit as n → ∞, without requiring us to be able to guess or otherwise infer beforehand what the limit is.

— G. H. Hardy, §70

Summary

Summary
  • An increasing sequence tends to a limit or to +∞+\infty, never anything else; it converges exactly when it is bounded above.
  • The proof sorts every ξ\xi into “reached” (LL) or “never reached” (RR); if RR is not empty, Dedekind’s theorem supplies the limit as the dividing number.
  • If ϕ(n)<K\phi(n) < K for all nn, the limit is ≤K\le K, not necessarily <K< K; every term is ≤\le the limit.
  • Decreasing sequences behave the same way with signs reversed.
  • The theorem proves that limits exist without naming them, which is how ee and log⁡x\log x will be defined.