Limits, proved

Calculus rests on the statement that a sequence converges to a limit, and so far that statement has been written down, read as a game and negated, but never proved for a single sequence.

The previous lesson supplied what was missing: the completeness axiom, that every nonempty set of reals bounded above has a least upper bound, and from it the Archimedean property, that for every real $x$ some natural number exceeds $x$. This lesson puts the whole course to work on one definition. It proves that particular sequences converge and that others do not, proves the general theorems that let limits be computed without returning to the definition every time, and reaches several theorems that are true in $ℝ$ and false in $\mathbb{Q}$, which is exactly what completeness buys. It ends by carrying the same ideas from sequences to functions, with the $\epsilon$ and $\delta$ definitions of limit and continuity that calculus is built on. Along the way it separates two activities that textbooks tend to blur: finding a proof and writing one.

The tools come from every earlier lesson: quantifiers for the definition, negation for divergence, the triangle inequality and its reverse form from the lesson on direct proof, contradiction for uniqueness, induction for recursive sequences, and the supremum for everything that needs completeness.

The definition, read closely

A sequence of real numbers is a function $a:\mathbb{N}\to ℝ$, written $a_1,a_2,a_3,\dots$ or $(a_n)$, with $\mathbb{N}=\{1,2,3,\dots \}$ as throughout the course. The sequence converges to the real number $L$ when

and then we write $a_n\to L$, or $\underset{n\to \infty }{lim}{a}_n=L$, and call $L$ a limit of the sequence. A sequence that converges to some real number is convergent; one that converges to none is divergent.

The lesson on quantifiers read the definition as a game. A sceptic names a tolerance $\epsilon >0$, as small as they like. A prover answers with a position $N$. The sceptic then picks any term from position $N$ on, and the prover wins if that term lies within $\epsilon$ of $L$. The sequence converges to $L$ when the prover has a winning answer to every tolerance.

Because $\exists N$ comes after $\forall \epsilon$, the position may depend on the tolerance, and for any interesting sequence it must: a smaller $\epsilon$ usually needs a later $N$. Because the last quantifier is $\forall n\ge N$, it is not enough for one term to land close; every term from $N$ on must, so the sequence stays close rather than visiting. The first $N-1$ terms are ignored completely, which is why changing, adding or deleting finitely many terms never changes whether a sequence converges, or to what.

There is a geometric reading too. The inequality $|a_n-L|<\epsilon$ says $L-\epsilon <a_n<L+\epsilon$: the term lies in the open interval of radius $\epsilon$ about $L$. So $a_n\to L$ says that every open interval around $L$, however narrow, contains all the terms from some point on, and only finitely many terms lie outside it. A phrase for "for all $n$ from some point on" is eventually: $a_n\to L$ when, for every $\epsilon >0$, eventually $|a_n-L|<\epsilon$.

The quantifiers also dictate the shape of every convergence proof before any arithmetic is done. The universal $\forall \epsilon >0$ is met by "Let $\epsilon >0$", assuming nothing about it but positivity. The existential $\exists N$ is met by naming an $N$, which may be built from $\epsilon$ but from nothing chosen later. The inner universal is met by "Let $n\ge N$". What remains is to show $|a_n-L|<\epsilon$ using only those facts. An $N$ that works may always be replaced by a larger one, so there is no need to find the smallest; the proof only has to find one.

The first limit: $\frac{1}{n}\to 0$

Theorem. The sequence $a_n=\frac{1}{n}$ converges to $0$.

Proof. Let $\epsilon >0$. By the Archimedean property there is a natural number $N$ with $N>\frac{1}{\epsilon }$. Let $n\ge N$. Then

where the first inequality holds because $n\ge N>0$, and the second follows from $N>\frac{1}{\epsilon }$ on multiplying both sides by the positive number $\frac{\epsilon }{N}$. Since $\epsilon$ was arbitrary, $\frac{1}{n}\to 0$. $\square$

For $\epsilon =0.01$ the proof asks for $N>100$, and $N=101$ is the answer the lesson on quantifiers found by hand. The proof answers every tolerance at once, with a recipe rather than a table.

The one step that is not arithmetic is the existence of $N$, and it is not a formality. It is the Archimedean property, which the lesson on the real numbers derived from completeness, and which fails in ordered fields that contain infinitesimals: positive elements smaller than every $\frac{1}{n}$. In such a field the sceptic names an infinitesimal as $\epsilon$ and wins. The most basic limit in analysis is already a fact about the reals, not about algebra.

