4.4 The Principle of Mathematical Induction

Mathematical induction is a key method of proof which follows from a fundamental property of the natural numbers called the Principle of Mathematical Induction. You may have seen proofs by induction before, especially to prove statements about summation or divisibility²² 2 You can see some of these kinds of examples in the Companion notes.. Here, we will study the method more formally and apply it to a much wider set of problems.

In the Companion, we saw an analogy for induction as a series of dominoes: if we can prove that one domino will fall (a statement $P(k)$ is true) and that the falling domino will cause the next domino to fall (the statement $P(k)$ implies $P(k+1)$ ) then we have shown that the statement $P(n)$ must be true for all $n\geq k$ .

Definition 4.29 (The Principle of Mathematical Induction).

Given a list of statements $P(k),P(k+1),...$ , we may conclude that $P(n)$ is true for every integer $n\geqslant k$ provided that

•

we know that $P(k)$ is true (the base case)
•

and we can prove that $P(n)\Rightarrow P(n+1)$ for any integer $n\geqslant k$ (the induction step).

A full written proof by induction has the following four parts clearly separated.

1.

A clear and explicit statement of the induction hypothesis $P(n)$ and a stated intention to prove that $P(n)$ is true for all $n\geqslant k$ by induction.
2.

The base case. Typically we prove a single statement $P(k)$ .
3.

The induction step. This normally involves assuming $P(n)$ is true and then reasoning that $P(n+1)$ must also be true.
4.

A conclusion that steps (2) and (3) mean that $P(n)$ is true for all natural numbers $n\geqslant k$ by the principle of mathematical induction.

Mathematics written by and for experts might skip some of the detail, for example saying “the base case is trivial” and not proving it in depth. For now, in this course and during the beginning of your degree, your proofs must be written systematically using all four parts of the format described above.

As an example, we now prove the following generalisation of Theorem 4.26.

Theorem 4.30 (Generalised De Morgan’s Laws).

Let $A_{1},\cdots,A_{n}$ be $n$ sets where $n\in\mathbb{N}$ . Then

(a)

$\displaystyle\left(\bigcup_{i=1}^{n}A_{i}\right)^{c}=\bigcap_{i=1}^{n}A_{i}^{c}$ ,
(b)

$\displaystyle\left(\bigcap_{i=1}^{n}A_{i}\right)^{c}=\bigcup_{i=1}^{n}A_{i}^{c}$ .

Proof (for (a)).

We proceed via induction on $n\in\mathbb{N}$ . Let $P(n)$ be the statement $\displaystyle\left(\bigcup_{i=1}^{n}A_{i}\right)^{c}=\bigcap_{i=1}^{n}A_{i}^{c}$ .

For the base case, first consider $P(1)$ $:\left(\bigcup_{i=1}^{1}A_{i}\right)^{c}=\bigcap_{i=1}^{1}A_{i}^{c}$ . The union or intersection of one set is the set itself so the left hand side of this equation is $(A_{1})^{c}$ while the right hand side is $A_{1}^{c}$ . The brackets make no difference here so we have proven the base case $P(1)$ to be true.

For the induction step, to prove $P(k)$ implies $P(k+1)$ , we suppose that $P(k):\left(\bigcup_{i=1}^{k}A_{i}\right)^{c}=\bigcap_{i=1}^{k}A_{i}^{c}$ holds for some $k\in\mathbb{N}$ .

Let $B=\bigcup_{i=1}^{k}A_{i}$ . Then,

$\displaystyle\left(\bigcup_{i=1}^{k+1}A_{i}\right)^{c}$	$\displaystyle=\left(B\cup A_{k+1}\right)^{c}\quad$	by definition of union
	$\displaystyle=B^{c}\cap A_{k+1}^{c}$	by Theorem 4.26
	$\displaystyle=\left(\bigcup_{i=1}^{k}A_{i}\right)^{c}\cap A_{k+1}^{c}$	by definition of $B$
	$\displaystyle=\left(\bigcap_{i=1}^{k}A_{i}^{c}\right)\cap A_{k+1}^{c}$	by inductive assumption $P(k)$
	$\displaystyle=\bigcap_{i=1}^{k+1}A_{i}^{c}$	by definition of intersection.

This shows that $P(k+1)$ holds if $P(k)$ holds so, by the principle of mathematical induction, we have shown $P(n)$ holds for all $n\in\mathbb{N}$ .

Exercise 4.31.

