Chapter 2 · Sequences and Series of Real Numbers

2.1 Sequences, Monotone and Cauchy Sequences

A sequence converges when its terms eventually stay within every tolerance $\varepsilon$ of one number. Monotone bounded sequences and Cauchy sequences always converge in $\mathbb{R}$ — that is completeness at work.

A sequence is the simplest infinite object in analysis: a rule that produces a number $a_n$ for every $n\in\mathbb{N}$. Almost everything later in this course is built from sequences. A series is a sequence of partial sums; a Riemann integral is a limit of a sequence of sums; continuity can be tested along sequences; compactness in a metric space is defined by them; and a numerical method — Newton's method, fixed-point iteration, a recursion in a computer program — is a sequence that we hope converges, and converges fast. The central question is always the same: do the terms settle down near one number, and how can we prove it when we cannot compute the limit in advance?

This section gives the precise $\varepsilon$–$N$ definition of convergence, the algebra of limits and the squeeze theorem, the standard limits ($a^n$, $a^{1/n}$, $n^{1/n}$, $n^k/a^n$, $a^n/n!$) that are used everywhere, and then the two great existence theorems that need completeness: the monotone convergence theorem (which produces the number $e$ and settles recursive sequences) and the Cauchy criterion (which lets us prove convergence without knowing the limit, and leads to contractive sequences and fixed-point iteration). CSIR NET tests these ideas directly — "the limit of this sequence is…", "which of these sequences are Cauchy / convergent / monotone" — and they reappear inside questions on series, continuity and metric spaces.

Convergence: the $\varepsilon$–$N$ Definition

📘 Definition 2.1 — Sequence, limit, convergence

A sequence of real numbers is a function $a:\mathbb{N}\to\mathbb{R}$; we write $a_n$ for $a(n)$ and $(a_n)$ or $(a_n)_{n\ge1}$ for the sequence. (The set of values $\{a_n:n\in\mathbb{N}\}$ is a different object: $(-1)^n$ has infinitely many terms but only two values.)

The sequence $(a_n)$ converges to $L\in\mathbb{R}$, written $a_n\to L$ or $\lim_{n\to\infty}a_n=L$, if

$$\forall\varepsilon\gt0\ \ \exists N\in\mathbb{N}\ \ \forall n\ge N:\quad |a_n-L|\lt\varepsilon .$$

A sequence that converges to some $L$ is convergent; otherwise it is divergent. A property holds eventually if it holds for all $n\ge N$ for some $N$. So $a_n\to L$ means: every $\varepsilon$-neighbourhood $(L-\varepsilon,L+\varepsilon)$ contains the terms eventually; only finitely many terms lie outside it. The number $N$ may (and usually does) depend on $\varepsilon$.

📘 Definition 2.2 — Divergence to $\pm\infty$
$(a_n)$ diverges to $+\infty$, written $a_n\to+\infty$, if for every $M\in\mathbb{R}$ there is $N$ with $a_n\gt M$ for all $n\ge N$; similarly $a_n\to-\infty$ if for every $M$ eventually $a_n\lt M$. Such sequences are called properly divergent. They are divergent: $+\infty$ is not a real number, and "$\lim a_n=\infty$" is shorthand. A divergent sequence need not be properly divergent: $(-1)^n$ and $n(-1)^n$ are neither convergent nor properly divergent (they oscillate).
📐 Theorem 2.1 — Uniqueness, boundedness and tails
(a) A sequence has at most one limit. (b) Every convergent sequence is bounded: there is $M$ with $|a_n|\le M$ for all $n$. (c) Changing, inserting or deleting finitely many terms does not affect convergence or the limit; in particular, for a fixed $m$, $a_n\to L$ iff the tail $(a_{n+m})_{n\ge1}\to L$. (d) $a_n\to L$ iff $|a_n-L|\to0$.

Proof. (a) Suppose $a_n\to L$ and $a_n\to L'$ with $L\ne L'$. Take $\varepsilon=|L-L'|/2\gt0$. There are $N_1,N_2$ with $|a_n-L|\lt\varepsilon$ for $n\ge N_1$ and $|a_n-L'|\lt\varepsilon$ for $n\ge N_2$. For $n=\max(N_1,N_2)$, $$|L-L'|\le|L-a_n|+|a_n-L'|\lt2\varepsilon=|L-L'|,$$ a contradiction.

(b) With $\varepsilon=1$ choose $N$ such that $|a_n-L|\lt1$ for $n\ge N$; then $|a_n|\le|L|+1$ for $n\ge N$ (triangle inequality). Put $M=\max(|a_1|,\dots,|a_{N-1}|,|L|+1)$: a maximum of finitely many numbers.

(c) If the two sequences agree for all $n\ge n_0$, any $N$ that works for one works, after replacing it by $\max(N,n_0)$, for the other. For the shifted tail, $|a_{n+m}-L|\lt\varepsilon$ for $n\ge N$ whenever $|a_k-L|\lt\varepsilon$ for $k\ge N$; conversely, if $|a_{n+m}-L|\lt\varepsilon$ for $n\ge N$, then $|a_k-L|\lt\varepsilon$ for $k\ge N+m$. (d) is the definition read twice: $\big||a_n-L|-0\big|=|a_n-L|$. ∎

The converse of (b) fails: $(-1)^n$ is bounded but divergent. Boundedness is necessary for convergence, not sufficient — the sufficient conditions come in the next subsections.

✏️ Example 1 — Using the definition
(a) Prove that $a_n=\dfrac{3n+1}{2n+5}\to\dfrac32$, and find the least $N$ that works for $\varepsilon=0.01$. (b) Prove that $\big((-1)^n\big)$ diverges. (c) Prove that $\dfrac{n^2+1}{n+1}\to+\infty$.
(a) Simplify the error $$\left|\frac{3n+1}{2n+5}-\frac32\right|=\left|\frac{2(3n+1)-3(2n+5)}{2(2n+5)}\right|=\frac{13}{2(2n+5)}\lt\frac{13}{4n}.$$
(a) Choose $N$ Given $\varepsilon\gt0$, by the Archimedean property (§1.2) choose $N\in\mathbb{N}$ with $N\gt\dfrac{13}{4\varepsilon}$. For $n\ge N$ the error is $\lt\dfrac{13}{4n}\le\dfrac{13}{4N}\lt\varepsilon$. For $\varepsilon=0.01$ the exact error is $\lt0.01$ iff $2(2n+5)\gt1300$, i.e. $n\gt322.5$: the least $N$ is $323$ (the cruder bound gives $N=326$, which also works — any $N$ that works is fine).
(b) Contradiction with $\varepsilon=1$ Suppose $(-1)^n\to L$. Choose $N$ with $|(-1)^n-L|\lt1$ for $n\ge N$. Taking an even and an odd $n\ge N$: $$2=|1-(-1)|\le|1-L|+|L-(-1)|\lt1+1=2,$$ which is absurd. So no $L$ works.
(c) Beat every $M$ $\dfrac{n^2+1}{n+1}\ge\dfrac{n^2-1}{n+1}=n-1$. Given $M$, choose $N\gt M+1$; then for $n\ge N$ the term is $\ge n-1\gt M$.
Interactive 1 — The $\varepsilon$-Band and the Number $N(\varepsilon)$

The amber band is $(L-\varepsilon,L+\varepsilon)$. Terms inside it are blue, terms outside are red, and the dashed line marks the least $N$ from which every term stays inside (found by an exact search far beyond the plot). Press Play to shrink $\varepsilon$: for a convergent sequence $N(\varepsilon)$ grows but always exists; for the oscillating sequence it stops existing once $\varepsilon\le1$.

candidate L—
ε—
least N(ε)—
terms outside the band—
error |a(N) − L|—

The Algebra of Limits, the Squeeze Theorem and Standard Limits

📐 Theorem 2.2 — Algebra of limits and order
Let $a_n\to a$ and $b_n\to b$ (real limits), and $c\in\mathbb{R}$. Then
  1. $a_n+b_n\to a+b$, $\ ca_n\to ca$, $\ a_nb_n\to ab$;
  2. if $b\ne0$, then $b_n\ne0$ eventually and $a_n/b_n\to a/b$ (over the indices where $b_n\ne0$);
  3. $|a_n|\to|a|$; and if $a_n\ge0$ for all $n$, then $a\ge0$ and $\sqrt{a_n}\to\sqrt a$;
  4. (order) if $a_n\le b_n$ eventually, then $a\le b$. In particular, if $\alpha\le a_n\le\beta$ eventually then $\alpha\le a\le\beta$.