How a proof is found, and how it is written

For most sequences the right $N$ is not obvious, and the finished proof hides how it was found, because the work happens in two passes. The first is scratch work, done on the side and never handed in: start from the goal $|a_n-L|<\epsilon$, simplify $|a_n-L|$, and work backwards to a condition on $n$ that guarantees it. The second is the proof, which runs forwards: it starts from $\epsilon$, names the $N$ the scratch work found, and checks that it wins. This is the pattern the lesson on direct proof called working backwards and writing forwards.

Example. Prove that $a_n=\frac{3n+1}{n+2}$ converges to $3$.

Scratch work. Simplify the distance to the limit:

The goal $\frac{5}{n+2}<\epsilon$ holds exactly when $n>\frac{5}{\epsilon }-2$. That is the sharpest condition, but a cruder one is easier to write with: since $\frac{5}{n+2}<\frac{5}{n}$, it is enough that $\frac{5}{n}<\epsilon$, which holds once $n>\frac{5}{\epsilon }$. So take $N>\frac{5}{\epsilon }$.

Proof. Let $\epsilon >0$. By the Archimedean property there is $N\in \mathbb{N}$ with $N>\frac{5}{\epsilon }$. Let $n\ge N$. Then

so $|a_n-3|<\epsilon$ for every $n\ge N$. Since $\epsilon$ was arbitrary, $a_n\to 3$. $\square$

At $\epsilon =0.1$ the proof asks for $N>50$, so $N=51$, while the sharp condition $n>48$ shows the smallest working position is $49$. Both win, and the proof is shorter for not caring which. What the proof never contains is the backwards reasoning: "suppose $|a_n-3|<\epsilon$, then..." would be assuming the conclusion, and a reader would rightly object.

The step that made the scratch work easy was replacing $\frac{5}{n+2}$ by the larger, simpler $\frac{5}{n}$. That is the central skill: to show a quantity is small, bound it above by something simpler that is visibly small. A fraction gets larger when its numerator is made larger or its denominator smaller (keeping it positive), so the usual moves are to drop negative terms from the numerator and positive terms from the denominator, or to replace a denominator by a fixed fraction of its leading term. For $\frac{n^2+1}{2n^3-n}$, for instance, $n^2+1\le 2n^2$ and $2n^3-n\ge n^3$ for $n\ge 1$, so the expression is at most $\frac{2n^2}{n^3}=\frac{2}{n}$.

Now you. Prove that $a_n=\frac{4n-1}{2n+3}$ converges to $2$, showing the scratch work and the proof separately.

A proof is written for a reader who does not trust its writer, and a few habits make it checkable. Name every quantity when it is introduced and say where it comes from: "let $\epsilon >0$" makes it arbitrary, "there is $N\in \mathbb{N}$ with $N>\frac{5}{\epsilon }$" makes it chosen, and a reader can then check that $N$ depends on $\epsilon$ and on nothing chosen later. Justify each step by a definition or an earlier result, by name. Then read the finished proof back as the sceptic, hunting for the move that would lose the game. Writing "take $N=\frac{5}{\epsilon }$" loses it, because that is not a natural number for most $\epsilon$, and the Archimedean property is what repairs it. Writing "let $\epsilon =\frac{1}{n}$" loses it too, because the sceptic chose $\epsilon$ first and $n$ does not yet exist.

Proving that a sequence diverges

A sequence diverges when it converges to no real number at all. The lesson on quantifiers negated the definition: $a_n$ fails to converge to $L$ when

The roles swap. Now the prover picks one tolerance, the sceptic picks any starting position, and the prover must find a term beyond it that misses. To prove divergence, this must be done for every candidate $L$, so the proof starts "Let $L$ be any real number."

Example. Prove that $a_n=(-1{)}^n$ diverges.

Let $L$ be any real number, and take $\epsilon =1$. Let $N\in \mathbb{N}$. The terms at positions $2N$ and $2N+1$ are both beyond $N$, and they are $1$ and $-1$. If both were within $1$ of $L$, the triangle inequality would give

which is impossible. So one of the two positions gives an $n\ge N$ with $|a_n-L|\ge 1$. Since $N$ was arbitrary, $a_n$ does not converge to $L$, and since $L$ was arbitrary, it converges to nothing. $\square$