Adapt this proof in order to prove part (b) of Theorem 4.30. Remember to make sure the four different parts of the induction proof are clear.

Induction proofs are not only used to prove results about sets. They are used in many different areas of maths.

Example 4.32.

Claim: For every $n\in\mathbb{N}$ , the sum of the first $n$ positive odd integers equals $n^{2}$ .

Proof: We prove by induction on $n$ . Let $P(n)$ be the statement “ $\sum_{k=1}^{n}(2k-1)=n^{2}$ ”. The sum of the first odd number, $1$ , equals $1^{2}$ so that $\sum_{k=1}^{1}(2k-1)=1^{2}$ and so $P(1)$ is true. Assume that $P(n)$ is true for some $n\in\mathbb{N}$ . Then

	$\displaystyle\sum_{k=1}^{n+1}(2k-1)$	$\displaystyle=2(n+1)-1+\sum_{k=1}^{n}(2k-1)$
		$\displaystyle=n^{2}+2n+1=(n+1)^{2}.$

Hence $P(n+1)$ is also true. Since $P(1)$ holds and $P(n)\Rightarrow P(n+1)$ , it follows that $P(n)$ is true for all $n\in\mathbb{N}$ by the principal of mathematical induction. $\square$

Example 4.33.

For every $n\in\mathbb{N}$ , we define $n!=n(n-1)(n-2)\cdots 2\cdot 1$ and we read $n!$ as “ $n$ factorial”.

For which $n\in\mathbb{N}$ do we have $2^{n}<n!$ ? If we plug in $n=1,2,3$ this inequality fails, but for $n\geq 4$ it starts to hold. This gives rise to the following conjecture:

Claim: $2^{n}<n!$ for every integer $n\geq 4$ .

Proof: We prove by induction on $n$ . Let $P(n)$ be the statement “ $2^{n}<n!$ ”.

•

Base case: For the base case, we consider when $n=4$ . Since $2^{4}=16<4!=24$ , we conclude that $P(4)$ is true.
•

Induction Step: Assume $P(n)$ is true, i.e. $2^{n}<n!$ for some integer $n\geq 4$ . Then

$2^{n+1}={2^{n}}\cdot 2<{n!}\cdot 2<n!\cdot(n+1)=(n+1)!.$

Since we have shown $P(4)$ is true and $P(n)\implies P(n+1)$ for every positive integer $n$ , we conclude that $P(n)$ holds for every integer $n\geqslant 4$ . $\square$

Example 4.34.

For this example, we need to introduce some definitions.

A polygon is a two-dimensional geometrical object consisting of a number of points (vertices), and the same number of straight line segments connecting them (edges), so that the set of edges forms the boundary of precisely one bounded region (face). A polygon is convex if every straight line segment joining any pair of vertices lies wholly within (or on the boundary of) the polygon.

A straight line segment connecting two vertices that are not adjacent to each other in an n-vertex polygon is called a diagonal of that polygon.

Claim: Every $n$ -vertex convex polygon has $n(n-3)/2$ diagonals, for all integers $n\geqslant 3$ .

Proof: Let $P(n)$ denote the statement “Every $n$ -vertex convex polygon has $n(n-3)/2$ diagonals.” We will prove that $P(n)$ is true for every integer $n\geqslant 3$ by induction on $n$ .

For the base case, observe that every $3$ -vertex convex polygon is a triangle. Since every pair of vertices is adjacent in a triangle, there are no diagonals. Hence, every $3$ -vertex convex polygon has $0=3(3-3)/2$ diagonals, which means that $P(3)$ is true.

For the induction step, let’s assume that $P(n)$ is true for some integer $n\geqslant 3$ . Now consider a general $(n+1)$ -vertex convex polygon $A$ and some vertex $v$ belonging to $A$ . Then $v$ has some pair of vertices, say $u$ and $w$ , that $v$ is adjacent to in $A$ . Suppose we remove vertex $v$ and its adjoining line segments $vu$ and $vw$ connecting $v$ to $u$ and $w$ respectively from $A$ and connect $u$ and $w$ with a line segment $uw$ . Let $B$ be the $n$ -vertex polygon that remains. Note that $B$ is also convex since any line segment connecting a pair of vertices in $B$ also connects a pair of vertices in $A$ and therefore must lie completely in $A$ by its convexity. So if there was a line segment connecting a pair of vertices in $B$ that did not lie wholly in $B$ , it would have to cross the section of $A$ that we cut off to form $B$ . This would only be possible if that line segment ended with the vertex $v$ , which is not in $B$ . Therefore, by $P(n)$ , $B$ has $n(n-3)/2$ diagonals. If we add $v$ and the line segments $vu$ and $vw$ back to $B$ to form $A$ , we introduce $n-2$ new diagonals, one for each vertex of $B$ that is not adjacent to $v$ , and $uw$ becomes an additional diagonal of $A$ . Also, every diagonal of $B$ is also a diagonal of $A$ . Hence, in total, $A$ has