Proof. Let $\varepsilon\gt0$. (1) Choose $N$ so that $|a_n-a|\lt\varepsilon/2$ and $|b_n-b|\lt\varepsilon/2$ for $n\ge N$ (take the larger of the two $N$'s). Then $|(a_n+b_n)-(a+b)|\le|a_n-a|+|b_n-b|\lt\varepsilon$. Also $|ca_n-ca|=|c||a_n-a|$. For products, let $M$ bound $|a_n|$ (Theorem 2.1(b)); then $$|a_nb_n-ab|=|a_n(b_n-b)+b(a_n-a)|\le M|b_n-b|+|b||a_n-a|,$$ and both terms tend to $0$: choose $N$ with $|b_n-b|\lt\varepsilon/(2M+1)$ and $|a_n-a|\lt\varepsilon/(2|b|+1)$.

(2) With $\varepsilon=|b|/2$ there is $N_0$ with $|b_n-b|\lt|b|/2$, hence $|b_n|\gt|b|/2\gt0$, for $n\ge N_0$. For those $n$, $$\left|\frac1{b_n}-\frac1b\right|=\frac{|b-b_n|}{|b_n||b|}\le\frac{2}{|b|^2}|b_n-b|\to0 ,$$ so $1/b_n\to1/b$, and $a_n/b_n=a_n\cdot(1/b_n)\to a/b$ by (1).

(3) $\big||a_n|-|a|\big|\le|a_n-a|$ (reverse triangle inequality). If $a_n\ge0$ for all $n$ but $a\lt0$, then with $\varepsilon=-a$ we would get $a_n\lt a+\varepsilon=0$ eventually — impossible; so $a\ge0$. If $a\gt0$, $$|\sqrt{a_n}-\sqrt a|=\frac{|a_n-a|}{\sqrt{a_n}+\sqrt a}\le\frac{|a_n-a|}{\sqrt a}\to0;$$ if $a=0$, then $a_n\lt\varepsilon^2$ eventually gives $\sqrt{a_n}\lt\varepsilon$.

(4) $b_n-a_n\ge0$ eventually and $b_n-a_n\to b-a$ by (1), so $b-a\ge0$ by the argument in (3) applied to the tail. ∎

Order is preserved only in the weak form: $a_n\lt b_n$ for every $n$ gives only $a\le b$ (take $a_n=-\tfrac1n$, $b_n=\tfrac1n$). And the theorem needs both limits to exist: $a_n=n$, $b_n=\tfrac1n$ give $a_nb_n=1$, but "$\infty\cdot0$" is not a rule.

📐 Theorem 2.3 — Squeeze theorem; comparison for infinite limits
(a) Squeeze (sandwich) theorem. If $x_n\le y_n\le z_n$ eventually and $x_n\to L$, $z_n\to L$, then $y_n\to L$. In particular, if $|y_n-L|\le t_n$ eventually and $t_n\to0$, then $y_n\to L$; and $a_n\to0$ with $(b_n)$ bounded gives $a_nb_n\to0$.
(b) If $a_n\to+\infty$ and $b_n\ge a_n$ eventually, then $b_n\to+\infty$. If $a_n\to+\infty$ and $(b_n)$ is bounded below, then $a_n+b_n\to+\infty$; if moreover $b_n\ge c\gt0$ eventually, $a_nb_n\to+\infty$. Finally, $a_n\to+\infty\Rightarrow\tfrac1{a_n}\to0$, and if $a_n\gt0$ with $a_n\to0$ then $\tfrac1{a_n}\to+\infty$.

Proof. (a) Given $\varepsilon\gt0$, choose $N$ (beyond the point where the inequalities hold) with $L-\varepsilon\lt x_n$ and $z_n\lt L+\varepsilon$ for $n\ge N$. Then $L-\varepsilon\lt x_n\le y_n\le z_n\lt L+\varepsilon$. For the special cases take $x_n=L-t_n$, $z_n=L+t_n$; and if $|b_n|\le M$ then $|a_nb_n|\le M|a_n|\to0$. (b) Given $M$, eventually $b_n\ge a_n\gt M$. If $b_n\ge\beta$ for all $n$, eventually $a_n\gt M-\beta$, so $a_n+b_n\gt M$. If $b_n\ge c\gt0$, eventually $a_n\gt\max(M,0)/c$ and $a_nb_n\gt M$. If $a_n\to\infty$ and $\varepsilon\gt0$, eventually $a_n\gt1/\varepsilon$, i.e. $0\lt1/a_n\lt\varepsilon$; the last claim is the same argument reversed. ∎

📐 Theorem 2.4 — The ratio criterion for sequences
Let $a_n\ne0$ for all $n$ and suppose $\left|\dfrac{a_{n+1}}{a_n}\right|\to\rho$. If $\rho\lt1$ then $a_n\to0$. If $\rho\gt1$ then $|a_n|\to+\infty$. (If $\rho=1$ nothing can be concluded: $a_n=1$, $\tfrac1n$ and $n$ all have $\rho=1$.)

Proof. If $\rho\lt1$, fix $r$ with $\rho\lt r\lt1$ and choose $N$ with $|a_{n+1}/a_n|\lt r$ for $n\ge N$. By induction $|a_n|\le|a_N|\,r^{n-N}$ for $n\ge N$, and $r^n\to0$ (Theorem 2.5(a) below, whose proof does not use this theorem), so $a_n\to0$ by the squeeze theorem. If $\rho\gt1$, fix $1\lt r\lt\rho$; then $|a_n|\ge|a_N|r^{n-N}$ for $n\ge N$, and $r^{n}\to\infty$ by Bernoulli's inequality $r^n=(1+(r-1))^n\ge1+n(r-1)$. ∎

📐 Theorem 2.5 — Standard limits
  1. $a^n\to0$ if $|a|\lt1$; $\ a^n\to+\infty$ if $a\gt1$; $(-1)^n$ and $a^n$ for $a\lt-1$ diverge.
  2. $a^{1/n}\to1$ for every $a\gt0$.
  3. $n^{1/n}\to1$.
  4. $\dfrac{n^k}{a^n}\to0$ for every fixed $k\in\mathbb{N}$ and $a\gt1$ ("exponentials beat powers").
  5. $\dfrac{a^n}{n!}\to0$ for every $a\in\mathbb{R}$, and $\dfrac{n!}{n^n}\to0$ ("factorials beat exponentials, $n^n$ beats factorials").

Proof. (1) If $0\lt|a|\lt1$ write $|a|=\dfrac1{1+h}$ with $h\gt0$. Bernoulli's inequality (§1.2, Exercise I.8) gives $(1+h)^n\ge1+nh\gt nh$, so $0\lt|a|^n\lt\dfrac1{nh}\to0$. For $a\gt1$, $a^n\ge1+n(a-1)\to\infty$. For $a\le-1$, consecutive terms differ by $|a^{n+1}-a^n|=|a|^n|a-1|\ge2$, which is impossible for a convergent sequence (eventually all terms would be within $\tfrac12$ of the limit).

(2) For $a\ge1$ put $d_n=a^{1/n}-1\ge0$. Then $a=(1+d_n)^n\ge1+nd_n$, so $0\le d_n\le\dfrac{a-1}{n}\to0$. For $0\lt a\lt1$, $a^{1/n}=1/(1/a)^{1/n}\to1/1=1$ by Theorem 2.2(2).

(3) Put $d_n=n^{1/n}-1\ge0$. For $n\ge2$ the binomial theorem (all terms non-negative) gives $$n=(1+d_n)^n\ge\binom n2d_n^2=\frac{n(n-1)}2d_n^2,$$ so $0\le d_n\le\sqrt{\dfrac2{n-1}}\to0$.

(4) With $a_n=n^k/a^n$: $\dfrac{a_{n+1}}{a_n}=\dfrac1a\left(1+\dfrac1n\right)^k\to\dfrac1a\lt1$ (Theorem 2.2, finitely many factors), so $a_n\to0$ by Theorem 2.4. (5) For $a\ne0$, $\left|\dfrac{a^{n+1}/(n+1)!}{a^n/n!}\right|=\dfrac{|a|}{n+1}\to0$. And $0\lt\dfrac{n!}{n^n}=\dfrac1n\cdot\dfrac2n\cdots\dfrac nn\le\dfrac1n$. ∎

✏️ Example 2 — Computing limits
Find (a) $\lim\left(\sqrt{n^2+n}-n\right)$; (b) $\lim\,(2^n+3^n)^{1/n}$; (c) $\lim\dfrac{n^3}{2^n}$; (d) $\lim\displaystyle\sum_{k=1}^{n}\frac{n}{n^2+k}$; (e) $\lim\dfrac{(-1)^n n+\sin n}{n^2+1}$.
(a) Conjugate $$\sqrt{n^2+n}-n=\frac{n}{\sqrt{n^2+n}+n}=\frac{1}{\sqrt{1+1/n}+1}\to\frac1{1+1}=\frac12,$$ using Theorem 2.2(3) for the square root. ("$\infty-\infty$" is not $0$.)
(b) Dominant term $3^n\le2^n+3^n\le2\cdot3^n$, so $3\le(2^n+3^n)^{1/n}\le2^{1/n}\cdot3\to3$ (Theorem 2.5(2)). By the squeeze theorem the limit is $3$. In general $(a_1^n+\cdots+a_m^n)^{1/n}\to\max a_i$ for $a_i\gt0$.
(c) Ratio $\dfrac{(n+1)^3/2^{n+1}}{n^3/2^n}=\dfrac12\left(1+\dfrac1n\right)^3\to\dfrac12\lt1$, so the limit is $0$ (Theorem 2.4).
(d) Squeeze a sum Each of the $n$ terms lies between $\dfrac{n}{n^2+n}$ and $\dfrac{n}{n^2+1}$, so $$\frac{n^2}{n^2+n}\le\sum_{k=1}^n\frac{n}{n^2+k}\le\frac{n^2}{n^2+1},$$ and both bounds tend to $1$. The limit is $1$. (Check: for $n=1000$ the sum is $0.99950\ldots$)
(e) Bound the oscillation $\left|\dfrac{(-1)^nn+\sin n}{n^2+1}\right|\le\dfrac{n+1}{n^2+1}\le\dfrac{2n}{n^2}=\dfrac2n\to0$. The limit is $0$ — oscillation in the numerator does not matter when the bound tends to $0$.
✏️ Example 3 — Prove or disprove
For real sequences, prove or disprove: (a) if $a_n\to0$ and $(b_n)$ is bounded, then $a_nb_n\to0$; (b) if $(a_n+b_n)$ and $(a_n)$ converge, then $(b_n)$ converges; (c) if $(a_nb_n)$ converges, then $(a_n)$ or $(b_n)$ converges; (d) if $(|a_n|)$ converges, then $(a_n)$ converges; (e) if $a_n\to a$ and $a_n\gt0$ for all $n$, then $a\gt0$.
(a) True If $|b_n|\le M$ then $|a_nb_n|\le M|a_n|\to0$ (Theorem 2.3(a)). Example: $\dfrac{\sin n}{n}\to0$. Boundedness matters: $a_n=\tfrac1n$, $b_n=n^2$.
(b) True $b_n=(a_n+b_n)-a_n$ is a difference of two convergent sequences (Theorem 2.2(1)).
(c) False $a_n=(-1)^n$, $b_n=(-1)^{n+1}$: both diverge, but $a_nb_n=-1$ converges. (Also $a_n+b_n=0$ converges.)
(d) False, except for limit $0$ $a_n=(-1)^n$ has $|a_n|=1$. But if $|a_n|\to0$ then $a_n\to0$, since $|a_n-0|=\big||a_n|-0\big|$.
(e) False $a_n=\tfrac1n\gt0$ but $a=0$. Theorem 2.2(4) gives only $a\ge0$: strict inequalities become weak in the limit.

Monotone Sequences, the Number $e$ and Recursive Sequences

📘 Definition 2.3 — Monotone sequences
$(a_n)$ is increasing (non-decreasing) if $a_n\le a_{n+1}$ for all $n$, strictly increasing if $a_n\lt a_{n+1}$, and decreasing / strictly decreasing with the inequalities reversed. It is monotone if it is increasing or decreasing, and eventually monotone if some tail is monotone.
📐 Theorem 2.6 — Monotone convergence theorem
A monotone sequence of real numbers converges if and only if it is bounded. More precisely: if $(a_n)$ is increasing and bounded above, then $a_n\to\sup_na_n$; if it is decreasing and bounded below, then $a_n\to\inf_na_n$. An increasing sequence that is not bounded above diverges to $+\infty$ (and a decreasing one not bounded below, to $-\infty$).

Proof. A convergent sequence is bounded (Theorem 2.1). Conversely, let $(a_n)$ be increasing and bounded above. The set $\{a_n:n\in\mathbb{N}\}$ is nonempty and bounded above, so by the completeness axiom (§1.2) it has a supremum $u$. Let $\varepsilon\gt0$. By the $\varepsilon$-characterisation of the supremum there is $N$ with $a_N\gt u-\varepsilon$. For $n\ge N$, monotonicity and the upper bound give $$u-\varepsilon\lt a_N\le a_n\le u,$$ so $|a_n-u|\lt\varepsilon$. Hence $a_n\to u$. For a decreasing sequence bounded below apply this to $(-a_n)$, using $\inf S=-\sup(-S)$. If $(a_n)$ is increasing and not bounded above, then for every $M$ some $a_N\gt M$, and $a_n\ge a_N\gt M$ for $n\ge N$. ∎

The theorem is an existence statement: it tells us the limit exists without computing it — and it is equivalent to completeness. In $\mathbb{Q}$ the increasing bounded sequence $1,\,1.4,\,1.41,\,1.414,\dots$ has no rational limit.

📐 Theorem 2.7 — The number $e$
Let $e_n=\left(1+\dfrac1n\right)^n$ and $s_n=\displaystyle\sum_{k=0}^n\frac1{k!}$. Then (a) $(e_n)$ is strictly increasing with $2\le e_n\lt3$; (b) $(s_n)$ is strictly increasing with $s_n\lt3$; (c) both converge to the same limit, called $e$; (d) $0\lt e-s_n\lt\dfrac1{n!\,n}$ for every $n\in\mathbb{N}$. Numerically $e=2.718281828\ldots$

Proof. (a) By the binomial theorem, $$e_n=\sum_{k=0}^n\binom nk\frac1{n^k}=\sum_{k=0}^n\frac1{k!}\left(1-\frac1n\right)\left(1-\frac2n\right)\cdots\left(1-\frac{k-1}n\right).$$ Passing from $n$ to $n+1$, every factor $1-\tfrac jn$ increases to $1-\tfrac j{n+1}$, every term increases (strictly for $k\ge2$), and a new positive term ($k=n+1$) appears; so $e_n\lt e_{n+1}$. Each product of brackets is at most $1$, so $e_n\le s_n$. Since $k!\ge2^{k-1}$ for $k\ge1$, $$s_n\le1+\left(1+\tfrac12+\tfrac14+\cdots+\tfrac1{2^{n-1}}\right)\lt1+2=3.$$ Also $e_1=2$. (b) is now clear. (c) By Theorem 2.6 both sequences converge; let $E=\lim e_n$, $s=\lim s_n$. From $e_n\le s_n$ we get $E\le s$ (Theorem 2.2(4)). For the reverse inequality fix $m$; for $n\ge m$, dropping the terms with $k\gt m$, $$e_n\ge\sum_{k=0}^m\frac1{k!}\left(1-\frac1n\right)\cdots\left(1-\frac{k-1}n\right).$$ The right side is a fixed finite sum of products, each tending to $\tfrac1{k!}$ as $n\to\infty$; so letting $n\to\infty$ gives $E\ge s_m$. Now let $m\to\infty$: $E\ge s$. Hence $E=s=e$.

(d) For $m\gt n$, $$s_m-s_n=\frac1{(n+1)!}\left(1+\frac1{n+2}+\frac1{(n+2)(n+3)}+\cdots\right)\le\frac1{(n+1)!}\sum_{j\ge0}\frac1{(n+2)^j}=\frac{1}{(n+1)!}\cdot\frac{n+2}{n+1}.$$ Letting $m\to\infty$, $0\lt s_{n+1}-s_n\le e-s_n\le\dfrac{n+2}{(n+1)!\,(n+1)}$, and this is $\lt\dfrac1{n!\,n}$ because $n(n+2)\lt(n+1)^2$. ∎

Part (d) is a fast error bound: $s_{10}$ already gives $e$ to $7$ decimals. It also proves that $e$ is irrational (Exercise III.6).

🧭 Problem-solving strategy — recursive sequences $a_{n+1}=f(a_n)$
  1. Compute the first few terms and guess the behaviour (increasing? alternating?) and the candidate limits: the solutions of $L=f(L)$.
  2. Bound by induction: show all $a_n$ lie in an interval $I$ (usually with the candidate limit as an end point).
  3. Monotone? Show $a_{n+1}-a_n$ has a constant sign — often by factorising $f(x)-x$ on $I$, or by induction "$a_n\le a_{n+1}\Rightarrow f(a_n)\le f(a_{n+1})$" when $f$ is increasing.
  4. Conclude with the monotone convergence theorem, then pass to the limit in $a_{n+1}=f(a_n)$ (needs $f$ continuous at $L$) and choose the root consistent with the bounds.
  5. If the sequence is not monotone (it alternates), use the odd and even subsequences (§2.2) or show it is contractive (Theorem 2.9 below).
Never solve $L=f(L)$ before proving that the limit exists: $a_{n+1}=2a_n$, $a_1=1$ "gives" $L=2L$, so $L=0$ — but $a_n=2^{n-1}\to\infty$.
✏️ Example 4 — Two monotone recursions
(a) $a_1=1$, $a_{n+1}=\sqrt{2+a_n}$. Prove that $(a_n)$ converges and find its limit. (b) (Babylonian square root) $x_1=2$, $x_{n+1}=\dfrac12\left(x_n+\dfrac2{x_n}\right)$. Prove $x_n\to\sqrt2$, and show $x_{n+1}-\sqrt2=\dfrac{(x_n-\sqrt2)^2}{2x_n}$.
(a) Bounded Claim $1\le a_n\lt2$. True for $n=1$; if $1\le a_n\lt2$ then $\sqrt3\le a_{n+1}\lt\sqrt4=2$.
(a) Increasing $a_{n+1}^2-a_n^2=2+a_n-a_n^2=(2-a_n)(1+a_n)\gt0$, and both $a_n,a_{n+1}$ are positive, so $a_{n+1}\gt a_n$.
(a) Limit By Theorem 2.6, $a_n\to L$ with $1\le L\le2$. Squaring, $a_{n+1}^2=2+a_n$; letting $n\to\infty$ (the tail $(a_{n+1})$ has the same limit), $L^2=2+L$, so $(L-2)(L+1)=0$ and $L=2$.
(b) Bounded below, decreasing All $x_n\gt0$. By AM–GM, $x_{n+1}=\tfrac12(x_n+\tfrac2{x_n})\ge\sqrt{x_n\cdot\tfrac2{x_n}}=\sqrt2$ for every $n$ (and $x_1=2\gt\sqrt2$). Then $x_n-x_{n+1}=\dfrac{x_n^2-2}{2x_n}\ge0$: decreasing, bounded below.
(b) Limit and speed $x_n\to L\ge\sqrt2\gt0$, and $L=\tfrac12(L+\tfrac2L)$ gives $L^2=2$, $L=\sqrt2$. Directly, $x_{n+1}-\sqrt2=\dfrac{x_n^2-2\sqrt2x_n+2}{2x_n}=\dfrac{(x_n-\sqrt2)^2}{2x_n}$: the error is squared at every step. Indeed $x_2=\tfrac32$, $x_3=\tfrac{17}{12}=1.41666\ldots$, $x_4=\tfrac{577}{408}=1.4142156\ldots$, while $\sqrt2=1.4142135\ldots$

Cauchy Sequences, Completeness and Contractive Sequences

The monotone convergence theorem needs monotonicity. To prove convergence of an oscillating sequence whose limit we do not know, we need a criterion that refers only to the terms themselves.

📘 Definition 2.4 — Cauchy sequence
$(a_n)$ is a Cauchy sequence if $$\forall\varepsilon\gt0\ \ \exists N\ \ \forall m,n\ge N:\quad|a_m-a_n|\lt\varepsilon .$$ Equivalently: for every $\varepsilon\gt0$ there is $N$ with $|a_{n+p}-a_n|\lt\varepsilon$ for all $n\ge N$ and all $p\in\mathbb{N}$ — the condition must hold uniformly in $p$, not just for $p=1$.
📐 Theorem 2.8 — Cauchy criterion (completeness of $\mathbb{R}$)
(a) Every convergent sequence is Cauchy. (b) Every Cauchy sequence is bounded. (c) Every Cauchy sequence of real numbers converges. Hence a real sequence converges if and only if it is Cauchy.

Proof. (a) If $a_n\to L$, choose $N$ with $|a_n-L|\lt\varepsilon/2$ for $n\ge N$; then for $m,n\ge N$, $|a_m-a_n|\le|a_m-L|+|L-a_n|\lt\varepsilon$.

(b) With $\varepsilon=1$ there is $N$ with $|a_n-a_N|\lt1$ for $n\ge N$, so $|a_n|\le M$ for all $n$, where $M=\max(|a_1|,\dots,|a_{N-1}|,\ |a_N|+1)$.

(c) Let $(a_n)$ be Cauchy, with $|a_n|\le M$ for all $n$. Consider $$S=\{x\in\mathbb{R}:\ x\lt a_n\text{ for infinitely many }n\}.$$ $S$ contains $-M-1$ and is bounded above by $M$ (no $x\ge M$ is below any $a_n$). By completeness $u=\sup S$ exists. We show $a_n\to u$. Let $\varepsilon\gt0$ and choose $N$ with $|a_m-a_n|\lt\varepsilon/2$ for $m,n\ge N$. Then for every $n\ge N$, $$a_N-\tfrac\varepsilon2\lt a_n\lt a_N+\tfrac\varepsilon2 .$$ The left inequality holds for infinitely many $n$, so $a_N-\varepsilon/2\in S$ and $u\ge a_N-\varepsilon/2$. If $x\ge a_N+\varepsilon/2$, then $x\lt a_n$ can hold only for some of the finitely many $n\lt N$, so $x\notin S$; thus every element of $S$ is $\lt a_N+\varepsilon/2$ and $u\le a_N+\varepsilon/2$. Hence $|u-a_N|\le\varepsilon/2$, and for $n\ge N$, $$|a_n-u|\le|a_n-a_N|+|a_N-u|\lt\tfrac\varepsilon2+\tfrac\varepsilon2=\varepsilon. \ ∎$$

The proof used the completeness axiom at exactly one point — the existence of $\sup S$. In $\mathbb{Q}$ the decimal truncations $1,\,1.4,\,1.41,\dots$ of $\sqrt2$ form a Cauchy sequence ($|a_m-a_n|\lt10^{-\min(m,n)+1}$) with no rational limit. Conversely, an Archimedean ordered field in which every Cauchy sequence converges is complete; this is why $\mathbb{R}$ can be constructed as the set of equivalence classes of rational Cauchy sequences. In §2.2 we give a second proof of (c) via the Bolzano–Weierstrass theorem, and in Chapter 7 the same definition defines complete metric spaces.

📘 Definition 2.5 — Contractive sequence
$(a_n)$ is contractive if there is a constant $c$ with $0\lt c\lt1$ such that $$|a_{n+2}-a_{n+1}|\le c\,|a_{n+1}-a_n|\quad\text{for all }n\in\mathbb{N}.$$ The constant $c$ must be the same for all $n$; "$|a_{n+2}-a_{n+1}|\lt|a_{n+1}-a_n|$" is not enough.
📐 Theorem 2.9 — Contractive sequences converge, with error bounds
Every contractive sequence is Cauchy, hence convergent. If $a_n\to a$ and $c$ is a contraction constant, then for every $n$ $$|a-a_n|\le\frac{c^{\,n-1}}{1-c}\,|a_2-a_1|\quad\text{(a priori)},\qquad |a-a_n|\le\frac{c}{1-c}\,|a_n-a_{n-1}|\quad\text{(a posteriori)}.$$

Proof. By induction $|a_{k+1}-a_k|\le c^{\,k-1}|a_2-a_1|$. For $m\gt n$, the triangle inequality and the geometric sum give $$|a_m-a_n|\le\sum_{k=n}^{m-1}|a_{k+1}-a_k|,$$ $$\sum_{k=n}^{m-1}|a_{k+1}-a_k|\le|a_2-a_1|\sum_{k=n}^{m-1}c^{\,k-1},$$ $$\text{so}\quad|a_m-a_n|\le\frac{c^{\,n-1}}{1-c}|a_2-a_1| .$$ Since $c^{\,n-1}\to0$ (Theorem 2.5(1)), $(a_n)$ is Cauchy and converges by Theorem 2.8; letting $m\to\infty$ in the display (Theorem 2.2(4)) gives the a priori bound. For the a posteriori bound, note $|a_{k+1}-a_k|\le c^{\,k-n+1}|a_n-a_{n-1}|$ for $k\ge n$, and sum: $|a-a_n|\le\sum_{k\ge n}|a_{k+1}-a_k|$, and this is $\le\dfrac{c}{1-c}|a_n-a_{n-1}|$. ∎

📐 Theorem 2.10 — Fixed-point iteration on an interval
Let $I$ be a closed interval (bounded or not) and $f:I\to I$ a contraction: $|f(x)-f(y)|\le c|x-y|$ for all $x,y\in I$, with a constant $0\le c\lt1$. Then $f$ has exactly one fixed point $x^\ast\in I$, and for every $x_1\in I$ the iterates $x_{n+1}=f(x_n)$ converge to $x^\ast$, with the error bounds of Theorem 2.9.

Proof. The iterates stay in $I$, and $|x_{n+2}-x_{n+1}|$ $=|f(x_{n+1})-f(x_n)|$ $\le c|x_{n+1}-x_n|$. If $c=0$ the sequence is constant from $n=2$; otherwise it is contractive and converges to some $x^\ast$ (Theorem 2.9). Since $I$ is closed, $x^\ast\in I$ (Theorem 2.2(4) applied to the end points). Next, $|f(x_n)-f(x^\ast)|\le c|x_n-x^\ast|\to0$, so $x_{n+1}=f(x_n)\to f(x^\ast)$, and by uniqueness of limits $f(x^\ast)=x^\ast$. If $y^\ast$ were another fixed point, $|x^\ast-y^\ast|=|f(x^\ast)-f(y^\ast)|\le c|x^\ast-y^\ast|$ forces $x^\ast=y^\ast$. ∎

This is the one-dimensional case of the Banach contraction principle (§7.1). By the mean value theorem (§3.3), a differentiable $f$ with $|f'(x)|\le c\lt1$ on $I$ is a contraction.

✏️ Example 5 — A contractive sequence that is not monotone
Let $x_1=1$ and $x_{n+1}=1+\dfrac1{x_n}$. Show that $(x_n)$ is not monotone, that it is contractive, and find its limit. How many terms does the a priori bound of Theorem 2.9 require for an error below $10^{-3}$, and what is the actual error of $x_{10}$?
Terms $1,\ 2,\ \tfrac32,\ \tfrac53,\ \tfrac85,\ \tfrac{13}8,\dots$ — ratios of consecutive Fibonacci numbers, $x_n=F_{n+1}/F_n$. They go up, down, up, …: not monotone, so Theorem 2.6 does not apply directly.
Contractive By induction $x_n\ge1$, so $x_nx_{n+1}=x_n\left(1+\tfrac1{x_n}\right)=x_n+1\ge2$. Then $$|x_{n+2}-x_{n+1}|=\left|\frac1{x_{n+1}}-\frac1{x_n}\right|=\frac{|x_n-x_{n+1}|}{x_nx_{n+1}}\le\frac12|x_{n+1}-x_n| .$$ So $(x_n)$ is contractive with $c=\tfrac12$ and converges to some $L\ge1$.
Limit $L=1+\tfrac1L$ (Theorem 2.2(2), $L\ne0$), so $L^2-L-1=0$ and $L=\dfrac{1+\sqrt5}2=1.6180339\ldots$, the golden ratio (the root $\tfrac{1-\sqrt5}2$ is negative).
Error A priori: $|L-x_n|\le\dfrac{(1/2)^{n-1}}{1/2}\cdot|2-1|=2^{2-n}\lt10^{-3}$ once $n\ge12$. Actually $x_{10}=\tfrac{89}{55}=1.6181818\ldots$ has error $1.48\times10^{-4}$, much better than the bound $2^{-8}=0.0039$ — the bound is safe, not sharp (a sharper $c$: $x_nx_{n+1}=x_n+1\ge2.5$ for $n\ge2$).
Remark $f(x)=1+\tfrac1x$ is not a contraction on $[1,2]$, since $|f'(1)|=1$; it is one on $[\tfrac32,2]$, which it maps into itself with $|f'|\le\tfrac49$. Working with the sequence directly avoided choosing the interval.
Interactive 2 — Cobweb Diagrams for $x_{n+1}=f(x_n)$

Left: the graph of $f$ and the diagonal $y=x$. From $x_n$ go up to $(x_n,f(x_n))$, then across to the diagonal: that is $x_{n+1}$. Right: the terms $x_n$ against $n$. A staircase means a monotone sequence; a spiral means an alternating, contractive one. The readout "ratio of steps" estimates the contraction constant $c$ of Theorem 2.9.

cobweb: $y=f(x)$ and $y=x$
terms $x_n$ against $n$
n—
xₙ—
|xₙ − xₙ₋₁|—
ratio of steps—
pattern—
✏️ Example 6 — Prove or disprove: Cauchy-type conditions
Prove or disprove: (a) if $a_{n+1}-a_n\to0$ then $(a_n)$ is Cauchy; (b) if $|a_{n+1}-a_n|\le2^{-n}$ for all $n$ then $(a_n)$ is Cauchy; (c) if $(a_n)$ and $(b_n)$ are Cauchy then $(a_nb_n)$ is Cauchy; (d) a Cauchy sequence of points of $(0,1)$ converges to a point of $(0,1)$.
(a) False $a_n=\sqrt n$: $a_{n+1}-a_n=\dfrac1{\sqrt{n+1}+\sqrt n}\to0$, but $(a_n)$ is unbounded, so not Cauchy (Theorem 2.8(b)). Similarly $H_n=1+\tfrac12+\cdots+\tfrac1n$ has $H_{2n}-H_n\ge n\cdot\tfrac1{2n}=\tfrac12$ for all $n$. The Cauchy condition must hold for all gaps $p$, not only $p=1$.
(b) True For $m\gt n$: $|a_m-a_n|\le\sum_{k=n}^{m-1}2^{-k}\lt2^{1-n}$, which is $\lt\varepsilon$ once $n$ is large (Theorem 2.5(1)). Summable step sizes force the Cauchy property.
(c) True Both are bounded, say by $M$ (Theorem 2.8(b)); then $|a_mb_m-a_nb_n|\le|a_m||b_m-b_n|+|b_n||a_m-a_n|\le M(|b_m-b_n|+|a_m-a_n|)$, which is small for $m,n$ large. (Or: both converge, so the product converges.)
(d) False $a_n=\tfrac1{n+1}\in(0,1)$ is Cauchy, but its limit $0$ is not in $(0,1)$. Being Cauchy depends only on distances between terms; whether a limit exists in the given set is a property of the set (completeness, Chapter 7). In $\mathbb{R}$ the limit always exists.
⚠️ Counterexamples and pitfalls
  1. Bounded does not imply convergent: $(-1)^n$. Bounded and monotone does.
  2. Small steps do not imply Cauchy: $\sqrt n$ and $H_n$ have $a_{n+1}-a_n\to0$ but diverge to $+\infty$.
  3. Decreasing steps are not a contraction: $\sqrt n$ has strictly decreasing steps $\sqrt{n+1}-\sqrt n$, yet diverges; a contraction needs one constant $c\lt1$.
  4. $|a_n|$ convergent, $a_n$ not: $(-1)^n$. The implication holds only when the limit is $0$.
  5. Products and sums of divergent sequences may converge: $(-1)^n\cdot(-1)^{n+1}=-1$, $(-1)^n+(-1)^{n+1}=0$.
  6. Strict inequalities become weak in the limit: $\tfrac1n\gt0$ for all $n$, but the limit is $0$.
  7. "$\infty-\infty$", "$\infty\cdot0$", "$1^\infty$" are not numbers: $\sqrt{n^2+n}-n\to\tfrac12$; $\left(1+\tfrac1n\right)^n\to e$, $\left(1+\tfrac1{n^2}\right)^n\to1$, $\left(1+\tfrac1n\right)^{n^2}\to+\infty$.
  8. Solving $L=f(L)$ first gives nonsense: $x_{n+1}=x_n^2+\tfrac14$ from $x_1=1$ diverges to $\infty$, although $L=\tfrac12$ solves $L=L^2+\tfrac14$. Prove existence first.
  9. Cauchy in a subset is not convergent in it: $\tfrac1{n+1}$ in $(0,1)$; decimal truncations of $\sqrt2$ in $\mathbb{Q}$.
  10. Divergent does not mean $\to\pm\infty$: $n(-1)^n$ is unbounded but neither tends to $+\infty$ nor to $-\infty$.
  11. The ratio criterion is silent at $\rho=1$: $1$, $\tfrac1n$, $n$ all have $a_{n+1}/a_n\to1$.
  12. Exponentials beat powers only eventually: $n^{10}/1.001^n\to0$, yet at $n=10^5$ it is still about $3.9\times10^6$.

Exercises

I
The definition of limit.
  • 1 Prove from the definition that $\dfrac{2n-1}{n+3}\to2$, and find the least $N$ that works for $\varepsilon=0.01$.
  • 2 Prove that $\dfrac{\sin n}{n}\to0$ and that $\left((-1)^n\dfrac{n}{n+1}\right)$ diverges.
  • 3 Prove: if $a_n\to a$ and $a\gt0$, then $a_n\gt a/2$ for all sufficiently large $n$.
  • 4 Prove: if $a_n\ge0$ and $a_n\to a$, then $\sqrt{a_n}\to\sqrt a$ (treat $a=0$ separately).
  • 5 Give divergent sequences $(a_n)$, $(b_n)$ such that both $(a_n+b_n)$ and $(a_nb_n)$ converge.
  • 6 Prove from Definition 2.2 that $\dfrac{n^2}{n+1}\to+\infty$ and that $\sqrt n-\sqrt{n+1}\to0$.
  • 7 Let $a_n\to a$. If $a_n\in[c,d]$ for all $n$, prove $a\in[c,d]$. If $a_n\in(c,d)$ for all $n$, must $a\in(c,d)$?
  • 8 Negate the definition of $a_n\to L$ in quantifier form. Use your negation to prove that $\left(\sin\frac{n\pi}{2}\right)$ does not converge to $0$.
1 $\left|\dfrac{2n-1}{n+3}-2\right|=\dfrac{7}{n+3}$. Given $\varepsilon$, choose $N\gt7/\varepsilon$; then $\tfrac7{n+3}\lt\tfrac7N\lt\varepsilon$ for $n\ge N$. For $\varepsilon=0.01$: $\tfrac7{n+3}\lt0.01\iff n\gt697$, so the least $N$ is $698$.
2 $\left|\tfrac{\sin n}{n}\right|\le\tfrac1n\to0$ (squeeze). For the second, the terms with even $n$ are $\tfrac{n}{n+1}\gt\tfrac12$ and those with odd $n$ are $\lt-\tfrac12$; if the limit were $L$, with $\varepsilon=\tfrac12$ an even and an odd term beyond $N$ would give $1\lt|a_{2k}-a_{2k+1}|\lt2\varepsilon=1$. Contradiction.
3 Take $\varepsilon=a/2\gt0$: eventually $|a_n-a|\lt a/2$, so $a_n\gt a-a/2=a/2$. (A convergent sequence eventually has the sign of a nonzero limit.)
4 See Theorem 2.2(3): for $a\gt0$, $|\sqrt{a_n}-\sqrt a|\le|a_n-a|/\sqrt a$; for $a=0$, given $\varepsilon$, eventually $a_n\lt\varepsilon^2$, so $\sqrt{a_n}\lt\varepsilon$.
5 $a_n=(-1)^n$, $b_n=(-1)^{n+1}$: $a_n+b_n=0$, $a_nb_n=-1$.
6 $\tfrac{n^2}{n+1}\ge\tfrac{n^2-1}{n+1}=n-1\gt M$ for $n\gt M+1$. And $|\sqrt n-\sqrt{n+1}|=\tfrac1{\sqrt n+\sqrt{n+1}}\lt\tfrac1{\sqrt n}\lt\varepsilon$ for $n\gt1/\varepsilon^2$.
7 Theorem 2.2(4) with constant sequences $c\le a_n\le d$ gives $c\le a\le d$. No: $a_n=\tfrac1n\in(0,2)$ but $a=0\notin(0,2)$.
8 $a_n\not\to L$ iff $\exists\varepsilon\gt0\ \forall N\ \exists n\ge N:\ |a_n-L|\ge\varepsilon$. For $a_n=\sin\tfrac{n\pi}2$ and $L=0$ take $\varepsilon=1$: for any $N$, $n=4N+1\ge N$ has $|a_n|=1$.
II
Computing limits. Find each limit (or show that the sequence diverges to $+\infty$).
  • 1 $\dfrac{5n^3-2n+7}{2n^3+n^2}$
  • 2 $\sqrt n\left(\sqrt{n+1}-\sqrt n\right)$
  • 3 $(3^n+5^n+7^n)^{1/n}$
  • 4 $\dfrac{n^2}{(1.01)^n}$
  • 5 $\dfrac{2^n\,n!}{n^n}$
  • 6 $(n^2+2n)^{1/n}$
  • 7 $\displaystyle\sum_{k=1}^n\frac{1}{\sqrt{n^2+k}}$
  • 8 $\left(1+\dfrac1n\right)^{2n}$ and $\left(1-\dfrac1n\right)^n$
  • 9 $(n!)^{1/n}$
1 Divide by $n^3$: $\dfrac{5-2/n^2+7/n^3}{2+1/n}\to\dfrac52$.
2 $\dfrac{\sqrt n}{\sqrt{n+1}+\sqrt n}=\dfrac1{\sqrt{1+1/n}+1}\to\dfrac12$.
3 $7^n\le3^n+5^n+7^n\le3\cdot7^n$, so the $n$-th root lies between $7$ and $3^{1/n}\cdot7\to7$: limit $7$.
4 Ratio $\tfrac1{1.01}\left(1+\tfrac1n\right)^2\to\tfrac1{1.01}\lt1$: limit $0$ (Theorem 2.5(4)).
5 $\dfrac{a_{n+1}}{a_n}=\dfrac{2(n+1)\,n^n}{(n+1)^{n+1}}=\dfrac{2}{(1+1/n)^n}\to\dfrac2e\approx0.736\lt1$: limit $0$.
6 $n^2\le n^2+2n\le3n^2$, so $(n^{1/n})^2\le(n^2+2n)^{1/n}\le3^{1/n}(n^{1/n})^2$; both bounds $\to1$: limit $1$.
7 $\dfrac{n}{\sqrt{n^2+n}}\le\text{sum}\le\dfrac{n}{\sqrt{n^2+1}}$, both $\to1$: limit $1$ (for $n=1000$ the sum is $0.99975\ldots$).
8 $\left(1+\tfrac1n\right)^{2n}=e_n^2\to e^2$. And $\left(1-\tfrac1n\right)^n=\left(\tfrac{n-1}{n}\right)^n=\dfrac{1}{\left(1+\frac1{n-1}\right)^{n-1}\left(1+\frac1{n-1}\right)}\to\dfrac1{e\cdot1}=\dfrac1e$ (for $n\ge2$).
9 The last $\lceil n/2\rceil$ factors of $n!$ are each $\ge n/2$, so $n!\ge(n/2)^{n/2}$ and $(n!)^{1/n}\ge\sqrt{n/2}\to\infty$: $(n!)^{1/n}\to+\infty$. (In §2.2 we find the sharper $(n!)^{1/n}/n\to1/e$.)
III
Monotone and recursive sequences; the number $e$.
  • 1 $a_1=1$, $a_{n+1}=\dfrac{2a_n+3}{4}$. Prove that $(a_n)$ is increasing and bounded, and find its limit.
  • 2 $a_1=\sqrt2$, $a_{n+1}=\sqrt{2a_n}$. Prove convergence and find the limit.
  • 3 $a_1=3$, $a_{n+1}=2-\dfrac1{a_n}$. Prove that $(a_n)$ is decreasing and bounded below, find the limit, and find a closed formula for $a_n$.
  • 4 $a_1=1$, $a_{n+1}=a_n+\dfrac1{a_n}$. Prove that $a_n\to+\infty$.
  • 5 Prove that $b_n=\left(1+\tfrac1n\right)^{n+1}$ is decreasing, deduce $e_n\lt e\lt b_n$ for all $n$, and use $n=5$ to show $2.48\lt e\lt2.99$.
  • 6 Use Theorem 2.7(d) to prove that $e$ is irrational.
  • 7 $x_{n+1}=x_n^2+\tfrac14$. Prove that $x_n\to\tfrac12$ if $x_1=0$, and $x_n\to+\infty$ if $x_1=1$.
  • 8 Applied. A patient takes $100$ mg of a drug every $12$ hours, and $60\%$ of the drug in the body is eliminated between doses. Let $a_n$ be the amount just after the $n$-th dose, so $a_1=100$ and $a_{n+1}=0.4a_n+100$. Prove that $(a_n)$ increases to a limit, find it, and find the first dose after which the amount is within $1$ mg of the limit.
1 Induction: $a_n\lt\tfrac32\Rightarrow a_{n+1}\lt\tfrac{3+3}4=\tfrac32$. Then $a_{n+1}-a_n=\tfrac{3-2a_n}{4}\gt0$. Limit: $L=\tfrac{2L+3}4\Rightarrow L=\tfrac32$.
2 $a_n\lt2\Rightarrow a_{n+1}=\sqrt{2a_n}\lt2$; and $a_{n+1}^2-a_n^2=a_n(2-a_n)\gt0$. So $a_n\uparrow L\in[\sqrt2,2]$ with $L^2=2L$, $L=2$. (Here $a_n=2^{1-2^{-n}}$.)
3 If $a_n\gt1$ then $a_{n+1}=2-\tfrac1{a_n}\gt1$; and $a_n-a_{n+1}=\dfrac{a_n^2-2a_n+1}{a_n}=\dfrac{(a_n-1)^2}{a_n}\gt0$. So $a_n\downarrow L\ge1$ with $L=2-\tfrac1L$, i.e. $(L-1)^2=0$: $L=1$. Formula: $a_n=\dfrac{2n+1}{2n-1}$ (check: $2-\tfrac{2n-1}{2n+1}=\tfrac{2n+3}{2n+1}$), which visibly tends to $1$ — slowly, because $f'(1)=1$.
4 $a_{n+1}-a_n=\tfrac1{a_n}\gt0$: increasing. If it were bounded it would converge to some $L\ge1$ with $L=L+\tfrac1L$, impossible. An unbounded increasing sequence tends to $+\infty$ (Theorem 2.6). (In fact $a_n\sim\sqrt{2n}$, §2.2.)
5 $\dfrac{b_{n-1}}{b_n}=\left(\dfrac{n^2}{n^2-1}\right)^n\dfrac{n}{n+1}=\left(1+\dfrac1{n^2-1}\right)^n\dfrac n{n+1}\ge\left(1+\dfrac{n}{n^2-1}\right)\dfrac n{n+1}\gt\left(1+\dfrac1n\right)\dfrac n{n+1}=1$ (Bernoulli, then $\tfrac n{n^2-1}\gt\tfrac1n$). So $b_n$ decreases, $b_n=e_n(1+\tfrac1n)\to e$, hence $e_n\lt e\lt b_n$ (strict since both are strictly monotone). $n=5$: $e_5=1.2^5=2.48832$, $b_5=1.2^6=2.985984$.
6 If $e=p/q$ with $p,q\in\mathbb{N}$, multiply $0\lt e-s_q\lt\tfrac1{q!\,q}$ by $q!$: $0\lt q!\,e-q!\,s_q\lt\tfrac1q\le1$. But $q!\,e=p\,(q-1)!$ and $q!\,s_q=\sum_{k\le q}q!/k!$ are integers, and no integer lies strictly between $0$ and $1$.
7 $f(x)=x^2+\tfrac14$, $f(x)-x=(x-\tfrac12)^2\ge0$, so $(x_n)$ is always increasing. If $x_1=0$: $0\le x_n\lt\tfrac12\Rightarrow x_{n+1}\lt\tfrac14+\tfrac14=\tfrac12$, so $x_n\uparrow L\le\tfrac12$ with $L=L^2+\tfrac14$, $L=\tfrac12$ (very slowly: the error is about $1/n$). If $x_1=1$: $x_n\ge1$ for all $n$ and $x_{n+1}-x_n=(x_n-\tfrac12)^2\ge\tfrac14$, so $x_n\ge1+\tfrac{n-1}4\to\infty$.
8 $a_n\lt\tfrac{500}3\Rightarrow a_{n+1}\lt0.4\cdot\tfrac{500}3+100=\tfrac{500}3$, and $a_{n+1}-a_n=100-0.6a_n\gt0$. Limit: $L=0.4L+100$, $L=\tfrac{500}3\approx166.67$ mg. Explicitly $L-a_n=\tfrac{200}{3}(0.4)^{n-1}$: after dose 5 the gap is $1.71$ mg, after dose 6 it is $0.68$ mg. So from the 6th dose (about $2.5$ days) on, the level is within $1$ mg of the steady state.
IV
Cauchy and contractive sequences.
  • 1 Show directly from Definition 2.4 that $\left(\dfrac{n+1}{n}\right)$ is Cauchy.
  • 2 Prove that $H_n=\sum_{k=1}^n\frac1k$ is not Cauchy, and deduce $H_n\to+\infty$.
  • 3 Prove that $x_n=\sum_{k=1}^n\frac1{k^2}$ is Cauchy, using $\frac1{k^2}\lt\frac1{k-1}-\frac1k$ for $k\ge2$.
  • 4 Prove that $x_n=\sum_{k=1}^n\frac{(-1)^{k+1}}k$ is Cauchy, by showing $|x_m-x_n|\le\frac1{n+1}$ for $m\gt n$.
  • 5 Prove: if $|x_{n+1}-x_n|\le r^n$ for some $0\lt r\lt1$ and all $n$, then $(x_n)$ is Cauchy. Give an example with $|x_{n+1}-x_n|\le\frac1n$ that is not Cauchy.
  • 6 $x_1=1$, $x_{n+1}=\dfrac1{2+x_n}$. Prove that $(x_n)$ is contractive with $c=\tfrac14$ and find its limit.
  • 7 $x_1=0$, $x_{n+1}=\cos x_n$. Using $|\cos x-\cos y|\le\sin1\cdot|x-y|$ on $[0,1]$ (mean value theorem, §3.3), prove convergence. How many iterations does the a priori bound require for an error below $10^{-6}$? (The limit is $0.739085\ldots$)
  • 8 Prove that a Cauchy sequence of integers is eventually constant. Give a Cauchy sequence of rationals with no limit in $\mathbb{Q}$.
1 $\left|\tfrac{m+1}m-\tfrac{n+1}n\right|=\left|\tfrac1m-\tfrac1n\right|\le\max\left(\tfrac1m,\tfrac1n\right)\le\tfrac1N\lt\varepsilon$ for $m,n\ge N\gt1/\varepsilon$.
2 $H_{2n}-H_n=\sum_{k=n+1}^{2n}\tfrac1k\ge n\cdot\tfrac1{2n}=\tfrac12$: with $\varepsilon=\tfrac12$ no $N$ works. So $(H_n)$ diverges; being increasing, it is unbounded and tends to $+\infty$ (Theorem 2.6).
3 For $m\gt n\ge1$: $0\lt x_m-x_n=\sum_{k=n+1}^m\tfrac1{k^2}\lt\sum_{k=n+1}^m\left(\tfrac1{k-1}-\tfrac1k\right)=\tfrac1n-\tfrac1m\lt\tfrac1n$. (The limit is $\pi^2/6$, §2.3.)
4 $x_m-x_n=\pm\left(\tfrac1{n+1}-\tfrac1{n+2}+\tfrac1{n+3}-\cdots\right)$ (finitely many terms). Grouping in pairs $\left(\tfrac1{n+1}-\tfrac1{n+2}\right)+\cdots$ shows the bracket is $\ge0$; grouping as $\tfrac1{n+1}-\left(\tfrac1{n+2}-\tfrac1{n+3}\right)-\cdots$ shows it is $\le\tfrac1{n+1}$. So $|x_m-x_n|\le\tfrac1{n+1}$. (The limit is $\log2$, §2.3.)
5 $|x_m-x_n|\le\sum_{k=n}^{m-1}r^k\lt\dfrac{r^n}{1-r}\to0$. Example: $H_n$ has steps $\tfrac1{n+1}\le\tfrac1n$ but is not Cauchy (part 2).
6 All $x_n\gt0$, so $|x_{n+2}-x_{n+1}|=\left|\tfrac1{2+x_{n+1}}-\tfrac1{2+x_n}\right|=\dfrac{|x_n-x_{n+1}|}{(2+x_n)(2+x_{n+1})}\le\tfrac14|x_{n+1}-x_n|$. Limit: $L(2+L)=1$, $L=\sqrt2-1\approx0.41421$ (the positive root).
7 $\cos$ maps $[0,1]$ into $[\cos1,1]\subseteq[0,1]$ and is a contraction there with $c=\sin1\approx0.8415$; Theorem 2.10 applies. A priori: $|x-x_n|\le\dfrac{c^{\,n-1}}{1-c}|x_2-x_1|=\dfrac{c^{\,n-1}}{1-c}$ (as $x_2=1$), which is $\lt10^{-6}$ iff $n-1\gt\dfrac{\log(10^{-6}(1-c))}{\log c}\approx90.7$, i.e. $n\ge92$. (In practice far fewer iterations are needed: near the fixed point the true contraction factor is $\sin(0.739)\approx0.67$.)
8 With $\varepsilon=\tfrac12$: for $m,n\ge N$, $|a_m-a_n|\lt\tfrac12$ and $a_m-a_n\in\mathbb{Z}$, so $a_m=a_n$. The decimal truncations $1,\ 1.4,\ 1.41,\ 1.414,\dots$ of $\sqrt2$ are rational and Cauchy ($|a_m-a_n|\le10^{1-\min(m,n)}$), but their real limit $\sqrt2$ is irrational.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA $\displaystyle\lim_{n\to\infty}\left(1+\frac1{n^2}\right)^{n}$ equals (A) $0$; (B) $1$; (C) $e$; (D) $\sqrt e$.

Idea "$1^\infty$" is not automatically $e$; squeeze with the binomial theorem.
Work $1\le\left(1+\tfrac1{n^2}\right)^n=\sum_{k=0}^n\binom nk n^{-2k}\le\sum_{k=0}^n\frac{n^k}{k!}n^{-2k}\le\sum_{k=0}^{n}n^{-k}\lt\dfrac{1}{1-1/n}\to1$ (for $n\ge2$). By the squeeze theorem the limit is $1$. (Numerically, $n=1000$ gives $1.0010005$.)
Answer (B).

E2. CSIR Part B Let $x_1=1$ and $x_{n+1}=\dfrac{x_n}2+\dfrac1{x_n}$. Then (A) $(x_n)$ is increasing; (B) $(x_n)$ is decreasing; (C) $x_n\to\sqrt2$; (D) $x_n\to2$.

Idea This is the Babylonian recursion $x_{n+1}=\tfrac12(x_n+\tfrac2{x_n})$ started below $\sqrt2$.
Work $x_2=\tfrac32\gt x_1$, but by AM–GM $x_n\ge\sqrt2$ for $n\ge2$, and then $x_{n+1}\le x_n$ (Example 4(b)): $x_3=\tfrac{17}{12}\lt x_2$. So the sequence is neither increasing nor decreasing — (A), (B) fail — but it is decreasing from $n=2$ on and converges to $\sqrt2$; (D) fails.
Answer (C).

E3. CSIR Part B Which of the following sequences is Cauchy? (A) $a_n=\sum_{k=1}^n\frac1k$; (B) $a_n=\sqrt n$; (C) $a_n=\sum_{k=0}^n\frac1{k!}$; (D) $a_n=(-1)^n+\frac1n$.

Idea In $\mathbb{R}$, Cauchy $\iff$ convergent.
Work (A) and (B) are unbounded (Exercise IV.2); (D) has $|a_{n+1}-a_n|\ge2-\tfrac2n\ge1$ for $n\ge2$; (C) increases to $e$ (Theorem 2.7), so it converges.
Answer (C).

E4. CSIR Part C Let $(a_n)$, $(b_n)$ be real sequences. Which of the following are true? (One or more options may be correct.) (A) If $a_n\to0$ and $(b_n)$ is bounded, then $a_nb_n\to0$. (B) If $a_{n+1}-a_n\to0$, then $(a_n)$ converges. (C) If $(a_n^2)$ converges, then $(a_n)$ converges. (D) If $(a_n)$ is monotone and $(a_n^2)$ converges, then $(a_n)$ converges.

(A) True $|a_nb_n|\le M|a_n|\to0$.
(B) False $a_n=\sqrt n$ (or $H_n$).
(C) False $a_n=(-1)^n$: $a_n^2=1$.
(D) True $(a_n^2)$ convergent ⇒ bounded, so $|a_n|$ is bounded; a bounded monotone sequence converges (Theorem 2.6).
Answer (A) and (D).

E5. CSIR Part C Let $x_{n+1}=\dfrac{x_n^2+2}{3}$. Which of the following are true? (A) If $x_1=1.5$, then $x_n\to1$. (B) If $x_1=0$, then $(x_n)$ is increasing and $x_n\to1$. (C) If $x_1=3$, then $(x_n)$ is bounded. (D) If $x_1=-2$, then $x_n\to2$.

Idea Fixed points: $L=\tfrac{L^2+2}3\iff(L-1)(L-2)=0$. Sign: $f(x)-x=\tfrac{(x-1)(x-2)}3$. Also $f$ is increasing on $[0,\infty)$, so it maps $[0,1]$ into $[\tfrac23,1]$, $[1,2]$ into $[1,2]$, and $(2,\infty)$ into $(2,\infty)$.
(A) True On $(1,2)$: $f(x)\lt x$ and $f(x)\gt1$, so $(x_n)$ decreases and is bounded below by $1$; its limit is a fixed point $\le1.5$, i.e. $1$. ($x_2=1.4167$, $x_3=1.3356,\dots$)
(B) True On $[0,1)$: $f(x)\gt x$ and $f(x)\lt1$, so $(x_n)$ increases, is bounded by $1$, and tends to $1$. ($x_2=\tfrac23$, $x_3=0.8148,\dots$)
(C) False On $(2,\infty)$: $f(x)\gt x$, so $(x_n)$ increases; if it were bounded its limit would be a fixed point $\ge3$ — there is none. So $x_n\to\infty$ ($3,\ 3.67,\ 5.15,\ 9.50,\dots$).
(D) True $x_2=\tfrac{4+2}3=2$, a fixed point: the sequence is $-2,2,2,2,\dots\to2$. A trap — the repelling fixed point is reached exactly.
Answer (A), (B) and (D).

E6. CSIR Part C Which of the following are true? (A) $n^{1/n}\to1$. (B) $(2^n+n^5)^{1/n}\to1$. (C) $\left(1+\frac1n\right)^{n^2}\to e$. (D) $\dfrac{n^{10}}{(1.001)^n}\to0$.

(A) True Theorem 2.5(3).
(B) False $2^n\le2^n+n^5\le2\cdot2^n$ for $n\ge23$ (when $n^5\le2^n$), so the root tends to $2$.
(C) False $\left(1+\tfrac1n\right)^{n^2}=e_n^{\,n}\ge2^n\to\infty$.
(D) True Theorem 2.5(4) with $a=1.001\gt1$ — even though the terms are huge for a long time.
Answer (A) and (D).
🧑‍🏫 For the teacher

Suggested plan — 2 lectures × 60 min (a third for practice with recursive sequences).

  1. Convergence and the algebra of limits. Definition 2.1 with the quantifier order spelled out; Example 1 on the board, then project Interactive 1 — first $(3n+1)/(2n+5)$ (watch $N(\varepsilon)$ grow), then $(-1)^n$ (no $N$ for $\varepsilon\le1$). Theorem 2.1 and Theorem 2.2 (prove the product rule in full), squeeze theorem, Theorem 2.5 with the Bernoulli/binomial proofs, Example 2 (b), (d). End with Example 3 as a quick class poll.
  2. Existence theorems. Monotone convergence theorem (stress the one use of completeness), Theorem 2.7 on $e$, the strategy box and Example 4. Cauchy sequences: Theorem 2.8 with the "$S$" proof, then Definition 2.5, Theorem 2.9 and Example 5; project Interactive 2 with $\sqrt{2+x}$ (staircase) and $1+1/x$ (spiral), then $x^2+\tfrac14$ (slow, non-contractive) and the logistic map (no limit). Finish with E2 and E5.

Discussion questions. (1) Does $N$ depend on $\varepsilon$, on $n$, or on both? What would it mean if one $N$ worked for every $\varepsilon$? (2) Which theorems of this section are false in $\mathbb{Q}$, and why exactly? (3) Is "$|a_{n+1}-a_n|\to0$" closer to "Cauchy" or to "bounded"? Find the weakest extra condition that makes it imply convergence.

Misconceptions to watch for. Choosing $N$ before $\varepsilon$; treating $\infty$ as a number ($\infty-\infty=0$, $1^\infty=1$); solving $L=f(L)$ without proving the limit exists; believing every bounded sequence converges; confusing the sequence with its set of values; reading "Cauchy" as a condition on consecutive terms only; forgetting that the contraction constant must be uniform.

Suggested homework. I(1, 3, 7, 8), II(2, 3, 5, 8, 9), III(1, 3, 5, 6, 8), IV(2, 4, 6, 7); Exam corner E1, E4, E5.

🔬 Research–Teaching NexusResearch-tutored · optional, about 45 minutes

Research question. For which values of the growth parameter $r$ does the population model $x_{n+1}=r\,x_n(1-x_n)$ converge, and what does it do when it does not?

Why it matters. This "logistic map" is the simplest model of a population with limited resources — insects, fish stocks, bacteria in a culture — measured as a fraction $x_n\in[0,1]$ of the carrying capacity. In a celebrated 1976 survey the ecologist Robert May showed that this innocent recursion can settle to a steady state, oscillate between two or four values, or behave chaotically, depending only on $r$. Fisheries managers and epidemiologists still use it to explain why populations can fluctuate wildly without any outside cause.

What to do.

  1. Find the fixed points of $f(x)=rx(1-x)$ and show that for $1\lt r\lt3$ the nonzero one, $x^\ast=1-\tfrac1r$, satisfies $|f'(x^\ast)|=|2-r|\lt1$. Explain, using Theorem 2.10 on a small interval around $x^\ast$, why iterates that come close to $x^\ast$ converge to it.
  2. Iterate (Interactive 2, or $10$ lines of Python) for $r=2.5$, $3.2$, $3.5$, $3.9$ from $x_1=0.2$. Record the long-run behaviour.
  3. For $r=3.2$, find the two values of the 2-cycle exactly by solving $f(f(x))=x$ and discarding the fixed points.
  4. Locate numerically the values $r_1=3\lt r_2\lt r_3$ at which the period doubles ($1\to2\to4\to8$) and compute $(r_2-r_1)/(r_3-r_2)$.

Tools: Python or a spreadsheet; the cobweb widget above (option "3.2 x(1 − x)").

Hand in: A one-page note with a table of $r$ against the long-run behaviour, your exact 2-cycle for $r=3.2$, and one paragraph explaining in terms of Theorem 2.9 why convergence is lost at $r=3$.

Going further. Read about the Feigenbaum constant $\delta\approx4.669$, which governs the period-doubling cascade of every smooth "one-hump" map, and about why it was a surprise that such a universal constant exists.

Instructor note: for $r=2.5$ the iterates converge to $0.6$; for $r=3.2$ they approach the 2-cycle $\dfrac{r+1\pm\sqrt{(r+1)(r-3)}}{2r}$, i.e. $0.5130$ and $0.7995$; for $r=3.5$ a 4-cycle $\approx0.3828,\ 0.8269,\ 0.5009,\ 0.8750$; for $r=3.9$ no pattern (chaos). At $r=3$, $|f'(x^\ast)|=1$ and the contraction estimate fails. $r_2=1+\sqrt6\approx3.4495$, $r_3\approx3.5441$, so the first ratio is $\approx4.75$, already close to $\delta$.

🧪 Self-check quiz

0/5 correct

Q1. Which statement means $a_n\to L$?

Q2. $\lim_{n\to\infty}n^{1/n}$ equals

Q3. An increasing sequence that is bounded above

Q4. Which sequence is not Cauchy?

Q5. If $a_1=1$ and $a_{n+1}=\sqrt{2+a_n}$, then $\lim a_n$ is