Problem 11 of the lesson on quantifiers proved this by splitting on the sign of $L$; the triangle inequality avoids the cases. The proof never says which of the two terms misses, only that one does, and an existential claim needs no more. The tolerance $\epsilon =1$ is half the distance between the two values the sequence keeps returning to, and that is what makes it work: no open interval of radius $1$ contains both $1$ and $-1$. A tolerance of $2$ would fail, since for $L=0$ every term lies within $2$ of $L$.

Now you. Prove that $a_n=n$ diverges.

The sequence $n$ diverges in a particular way: it grows beyond every bound. A sequence tends to infinity, written $a_n\to \infty$, when

The shape is the same as convergence, with "within $\epsilon$ of $L$" replaced by "above $M$", and the proofs have the same shape too. For $a_n=\sqrt{n}$: let $M$ be real, choose $N\in \mathbb{N}$ with $N>M^2$, and let $n\ge N$; then $\sqrt{n}\ge \sqrt{N}>\sqrt{M^2}=|M|\ge M$, using that square roots preserve order on non-negative numbers. Tending to infinity is a kind of divergence, not a kind of convergence: $\infty$ is not a real number, and "$lim{a}_n=\infty$" is a shorthand for the displayed statement, not a limit in the sense of the definition. And not every divergent sequence tends to infinity, as $(-1{)}^n$ shows.

Uniqueness, and bounded sequences

Writing $lim{a}_n=L$ presumes a sequence has only one limit, and that needs proof.

Theorem. If $a_n\to L$ and $a_n\to M$, then $L=M$.

Proof. Suppose not, so $L\ne M$, and let $\epsilon =\frac{|L-M|}{2}$, which is positive. Since $a_n\to L$ there is $N_1$ with $|a_n-L|<\epsilon$ for all $n\ge N_1$, and since $a_n\to M$ there is $N_2$ with $|a_n-M|<\epsilon$ for all $n\ge N_2$. Let $n$ be the larger of $N_1$ and $N_2$. By the triangle inequality,

a contradiction. So $L=M$. $\square$

The picture is two intervals of radius $\frac{|L-M|}{2}$ around $L$ and around $M$. They do not overlap, and a convergent sequence would have to be eventually inside both. Two features of the proof recur throughout the lesson. Each hypothesis "$a_n\to L$" was used with a tolerance chosen by the prover, since a convergence hypothesis may be applied to any $\epsilon >0$ we like. And the two guarantees, which start at different positions $N_1$ and $N_2$, were made to hold together by going past both.

A sequence is bounded when some real $B$ has $|a_n|\le B$ for every $n$; equivalently, the set of its terms is bounded above and below.

Theorem. Every convergent sequence is bounded.

Proof. Let $a_n\to L$. The definition with $\epsilon =1$ gives $N$ with $|a_n-L|<1$ for all $n\ge N$, and then, by the triangle inequality, $|a_n|\le |a_n-L|+|L|<|L|+1$ for $n\ge N$. Only the finitely many terms before position $N$ are left. Let $B$ be the largest of the numbers $|a_1|,|a_2|,\dots ,|a_{N-1}|$ and $|L|+1$. Then $|a_n|\le B$ for every $n$. $\square$

The finitely many early terms can be anything, and they are handled by taking a maximum, which a finite set always has. The contrapositive is a quick test for divergence: an unbounded sequence, such as $n$ or $(-2{)}^n$, cannot converge. The converse of the theorem fails, as the bounded divergent sequence $(-1{)}^n$ shows. Much of the rest of the lesson is about what can be added to "bounded" to rescue it.

The algebra of limits

Proving every limit from the definition would be exhausting. The theorems of this section let limits be computed from limits already known, and each is proved once, from the definition. The basic tool is the idea of spending the tolerance in parts.

Example. Prove that if $a_n\to L$ and $b_n\to M$, then $a_n+b_n\to L+M$.

Let $\epsilon >0$. Then $\frac{\epsilon }{2}>0$, so, applying the definition to each sequence with tolerance $\frac{\epsilon }{2}$, there are $N_1$ and $N_2$ with $|a_n-L|<\frac{\epsilon }{2}$ for $n\ge N_1$ and $|b_n-M|<\frac{\epsilon }{2}$ for $n\ge N_2$. Let $N$ be the larger of $N_1$ and $N_2$, and let $n\ge N$. Then

