Mathematical Induction

The template for a proof by mathematical induction:

Define a statement $𝑃(𝑛)$ that depends on the positive integer $𝑛$ .
Base case. Prove $𝑃(1)$ .
Inductive step. Assuming $𝑃(𝑘)$ for some $𝑘\geq 1$ , prove $𝑃(𝑘+1)$ .

Theorem 1.3The principle of mathematical induction

A set of positive integers that contains the integer $1$ , and that has the property that, if it contains $𝑘$ , then it also contains $𝑘+1$ , must be set of all the positive integers.

In symbols: Let $𝑆\subseteq {\mathbb{Z}}^{+}$ with $1\in 𝑆$ . If $𝑆$ has the property that

𝑘\in {\mathbb{Z}}^{+},\quad 𝑘\in 𝑆\quad ⟹\quad 𝑘+1\in 𝑆,

then $𝑆={\mathbb{Z}}^{+}$ .

Back to the template. The theory behind this proof technique is that we define

𝑆=\{𝑛\in {\mathbb{Z}}^{+}:𝑃(𝑛)\, \text{ holds}\}

and use the principle to conclude that $𝑆={\mathbb{Z}}^{+}$ . Equivalently, $𝑃(𝑛)$ holds for all $𝑛\in {\mathbb{Z}}^{+}$ .

The proof will mainly make use of the well-ordering principle.

Proof

We prove by contradiction. Assume $𝑆\neq {\mathbb{Z}}^{+}$ . Equivalently, the complement ${\mathbb{Z}}^{+}∖𝑆$ is nonempty. Since ${\mathbb{Z}}^{+}∖𝑆\subseteq {\mathbb{Z}}^{+}$ and ${\mathbb{Z}}^{+}∖𝑆\neq \emptyset$ , the well-ordering principle Axiom 1.1 gives a least element $𝑛\in {\mathbb{Z}}^{+}∖𝑆$ .

Then $𝑛>1$ , because $1\in 𝑆$ , and hence $𝑛-1\in {\mathbb{Z}}^{+}$ . The property of $𝑆$ forces $𝑛-1\notin 𝑆$ : otherwise $𝑛\in 𝑆$ , which is absurd. So $𝑛-1\in {\mathbb{Z}}^{+}∖𝑆$ , contradicting that $𝑛$ is the least element of ${\mathbb{Z}}^{+}∖𝑆$ . Therefore the assumption is false, and $𝑆={\mathbb{Z}}^{+}$ .

Exercise 1.1

Use mathematical induction to prove

\sum _{𝑗=1}^{𝑛}{𝑗}^{2}=\frac{𝑛(𝑛+1)(2𝑛+1)}{6}

Proof

Let $𝑃(𝑛)$ be the statement that the equation holds for $𝑛$ .

Base case. When $𝑛=1$ , the LHS is ${1}^{2}=1$ and the RHS is $1\cdot (1+1)\cdot (2\cdot 1+1)/6=1$ . Thus, $𝑃(1)$ holds.

Inductive step. Assume $𝑃(𝑘)$ . Consider $𝑛=𝑘+1$ . On the LHS, we have

\begin{aligned}\sum _{𝑗=1}^{𝑘+1}{𝑗}^{2} & = & & \sum _{𝑗=1}^{𝑘}{𝑗}^{2}+{(𝑘+1)}^{2} \\ & & & \text{Apply }\, 𝑃(𝑘)\, \text{ to }\sum _{𝑗=1}^{𝑘}{𝑗}^{2} \\ & = & & \frac{𝑘(𝑘+1)(2𝑘+1)}{6}+{(𝑘+1)}^{2} \\ & = & & \frac{𝑘+1}{6}\cdot [𝑘(2𝑘+1)+(𝑘+1)] \\ & = & & \frac{𝑘+1}{6}\cdot (2{𝑘}^{2}+7𝑘+6) \\ & = & & \frac{𝑘+1}{6}\cdot (𝑘+2)(2𝑘+3) \\ & = & & \frac{(𝑘+1)(𝑘+2)(2(𝑘+1)+1)}{6}.\end{aligned}

Note that the RHS is exactly the expression of the RHS of the equation to prove when $𝑛=𝑘+1$ . Therefore, we have shown that $𝑃(𝑘+1)$ also holds.