\frac{n(n-3)}{2}+n-2+1=\frac{(n+1)((n+1)-3)}{2},

diagonals. Thus $P(n+1)$ holds.

Therefore, since we have shown that $P(3)$ is true and $P(n)\implies P(n+1)$ for every positive integer $n$ , we conclude that $P(n)$ holds for every integer $n\geqslant 3$ . $\square$

Notice that, as the examples above show, the base case does not always have to consider when $n=1$ . The base case just involves the smallest value of $n$ for which $P(n)$ is true.

4.4.1 Strong Mathematical Induction

Sometimes, in the induction step, it’s not enough to know that $P(n)$ is true in order to prove that $P(n+1)$ is true; we might additionally need to use that some of the "previous" statements $P(k),P(k+1),\dots,P(n-1)$ are true.

Definition 4.35 (Principle of Strong Mathematical Induction).

Let $k\in\mathbb{N}$ and let $P(k),P(k+1),...$ be statements. Suppose that

•

$P(k)$ is true, (base case(s) - we may require more than one base case in a strong induction)
•

and for any integer $n\geqslant k$ , all the statements $P(k),P(k+1),P(k+2),\ldots,P(n)$ taken together imply $P(n+1)$ (induction step).

Then $P(n)$ is true for every positive integer $n\geqslant k$ .

We saw a proof of the following theorem as part of the Fundamental Theorem of Arithmetic in B1 Numbers, but there we used a contradiction argument. We can also prove this result using strong induction.

Theorem 4.36.

Every integer $n\geqslant 2$ can be written as a product of primes $n=p_{1}\cdots p_{k}$ .

If $n$ is prime, this statement still makes sense: we just interpret $n$ as being the product of just one number, $n$ itself.

Proof.

We prove by strong induction on $n$ . Let $P(n)$ denote the statement “There exist $k\in\mathbb{N}$ and primes $p_{1},\ldots,p_{k}$ such that $n=p_{1}\cdots p_{k}$ .

The base case $n=2$ immediately holds since 2 is prime.

For the induction step, let $N\geqslant 3$ be an integer and suppose that $P(n)$ holds for all integers $n$ satisfying $2\leqslant n<N$ (this is our strong inductive hypothesis). If $N$ is prime, there is nothing to prove; otherwise, if $N$ is not prime, then $N=a\cdot b$ for some positive integers $a$ and $b$ greater than $1$ and smaller than $N$ . Both $a$ and $b$ can be decomposed into a product of primes by the strong induction hypothesis, thus so can $N=ab$ . Hence $P(N)$ holds.

Therefore, since $P(2)$ is true and we’ve shown that, for every integer $N\geqslant 3$ , $P(N)$ follows from the statements $P(n)$ for all integers $n$ satisfying $2\leqslant n<N$ , we conclude by strong induction that $P(n)$ holds for all integers $N\geqslant 2$ .

Another situation which often requires strong induction is when studying recurrence relations. A recurrence relation is a sequence $a_{1},a_{2},...$ of numbers where each $a_{n}$ is defined in terms of previous terms in the sequence. The most famous recurrence relation is the Fibonacci sequence, which is defined as $f_{1}=1$ , $f_{2}=1$ and for $n>2$ , $f_{n}=f_{n-1}+f_{n-2}$ .

Example 4.37.

Let $x_{1}=1,x_{2}=3$ and for $n\geq 2$ , let

x_{n+1}=4x_{n}-3x_{n-1}.

Let’s try and find a general pattern for what $x_{n}$ is. If we test the first few values, we get

x_{1}=1,\;\;x_{2}=3,\;\;x_{3}=4\cdot 3-3\cdot 1=9,\;\;x_{4}=4\cdot 9-3\cdot 3=27

so it seems like $x_{n}=3^{n-1}$ . We will prove this by strong induction.

Let $P(n)$ be the statement " $x_{n}=3^{n-1}$ ".

Let’s first prove the first two base cases. Indeed, $x_{1}=1=3^{1-1}$ and $x_{2}=3=3^{2-1}$ , so $P(1)$ and $P(2)$ are true.