Since $\epsilon$ was arbitrary, $a_n+b_n\to L+M$. $\square$

The total error is a sum of two errors, so each was given half the budget. Nothing is special about halves. A proof that ends with $|(a_n+b_n)-(L+M)|<2\epsilon$ is also acceptable, once it is observed that $2\epsilon$ is an arbitrary positive number as $\epsilon$ is; the $\frac{\epsilon }{2}$ version simply arranges in advance for the final line to read $\epsilon$.

Now you. Prove that if $a_n\to L$, then $|a_n|\to |L|$. Is the converse true?

Products need one more idea, because the error in $a_n{b}_n$ involves the sizes of the terms, not just their distances from the limits.

Theorem (the algebra of limits). Suppose $a_n\to L$ and $b_n\to M$, and let $c$ be a real number. Then

(i) $c{a}_n\to cL$;

(ii) $a_n{b}_n\to LM$;

(iii) if $M\ne 0$, then $b_n\ne 0$ for all $n$ from some point on, and $\frac{1}{b_n}\to \frac{1}{M}$;

(iv) if $M\ne 0$, then $\frac{a_n}{b_n}\to \frac{L}{M}$.

Proof. (i) If $c=0$ every term is $0$ and the claim is clear. Otherwise let $\epsilon >0$, and choose $N$ with $|a_n-L|<\frac{\epsilon }{|c|}$ for $n\ge N$. Then $|c{a}_n-cL|=|c||a_n-L|<\epsilon$ for $n\ge N$.

(ii) The trick is to add and subtract a mixed term:

Convergent sequences are bounded, so there is $B>0$ with $|a_n|\le B$ for every $n$. Let $\epsilon >0$. Choose $N_1$ with $|b_n-M|<\frac{\epsilon }{2B}$ for $n\ge N_1$, and $N_2$ with $|a_n-L|<\frac{\epsilon }{2(|M|+1)}$ for $n\ge N_2$. For $n$ at least the larger of $N_1$ and $N_2$,

(The $+1$ in the second tolerance keeps the denominator positive when $M=0$.)

(iii) Since $|b_n|\to |M|$ and $|M|>0$, the definition with tolerance $\frac{|M|}{2}$ gives $N_1$ with $|b_n|>|M|-\frac{|M|}{2}=\frac{|M|}{2}$ for $n\ge N_1$; in particular $b_n\ne 0$ there. Let $\epsilon >0$, and choose $N_2$ with $|b_n-M|<\frac{|M{|}^2\epsilon }{2}$ for $n\ge N_2$. For $n$ at least the larger of $N_1$ and $N_2$,

(iv) Write $\frac{a_n}{b_n}=a_n\cdot \frac{1}{b_n}$ and apply (ii) and (iii). $\square$

Part (iii) contains the point everyone forgets: $b_n\to M\ne 0$ does not say $b_n\ne 0$ for every $n$, and the sequence $\frac{1}{b_n}$ may not exist at the start. It exists eventually, and since early terms do not affect limits, that is enough. The lower bound $|b_n|>\frac{|M|}{2}$, keeping the terms away from $0$, is what controls the denominator.

With these rules most limits reduce to $\frac{1}{n}\to 0$ and constants. Take $a_n=\frac{2n^2-n+3}{5n^2+4}$. Dividing top and bottom by $n^2$ gives

The numerator tends to $2-0+3\cdot 0\cdot 0=2$ by the rules for sums, constant multiples and products, and the denominator to $5\ne 0$, so $a_n\to \frac{2}{5}$ by the rule for quotients. Each step cites a theorem, and the theorems were proved from the definition, so this is a proof.

The hypotheses matter. The rules say that if the parts converge, the combination converges to the combination of the limits. They say nothing when the parts diverge: $a_n=n$ and $b_n=-n$ both diverge while $a_n+b_n=0$ converges, and $(-1{)}^n\cdot (-1{)}^n=1$ converges although neither factor does. Writing "$lim(a_n+b_n)=lim{a}_n+lim{b}_n$" before knowing that the limits on the right exist is the commonest misuse. And the quotient rule needs $M\ne 0$: the quotient of $\frac{1}{n}$ by $\frac{1}{n^2}$ is $n$, which diverges, though both parts tend to $0$.