By mathematical induction, we claim that $𝑃(𝑛)$ holds for all $𝑛\in {\mathbb{Z}}^{+}$ .

There is a variant we call the second principle of mathematical induction. It is often useful when we feel that $𝑃(𝑘)$ alone is not enough, and we need $𝑃(1),\ldots ,𝑃(𝑘)$ to prove $𝑃(𝑘+1)$ . The usual template is then:

Define a statement $𝑃(𝑛)$ that depends on the positive integer $𝑛$ .
Base case. Prove $𝑃(1)$ .
Inductive step. Assuming $𝑃(1),\ldots ,𝑃(𝑘)$ all hold for some $𝑘\geq 1$ , prove $𝑃(𝑘+1)$ .

Of course, we can always reduce the second template to the first by altering the statement itself, but that is a more roundabout way to think.

Theorem 1.4The second principle of mathematical induction

A set of positive integers that contains the integer $1$ , and for every positive integer $𝑘$ , if it contains $1,\ldots ,𝑘$ , then it also contains $𝑘+1$ , must be set of all the positive integers.

In symbols: Let $𝑆\subseteq {\mathbb{Z}}^{+}$ with $1\in 𝑆$ . If $𝑆$ has the property that

𝑘\in {\mathbb{Z}}^{+},\quad \{1,\ldots ,𝑘\}\subseteq 𝑆\quad ⟹\quad 𝑘+1\in 𝑆,

then $𝑆={\mathbb{Z}}^{+}$ .

The proof is almost the same as that of the first principle of mathematical induction, except for a tiny difference in how we argue the contradiction.

Proof

We prove by contradiction. Assume $𝑆\neq {\mathbb{Z}}^{+}$ . Equivalently, ${\mathbb{Z}}^{+}∖𝑆\neq \emptyset$ . Since ${\mathbb{Z}}^{+}∖𝑆\subseteq {\mathbb{Z}}^{+}$ and ${\mathbb{Z}}^{+}∖𝑆\neq \emptyset$ , the well-ordering principle gives a least element $𝑛\in {\mathbb{Z}}^{+}∖𝑆$ .

Now, $𝑛\geq 2$ . Since $𝑛\notin 𝑆$ , there must exist $𝑚\in \{1,\ldots ,𝑛-1\}$ such that $𝑚\notin 𝑆$ . Otherwise, by the property of $𝑆$ , it would mean that $𝑛\in 𝑆$ , which is not the case. So, $𝑚\in {\mathbb{Z}}^{+}∖𝑆$ , contradicting that $𝑛$ the least element of ${\mathbb{Z}}^{+}∖𝑆$ . Therefore the assumption is false, and $𝑆={\mathbb{Z}}^{+}$ .

We can also prove Theorem 1.4 by mathematical induction since we have already proved the first principle Theorem 1.3.

Proof

Let $𝑃(𝑛)$ be the statement that $𝑆$ contains all positive integers less than or equal to $𝑛$ , i.e. $𝑚\in 𝑆$ for all $𝑚\leq 𝑛$ .

Base case. $𝑛=1$ . This is the given condition. There is nothing to show.

Inductive step. Assume $𝑃(𝑘)$ , which states that $\{1,\ldots ,𝑘\}\subseteq 𝑆$ . By the property of $𝑆$ , we have $𝑘+1\in 𝑆$ , which proves $𝑃(𝑘+1)$ .

Therefore, $𝑃(𝑛)$ holds for all $𝑛\in {\mathbb{Z}}^{+}$ . This is equivalent to say that $𝑆$ contains all positive integers.

Recurrence Relations

A recurrence relation is an equation according to which the $𝑛$ -th term ${𝑎}_{𝑛}$ of a sequence $\{{𝑎}_{𝑛}\}$ is equal to some expression in the preceding terms.

If each ${𝑎}_{𝑛}$ (except ${𝑎}_{1}$ ) is determined only by the immediatel peceding term, we can write

{𝑎}_{𝑛}=\varphi (𝑛,{𝑎}_{𝑛-1}),\quad 𝑛\geq 2.