Now suppose $P(k)$ is true for $k=1,2,...,n$ for some $n\geq 2$ . Then

x_{n+1}=4x_{n}-3x_{n-1}=4\cdot 3^{n-1}-3x_{n-1}=4\cdot 3^{n-1}-3\cdot 3^{n-2}=% 3^{n}=3^{(n+1)-1}.

This proves that $P(n+1)$ is true, and thus $x_{n}=3^{n-1}$ for all $n$ by strong induction.

Exercise 4.38.

Why did we need to prove two base cases here? Why did we use strong induction instead of standard induction?

Solution (please try for yourself before looking)

Note that the formula $x_{n+1}=4x_{n}-3x_{n-1}$ holds only for $n\geq 2$ , so in particular, we can’t use it to prove $P(2)$ (i.e. that $x_{2}=3^{2-1}$ ). For this reason, we need to prove a few more base cases that can’t be covered in the induction step.

Both $P(n)$ and $P(n-1)$ need to be true to prove $P(n+1)$ , but with standard induction, we would need to prove $P(n+1)$ follows from $P(n)$ alone.

4.4.2 When induction fails

It can be very easy to write something that looks like an induction proof but is actually invalid. Sometimes these errors can be very subtle.

Exercise 4.39.

Spot the flaws in the following argument:

Let $P(n)$ be the statement that “ $1.1!+2.2!+3.3!+\cdots+n.n!=(n+1)!$ ”.

Assume $P(k)$ holds for some $k\in\mathbb{N}$ , then

$\displaystyle 1\cdot 1!+\cdots+k\cdot k!+(k+1)(k+1)!$	$\displaystyle=(k+1)!+(k+1)(k+1)!\quad$	by assumption
	$\displaystyle=(k+1)!(k+2)$	by rearranging
	$\displaystyle=(k+2)!$	by definition of $n!$

Therefore, we can conclude $P(n)$ holds for all $n\in\mathbb{N}$ .

Solution (please try for yourself before looking)

In this argument, the induction step is clear and valid. However, there is no base case. Checking $P(1)$ , we find $1\neq 2$ which means this proof cannot hold.

Exercise 4.40.

Spot the flaws in the following argument:

Define $S(n)$ to be the statement “For any collection of $n$ lines in the plane, if no two are parallel then all lines intersect at one point”.

The base case $S(1)$ holds immediately.

Assume $S(k)$ for some $k\in\mathbb{N}$ so that any collection of $k$ lines (no two of which are parallel) intersect at a single point. Then consider having $k+1$ lines, where no two are parallel. The first $k$ lines must intersect at a single point $P$ by the inductive hypothesis. Moreover, the last $k$ lines also intersect at a single point $Q$ . Two non-parallel lines intersect at a single point so $P=Q$ .

Therefore $S(n)$ holds for all $n\in\mathbb{N}$ .

Solution (please try for yourself before looking)

The error here is more subtle. The base case is valid for $P(1)$ and the induction step shows $P(n)\implies P(n+1)$ , but only for $n\geq 3$ because you need the same two lines to be present in the first $k$ lines and the last $k$ lines to conclude that $P=Q$ . So we are missing two additional base cases: $P(2)$ (which is true) and $P(3)$ which is false.

Exercise 4.41.

Spot the flaws in the following argument:

We will prove by induction on $n$ that $a^{n}=1$ whenever $n$ is a non-negative integer and $a$ is a non-zero real number.

Let $P(n)$ be the statement “ $a^{n}=1$ for every non-zero $a\in\mathbb{R}$ ”.

As $a^{0}=1$ , $P(0)$ is true.

Assume $P(k)$ holds. Then

a^{k+1}=\frac{a^{k}\cdot a^{k}}{a^{k-1}}=\frac{1\cdot 1}{1}=1.

Hence $P(k+1)$ is true.

Therefore, $P(n)$ holds for all values $n\in\mathbb{N}$ .

Solution (please try for yourself before looking)

This is an example where the induction step fails from too few base cases. Here, the induction step uses strong induction to assume both $a^{k}=1$ and $a^{k-1}=1$ . But we have only shown that one base case $P(0)$ is true. So in order to rely on $P(k-1)$ and $P(k)$ to show $P(k+1)$ , we would need to show $P(1)$ is true too. But clearly, $a^{1}=1$ for all non-zero $a\in\mathbb{R}$ is false. So the proof fails.