Limits also respect weak inequalities.

Theorem (limits preserve order). If $a_n\to L$, $b_n\to M$ and $a_n\le b_n$ for every $n$, then $L\le M$.

Proof. By the algebra of limits, $b_n-a_n\to M-L$. Suppose, for contradiction, that $M-L<0$, and take $\epsilon =L-M>0$. For $n$ large enough, $|(b_n-a_n)-(M-L)|<L-M$, which gives $b_n-a_n<(M-L)+(L-M)=0$, contradicting $a_n\le b_n$. $\square$

Strict inequalities are not preserved: $\frac{1}{n}>0$ for every $n$, and the limit is $0$, not something positive. This is the same pitfall as for suprema in the previous lesson, and for the same reason.

The squeeze theorem

Some sequences are too awkward to handle directly but can be trapped between two simpler ones.

Theorem (the squeeze theorem). Suppose that $a_n\le b_n\le c_n$ for every $n\ge N_0$, and that $a_n\to L$ and $c_n\to L$. Then $b_n\to L$.

Proof. Let $\epsilon >0$. There are $N_1$ with $|a_n-L|<\epsilon$ for $n\ge N_1$, and $N_2$ with $|c_n-L|<\epsilon$ for $n\ge N_2$. Let $N$ be the largest of $N_0$, $N_1$, $N_2$, and let $n\ge N$. Then

so $|b_n-L|<\epsilon$. Since $\epsilon$ was arbitrary, $b_n\to L$. $\square$

Both outer sequences must tend to the same limit. Knowing $0\le b_n\le 1$ says nothing about whether $b_n$ converges. The commonest use has $a_n=0$ or $a_n=-c_n$: if $|b_n-L|\le c_n$ and $c_n\to 0$, then $b_n\to L$.

Example. Prove that $r^n\to 0$ for every real $r$ with $|r|<1$.

If $r=0$ every term is $0$. Suppose first that $0<r<1$. Then $\frac{1}{r}>1$, so $\frac{1}{r}=1+h$ for some $h>0$. By Bernoulli's inequality, proved in the lesson on induction, $(1+h{)}^n\ge 1+nh>nh$ for every $n\in \mathbb{N}$. Taking reciprocals of positive numbers reverses the inequality, so

The right-hand side tends to $\frac{1}{h}\cdot 0=0$ by the rule for constant multiples, and the left-hand side is the constant $0$. By the squeeze theorem, $r^n\to 0$.

For general $r$ with $0<|r|<1$, the first case gives $|r^n|=|r{|}^n\to 0$, and a sequence tends to $0$ exactly when its absolute values do. So $r^n\to 0$.

The proof turned an unknown, $r^n$, into a known, $\frac{1}{n}$, at the cost of a constant, and that is the typical shape. For $r=0.9$, $h=\frac{1}{9}$, and the bound says ${0.9}^n<\frac{9}{n}$; at $n=100$ it gives ${0.9}^{100}<0.09$, while the truth is about $0.0000266$. The bound is crude, and crude bounds are enough. For $|r|\ge 1$ the sequence $r^n$ does not tend to $0$: its terms have $|r^n|\ge 1$.

Now you. Prove that $\frac{n}{2^n}\to 0$. (First show by induction that $2^n\ge n^2$ for $n\ge 4$.)

Monotone sequences and what completeness buys

A sequence is increasing when $a_n\le a_{n+1}$ for every $n$, and decreasing when $a_n\ge a_{n+1}$ for every $n$; it is monotone if it is one or the other. By induction, an increasing sequence has $a_n\le a_m$ whenever $n\le m$. Boundedness alone did not force convergence, but boundedness with monotonicity does, and this is the first theorem of the lesson that needs completeness.

Theorem (monotone convergence). A bounded increasing sequence of reals converges to the supremum of its terms. A bounded decreasing sequence converges to the infimum of its terms.

Proof. Let $(a_n)$ be increasing and bounded. The set $A=\{a_n:n\in \mathbb{N}\}$ is nonempty and bounded above, so by the completeness axiom it has a supremum $s$. Let $\epsilon >0$. Since $s-\epsilon <s$, it is not an upper bound of $A$ (the characterisation of the supremum), so some term has $a_N>s-\epsilon$. Let $n\ge N$. Then

