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
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$.
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.
The Algebra of Limits, the Squeeze Theorem and Standard Limits
- $a_n+b_n\to a+b$, $\ ca_n\to ca$, $\ a_nb_n\to ab$;
- if $b\ne0$, then $b_n\ne0$ eventually and $a_n/b_n\to a/b$ (over the indices where $b_n\ne0$);
- $|a_n|\to|a|$; and if $a_n\ge0$ for all $n$, then $a\ge0$ and $\sqrt{a_n}\to\sqrt a$;
- (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.
(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. ∎
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)$. ∎
- $a^n\to0$ if $|a|\lt1$; $\ a^n\to+\infty$ if $a\gt1$; $(-1)^n$ and $a^n$ for $a\lt-1$ diverge.
- $a^{1/n}\to1$ for every $a\gt0$.
- $n^{1/n}\to1$.
- $\dfrac{n^k}{a^n}\to0$ for every fixed $k\in\mathbb{N}$ and $a\gt1$ ("exponentials beat powers").
- $\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$. ∎
Monotone Sequences, the Number $e$ and Recursive Sequences
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.
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).
- Compute the first few terms and guess the behaviour (increasing? alternating?) and the candidate limits: the solutions of $L=f(L)$.
- Bound by induction: show all $a_n$ lie in an interval $I$ (usually with the candidate limit as an end point).
- 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.
- 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.
- 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).
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.
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.
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}|$. ∎
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.
- Bounded does not imply convergent: $(-1)^n$. Bounded and monotone does.
- Small steps do not imply Cauchy: $\sqrt n$ and $H_n$ have $a_{n+1}-a_n\to0$ but diverge to $+\infty$.
- 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$.
- $|a_n|$ convergent, $a_n$ not: $(-1)^n$. The implication holds only when the limit is $0$.
- Products and sums of divergent sequences may converge: $(-1)^n\cdot(-1)^{n+1}=-1$, $(-1)^n+(-1)^{n+1}=0$.
- Strict inequalities become weak in the limit: $\tfrac1n\gt0$ for all $n$, but the limit is $0$.
- "$\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$.
- 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.
- Cauchy in a subset is not convergent in it: $\tfrac1{n+1}$ in $(0,1)$; decimal truncations of $\sqrt2$ in $\mathbb{Q}$.
- Divergent does not mean $\to\pm\infty$: $n(-1)^n$ is unbounded but neither tends to $+\infty$ nor to $-\infty$.
- The ratio criterion is silent at $\rho=1$: $1$, $\tfrac1n$, $n$ all have $a_{n+1}/a_n\to1$.
- 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
- 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 $\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 $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 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}$.
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$.
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$.
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$.
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.
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$.
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$.
Suggested plan — 2 lectures × 60 min (a third for practice with recursive sequences).
- 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.
- 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 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.
- 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.
- 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.
- For $r=3.2$, find the two values of the 2-cycle exactly by solving $f(f(x))=x$ and discarding the fixed points.
- 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.
🧪 Self-check quiz
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