The reason why $\varphi$ also depends on $𝑛$ (as its first parameter) is that the expression of each pair of consecutive terms may differ. Then by the principle of mathematical induction Theorem 1.3, we may conclude that ${𝑎}_{𝑛}$ is well-defined for each $𝑛\in {\mathbb{Z}}^{+}$ , and hence the sequence $\{{𝑎}_{𝑛}\}$ is defined.

The recurrence relation of the arithmetic sequence ${𝑎}_{𝑛}=𝑎+(𝑛-1)𝑑$ is

{𝑎}_{𝑛}={𝑎}_{𝑛-1}+𝑑,\quad 𝑛\geq 2.

And the recurrence relation of the geometric sequence ${𝑎}_{𝑛}=𝑎{𝑟}^{𝑛-1}$ is

{𝑎}_{𝑛}={𝑎}_{𝑛-1}𝑟,\quad 𝑛\geq 2.

In the preceding two examples, $\varphi (𝑛,{𝑎}_{𝑛-1})$ only depends on ${𝑎}_{𝑛-1}$ .

Consider the sequence of factorials ${𝑎}_{𝑛}=𝑛!$ . Its recurrence relation is

{𝑎}_{𝑛}=𝑛{𝑎}_{𝑛-1},\quad 𝑛\geq 2.

Here $\varphi (𝑛,{𝑎}_{𝑛-1})=𝑛{𝑎}_{𝑛-1}$ does not only depend on ${𝑎}_{𝑛-1}$ .

More generally, the $𝑛$ -th term ${𝑎}_{𝑛}$ may depend on its preceding $𝑘$ terms, i.e.,

{𝑎}_{𝑛}=\varphi (𝑛,{𝑎}_{𝑛-1},{𝑎}_{𝑛-2},\ldots ,{𝑎}_{𝑛-𝑘}),\quad 𝑛\geq 𝑘+1.

The classical example is the Fibonacci sequence

{𝑎}_{𝑛}={𝑎}_{𝑛-1}+{𝑎}_{𝑛-2},\quad 𝑛\geq 3

with ${𝑎}_{1}={𝑎}_{2}=1$ .

By the second principle of mathematical induction Theorem 1.4, we can show that ${𝑎}_{𝑛}$ is defined for all positive integer numbers $𝑛$ .

Exercises

Consider the $𝑛$ -th partial sum of the harmonic series, ${𝐻}_{𝑛}={\sum }_{𝑗=1}^{𝑛}\frac{1}{𝑗}$ .

Exercise 1.2

Show by mathematical induction that

{𝐻}_{{2}^{𝑛}}\geq 1+\frac{𝑛}{2}.

Proof

Let $𝑃(𝑛)$ be the statement that the inequality to show holds for $𝑛$ .

Base case. $𝑛=1$ . LHS is ${𝐻}_{2}=1+1/2$ and RHS is $1+1/2$ . In this case LHS equals to RHS. Hence, $𝑃(1)$ holds.

Inductive step. Assume $𝑃(𝑘)$ . Let $𝑛=𝑘+1$ . We have

\begin{aligned}{𝐻}_{{2}^{𝑛}}={𝐻}_{{2}^{𝑘+1}} & = & & \underbrace{\sum _{𝑗=1}^{{2}^{𝑘}}\frac{1}{𝑗}}_{\geq 1+\frac{𝑘}{2}\, \text{ by }\, 𝑃(𝑘)}+\sum _{𝑗={2}^{𝑘}+1}^{{2}^{𝑘+1}}\frac{1}{𝑗} \\ & \geq & & 1+\frac{𝑘}{2}+\sum _{𝑗={2}^{𝑘}+1}^{{2}^{𝑘+1}}\frac{1}{𝑗} \\ & & & \text{Each }\, 𝑗\leq {2}^{𝑘+1} \\ & \geq & & 1+\frac{𝑘}{2}+\sum _{𝑗={2}^{𝑘}+1}^{{2}^{𝑘+1}}\frac{1}{{2}^{𝑘+1}} \\ & \geq & & 1+\frac{𝑘}{2}+\frac{1}{{2}^{𝑘+1}}\cdot {2}^{𝑘} \\ & \geq & & 1+\frac{𝑘}{2}+\frac{1}{2} \\ & \geq & & 1+\frac{𝑘+1}{2}.\end{aligned}

This proves $𝑃(𝑘+1)$ .