the middle step because the sequence increases and the last because $s$ is an upper bound. So $|a_n-s|<\epsilon$, and $a_n\to s$.

If $(a_n)$ is decreasing and bounded, then $(-a_n)$ is increasing and bounded, so $-a_n\to \sup \{-a_n\}=-\inf \{a_n\}$, and by the rule for constant multiples $a_n\to \inf \{a_n\}$. $\square$

In $\mathbb{Q}$ the theorem is false. The decimal truncations of $\sqrt{2}$, namely $1,1.4,1.41,1.414,1.4142,\dots$, are rational, increasing and bounded above by $2$. In $ℝ$ the $n$th truncation is within ${10}^{-(n-1)}$ of $\sqrt{2}$, and ${10}^{-(n-1)}\le \frac{1}{n}$, so by the squeeze theorem they converge to $\sqrt{2}$. If they also converged to some rational $q$ (a real tolerance can always be shrunk to a rational one, so the definition means the same in either setting), uniqueness would force $q=\sqrt{2}$, which is irrational. So the sequence has no limit in $\mathbb{Q}$. The proof breaks at its first line, where a supremum is needed and the rationals do not supply one. This is the theorem Dedekind could not prove in 1858, and the reason he went looking for a definition of the real numbers.

The theorem proves that a limit exists without saying what it is. For sequences defined by a rule that produces each term from the previous one, the value can often be found afterwards.

Example. Let $a_1=2$ and $a_{n+1}=\frac{1}{2}(a_n+\frac{2}{a_n})$. Prove that $a_n\to \sqrt{2}$.

The first terms are $2$, $\frac{3}{2}$, $\frac{17}{12}$, $\frac{577}{408}$, and $\frac{577}{408}\approx 1.4142157$ already agrees with $\sqrt{2}\approx 1.4142136$ to five decimal places. The plan is to show the sequence is decreasing and bounded below, conclude that it converges, and then identify the limit.

Positivity. By induction, every $a_n>0$: $a_1=2$, and if $a_n>0$ then $a_{n+1}$ is half a sum of two positive numbers.

Squares at least $2$. For every $n$, writing $a_{n+1}=\frac{a_n^2+2}{2a_n}$,

and $a_1^2=4\ge 2$. Since $a_n>0$, this gives $a_n\ge \sqrt{2}$ for every $n$.

Decreasing. $a_n-a_{n+1}=a_n-\frac{a_n^2+2}{2a_n}=\frac{a_n^2-2}{2a_n}\ge 0$.

Convergence. The sequence is decreasing and bounded below by $\sqrt{2}$, so by the monotone convergence theorem it converges to some $L$, and $L\ge \sqrt{2}$ because limits preserve order. In particular $L\ne 0$.

The limit. The shifted sequence $b_n=a_{n+1}$ also converges to $L$: given $\epsilon$, the $N$ that works for $(a_n)$ works for $(b_n)$, since $n\ge N$ gives $n+1\ge N$. On the other hand, by the algebra of limits, $a_{n+1}=\frac{a_n^2+2}{2a_n}\to \frac{L^2+2}{2L}$, using $2L\ne 0$. By uniqueness of limits, $L=\frac{L^2+2}{2L}$, so $2L^2=L^2+2$ and $L^2=2$. As $L>0$, $L=\sqrt{2}$. $\square$

This is Newton's method applied to $x^2-2=0$, and the rule is older than Newton: it is the Babylonian method for square roots. Notice that every term is rational, so in $\mathbb{Q}$ the sequence is decreasing, bounded below, and has no limit. Every step of the proof works in $\mathbb{Q}$ except the one that invoked monotone convergence.

The order of the steps matters. Solving $L=f(L)$ only identifies the limit once convergence is known. With $a_1=1$ and $a_{n+1}=2a_n$, the same manipulation gives $L=2L$, so "$L=0$", but the sequence is $2^{n-1}$, which tends to infinity. The equation found the only possible limit; it did not show there is one.

Now you. Let $a_1=0$ and $a_{n+1}=\frac{a_n^2+1}{2}$. Prove that $(a_n)$ converges and find its limit.

Subsequences and the theorem of Bolzano and Weierstrass

A bounded sequence need not converge, but it cannot avoid converging entirely: part of it always does. To say which part, pick out infinitely many of its terms in order. If $n_1<n_2<n_3<\cdots$ are natural numbers, the sequence $a_{n_1},a_{n_2},a_{n_3},\dots$ is a subsequence of $(a_n)$, and its $k$th term is $a_{n_k}$. The even-numbered terms $a_2,a_4,a_6,\dots$ form a subsequence with $n_k=2k$; so do the terms at prime positions. The terms must be taken in their original order and without repetition, so $a_2,a_1,a_3,\dots$ and $a_1,a_1,a_2,\dots$ are not subsequences.

Since $n_1\ge 1$ and each $n_{k+1}\ge n_k+1$, induction gives $n_k\ge k$ for every $k$: the $k$th term of a subsequence sits at position $k$ or later in the original sequence.

Theorem. If $a_n\to L$, then every subsequence of $(a_n)$ also converges to $L$.

Proof. Let $(a_{n_k})$ be a subsequence and let $\epsilon >0$. There is $N$ with $|a_n-L|<\epsilon$ for all $n\ge N$. Let $k\ge N$. Then $n_k\ge k\ge N$, so $|a_{n_k}-L|<\epsilon$. $\square$

The contrapositive is the most efficient divergence test there is: a sequence with two subsequences converging to different limits, or with one divergent subsequence, diverges. For $(-1{)}^n$, the even-numbered terms are all $1$ and the odd-numbered terms all $-1$, so the sequence diverges, in one line. The same test disposes of $a_n=(-1{)}^n\frac{n}{n+1}$: the even terms $\frac{2k}{2k+1}$ tend to $1$ and the odd terms tend to $-1$.

The positive result needs one lemma, which has nothing to do with limits.

Lemma. Every sequence of real numbers has a monotone subsequence.

Proof. Call a position $m$ a peak if $a_m\ge a_n$ for every $n>m$: the term at $m$ is at least as large as every later term.

Suppose there are infinitely many peaks, at positions $m_1<m_2<m_3<\cdots$. Each $m_{k+1}$ comes after the peak $m_k$, so $a_{m_k}\ge a_{m_{k+1}}$, and $(a_{m_k})$ is a decreasing subsequence.

Suppose instead there are finitely many peaks (perhaps none). Choose a position $n_1$ after all of them. Since $n_1$ is not a peak, some later position $n_2>n_1$ has $a_{n_2}>a_{n_1}$. Since $n_2$ is also after every peak, it is not a peak, so some $n_3>n_2$ has $a_{n_3}>a_{n_2}$. Continuing in this way (formally, by a recursive definition) gives positions $n_1<n_2<n_3<\cdots$ with $(a_{n_k})$ increasing. $\square$

Theorem (Bolzano and Weierstrass). Every bounded sequence of real numbers has a convergent subsequence.

Proof. By the lemma, a bounded sequence has a monotone subsequence. The subsequence is bounded, since its terms are among those of the original, so by the monotone convergence theorem it converges. $\square$

Bolzano used the idea in 1817, and Weierstrass made it a cornerstone of his Berlin lectures half a century later, hence the double name. The theorem is again a fact about $ℝ$ and not about $\mathbb{Q}$: the bounded sequence of decimal truncations of $\sqrt{2}$ has no subsequence converging to a rational, since every subsequence converges in $ℝ$ to $\sqrt{2}$. It is the tool analysis uses whenever something must be found and no formula is available. A continuous function on a closed interval $[a,b]$ attains a greatest value, for instance, because a sequence of points at which the values approach their least upper bound has, by this theorem, a subsequence of points converging to some point of $[a,b]$, and continuity makes the value there the maximum (the same theorem first shows that the values are bounded, so that the least upper bound exists). The Calculus lesson on continuity states this extreme value theorem and builds on it.

Limits of functions and continuity

The same game can be played with a function instead of a sequence. Where a sequence is watched as $n$ grows, a function is watched as $x$ approaches a point $a$, and the position $N$ is replaced by a distance $\delta$.

Let $f$ be a real function whose domain $D$ contains every $x$ with $0<|x-a|<r$, for some $r>0$: the function is defined near $a$, though perhaps not at $a$ itself. Then $f(x)$ tends to $L$ as $x$ tends to $a$, written $\underset{x\to a}{lim}f(x)=L$ or $f(x)\to L$ as $x\to a$, when

The sceptic names a tolerance $\epsilon$ on the output. The prover answers with a tolerance $\delta$ on the input. The sceptic picks any $x$ in the domain within $\delta$ of $a$ other than $a$ itself, and the prover wins if $f(x)$ is within $\epsilon$ of $L$. As before, $\delta$ may depend on $\epsilon$, a working $\delta$ may be replaced by any smaller positive one, and a proof has the shape: let $\epsilon >0$; choose $\delta$; let $x$ satisfy $0<|x-a|<\delta$; show $|f(x)-L|<\epsilon$.

The central technique is new. In a sequence proof, the distance $|a_n-L|$ was bounded by something depending on $n$ alone. Here $|f(x)-L|$ usually factors as $|x-a|$ times something else, and the something else must be kept under control by first insisting that $x$ stay reasonably near $a$.

Example. Prove that $\underset{x\to 2}{lim}{x}^2=4$.

Scratch work. $|x^2-4|=|x-2||x+2|$. The first factor is what $\delta$ controls. The second is not small, but it is bounded if $x$ stays near $2$: if $|x-2|<1$, then $1<x<3$, so $|x+2|<5$. Then $|x^2-4|<5|x-2|$, which is below $\epsilon$ once $|x-2|<\frac{\epsilon }{5}$. Both restrictions are wanted, so take $\delta$ to be the smaller of $1$ and $\frac{\epsilon }{5}$.

Proof. Let $\epsilon >0$, and let $\delta$ be the smaller of $1$ and $\frac{\epsilon }{5}$, so $\delta >0$. Let $x$ satisfy $0<|x-2|<\delta$. Since $|x-2|<1$, we have $1<x<3$, so $0<x+2<5$. Since $|x-2|<\frac{\epsilon }{5}$,

Since $\epsilon$ was arbitrary, $\underset{x\to 2}{lim}{x}^2=4$. $\square$

The first restriction, $\delta \le 1$, is arbitrary: $\delta \le \frac{1}{2}$ would bound $|x+2|$ by $4.5$ and work as well. What matters is that some fixed restriction comes first, so that the bound on the other factor does not depend on $\delta$ itself. Choosing "$\delta =\frac{\epsilon }{|x+2|}$" is the classic error: $\delta$ must be chosen before $x$, so it cannot depend on $x$.

Now you. Prove that $\underset{x\to 3}{lim}(x^2-x)=6$.

A function $f$ with domain $D$ is continuous at a point $a\in D$ when

and continuous when it is continuous at every point of its domain. The condition $0<|x-a|$ has gone, since at $x=a$ the inequality holds automatically, and the limit $L$ has become the value $f(a)$. So when $f$ is defined near $a$, continuity at $a$ says exactly that $\underset{x\to a}{lim}f(x)=f(a)$: the function's value is what its nearby values predict. The Example shows that $x^2$ is continuous at $2$.

Proving continuity function by function would be as tiring as proving limits sequence by sequence. The link between the two kinds of limit makes the algebra of limits available.

Theorem (sequential continuity). If $f$ is continuous at $a$, and $(x_n)$ is a sequence in the domain with $x_n\to a$, then $f(x_n)\to f(a)$.

Proof. Let $\epsilon >0$. By continuity there is $\delta >0$ such that $|f(x)-f(a)|<\epsilon$ whenever $x$ is in the domain and $|x-a|<\delta$. Since $x_n\to a$, applying the definition of convergence with tolerance $\delta$, there is $N$ with $|x_n-a|<\delta$ for all $n\ge N$. For such $n$, $|f(x_n)-f(a)|<\epsilon$. So $f(x_n)\to f(a)$. $\square$

The converse is true as well, and the problem sheet proves it: if $f(x_n)\to f(a)$ for every sequence $x_n\to a$ in the domain, then $f$ is continuous at $a$. With both directions, continuity becomes a statement about sequences, and the algebra of limits transfers. If $f$ and $g$ are continuous at $a$ and $x_n\to a$, then $f(x_n)\to f(a)$ and $g(x_n)\to g(a)$, so $f(x_n)+g(x_n)\to f(a)+g(a)$, and the same for products, and for quotients when $g(a)\ne 0$. So sums, products and quotients of continuous functions are continuous. The constant functions and $x$ itself are plainly continuous (take $\delta =\epsilon$ for $x$), so every polynomial is continuous everywhere, and every rational function wherever its denominator is not zero.