Mathematical Induction

“Induction makes you feel guilty for getting something out of nothing, and it is artificial, but it is one of the greatest ideas of civilization.”
—Herbert S. Wilf

“The use of mathematical induction in demonstrations was, in the past, something of a mystery. There seemed no reasonable doubt that it was a valid method of proof, but no one quite knew why it was valid. ” —Bertrand Russell

We assume you have already seen proofs by induction in your previous math classes. In this section, we focus on what induction actually is, and why it works.

Proofs by induction are common in mathematics and ubiquitous in Computer Science.

Example

Theorem: for every $n\in\mathbb{N}$ , $\sum_{i=0}^{n} i \ = \ \frac{n(n+1)}{2}$ .

Proof (by induction on the natural numbers):

Base case: If $n = 0$ the equation holds because $0 = 0$ .
Inductive case: Let $n\geq 0$ and assume $n$ satisfies the above equation. Then

\begin{array}{rcll} \sum_{i=0}^{n+1} i & = & \left(\sum_{i=0}^{n} i\right) \ + n+1 \\[10pt] & = & \frac{n(n+1)}{2} + n+1 & \mathrm{(by~IH)} \\[10pt] & = & \frac{(n+1)((n+1)+1)}{2} \\ \end{array}

So $n+1$ satisfies the equation.

QED

What is Induction?

Suppose $P$ is a property that natural numbers can have.

Example

$P(k)$ := $k\geq 2$ .
$P(k)$ := $k$ is prime.
$P(k)$ := $k$ is either even or odd.

Then induction is a way to prove that $P$ holds for all natural numbers

Specifically, a proof by induction on the natural numbers is a proof that invokes the following property of the natural numbers, called the Induction Principle for $\mathbb{N}$ :

Definition

Induction Principle for $\mathbb{N}$

For any property $P$ of natural numbers, if

$P(0)$ , and
for every $n{\in}\mathbb{N}$ , if $P(n)$ then $P(n+1)$ ,

then for every $n{\in}\mathbb{N},\ \ P(n)$ .

Or equivalently,

P(0) \land \bigl(\forall n{\in}\mathbb{N}\ (P(n)\to P(n+1))\bigr) \ \to \ \bigl(\forall n{\in}\mathbb{N}\ P(n)\bigr)

So,

if we prove $\forall n{\in}\mathbb{N}\ P(n)$ using the general strategy for quantifiers (i.e., assume we have an arbitrary $n{\in}\mathbb{N}$ , and directly prove that $P(n)$ holds), this is not an inductive proof.
But if we prove that $\forall n{\in}\mathbb{N}\ P(n)$ by showing that the premises of the Induction Principle are true — namely, that $P(0)$ holds and that $\forall n{\in}\mathbb{N}\ \ (P(n)\to P(n+1))$ — then it is an inductive proof.

The Example above is a proof by induction in this sense because:

The relevant property $P$ is

P(n) \ := \ \sum_{i=0}^{n} i \ = \ \frac{n(n+1)}{2}.

The “base case” argues that that $P(0)$ is true.
The “inductive case” shows that $\forall n{\in}\mathbb{N}\ (P(n)\to P(n+1))$ is true. The proof structure exactly matches the structure of this formula: it startwith an arbitrary natural number $n$ , assumes that $P(n)$ holds, and proves that $P(n+1)$ holds).

Why Does Induction Work? Argument 1

Assume $P(0)$ , and that for every $n{\in}\mathbb{N}$ , if $P(n)$ then $P(n+1)$ . Then:

$P(0)$ by assumption.
Since $P(0)\to P(1)$ , we also have $P(1)$ .
Since $P(1)\to P(2)$ , we also have $P(2)$ .
Since $P(2)\to P(3)$ , we also have $P(3)$ .
etc.

Thus for every $n{\in}\mathbb{N},\ \ P(n)$ .

While this makes sense, any proof that ends with “etc.” is hand-waving, and is not a truly solid argument. Plus, the our intuition that this sequence of steps eventually shows every natural number has property $P$ is essentially the same as our intuition that induction works, so it’s somewhat of a circular argument.

Maybe we can do better?

Why Does Induction Work? Argument 2

The following idea is attributed to Peano:

Definition

Here’s how to tell whether a set $S$ is the set of natural numbers:

There exists an element $z\in S$ and a function $s : S\to S$ (such that)
( $z$ is not $s(x)$ for any $x\in S$ .)

$z$ is not in the range of $s$ .
( if $x\not=y$ then $s(x) \not= s(y)$ .)

$s$ is injective a.k.a. one-to-one.
For any property $P$ , if $P(z)$ and $\forall x{\in}S\ (\, P(x)\to P(s(x))\,)$ then $\forall x{\in} S\ \ P(x)$ .

(Induction works for $S$ .)

Then we define $\mathbb{N}$ to be a set with these four properties. Since one of those properties is that induction works, we know that induction works for $\mathbb{N}$ !

(This argument is completely rigorous, but perhaps not completely satisfying. We’ll consider one more approach to justifying Induction at the end of this section.)

Induction Variations

Sets isomorphic to $\mathbb{N}$

We can also do induction starting at 1, at 2, etc.

P(1) \land \bigl(\,\forall n{\geq 1}\ (P(n){\to}P(n+1))\,\bigr) \ \to \ \bigl(\forall n{\geq}1\ P(n)\bigr)

P(2) \land \bigl(\,\forall n{\geq 2}\ (P(n){\to}P(n+1))\,\bigr) \ \to \ \bigl(\forall n{\geq}2\ P(n)\bigr)

We can justify the first as follows:

Suppose $P(1)$ and $\bigl(\,\forall n{\geq 1}\ (P(n){\to}P(n+1))\,\bigr)$ .
Define $Q(n) := P(n+1)$ .
Then $Q(0)$ and $\bigl(\,\forall n{\geq 0}\ (Q(n){\to}Q(n+1))\,\bigr)$ .
By the Induction Principle, $\forall n{\geq}0\ \ Q(n)$ .
That is, $\forall n{\geq}1\ P(n)$ .

In general, we can apply induction to any set which is isomorphic to $\mathbb{N}$ .

Strong Induction

Sometimes, it seems like we need something “stronger” than the usual induction principle.

Example

The following proof has a flaw:

Theorem: Every natural number $n\geq 2$ is a product of primes.

Proof (by induction on the natural numbers):

Base case: If $n = 2$ , the factorization is just $2$ .
Inductive case: Let $n\geq 2$ and assume $n$ is a product of primes. We must show that $n+1$ is a product of primes.
- If $n+1$ is prime, we are done.
- If $n+1$ is not prime, then $n+1 = ab$ with $2 \leq a,b \leq n$ . By the Inductive Hypothesis, $a$ and $b$ are both products of primes, so $n+1 = ab$ is too.
In either case, though, $n+1$ is a product of primes.

QED

The problem is that we are applying the inductive hypothesis to $a$ and $b$ , but we only assumed that $n$ was a product of primes. To make this proof work, we need to assume that all numbers between 2 and $n$ are product of primes, not just $n$ .

One option is to switch from the Induction Principle to the Strong Induction Principle:

Definition

Strong Induction Principle for $\mathbb{N}$

For any property $P$ of natural numbers, if

P(0)
for every $n\geq 1$ : if $P(k)$ for all $k<n$ then $P(n)$ .

Then $\forall n\in\mathbb{N}\ P(n)$ .

Equivalently,

\forall n{\in}\mathbb{N}\ \biggl((\forall k{<}n\ P(k))\to P(n)\biggr)\ \ \ \to \ \ \ \bigl(\forall n{\in}\mathbb{N}\ P(n)\bigr)

(The symbolic form might look like it’s missing the base case, but when $n$ is zero the assumption $\forall k{<}n\ P(n)$ is trivially true and doesn’t provide any help in proving $P(0)$ ; as a result, we normally have to prove the $n=0$ case with a separate argument.)

Now we can fix our proof:

Example

Theorem: Every natural number $n\geq 2$ is a product of primes.

Proof (by strong induction on the natural numbers):

Base case: If $n = 2$ , the factorization is just $2$ .
Inductive case: Let $n>2$ and assume every number between 2 and $n$ inclusive is a product of primes . We must show that $n+1$ is a product of primes.
- If $n+1$ is prime, we are done.
- If $n+1$ is not prime, then $n+1 = ab$ with $2 \leq a,b \leq n$ . By the Inductive Hypothesis, $a$ and $b$ are both products of primes, so $n+1 = ab$ is too.
In either case, though, $n+1$ is a product of primes.

QED

Of course, with a little more thought, we can see that we could have gotten the same result with the standard Induction Principle. In fact, any proof that uses Strong Induction could be done with the standard Induction Principle by strengthening the induction hypothesis; strong induction isn’t actually stronger! (And the Strong Induction Principle can be proved correct using the Induction Principle.)

Example

Theorem: For every natural number $n\geq 2$ , every number between 2 and $n$ inclusive is a product of primes

Proof (by “standard” induction on the natural numbers):

Base case: If $n = 2$ , the factorization is just $2$ .
Inductive case: Let $n>2$ and assume every number between 2 and $n$ inclusive is a product of primes . We must show that every number between 2 and $n{+}1$ inclusive is a product of primes .

We only need to check $n{+}1$ ; everything else was already assumed to work!
- If $n+1$ is prime, we are done.
- If $n+1$ is not prime, then $n+1 = ab$ with $2 \leq a,b \leq n$ . By the Inductive Hypothesis, $a$ and $b$ are both products of primes, so $n+1 = ab$ is too.
In either case, though, $n+1$ is a product of primes.

QED

Why Does Induction Work? Argument 3

Finally, here is one more way we could define the natural numbers:

Definition

$\mathbb{N}$ can alternatively be defined as the smallest set $S$ such that

( $S$ contains zero)

$\mathsf{z}\in S$
( $S$ is closed under successor)

If $x\in S$ then $\mathsf{s}x\in S$

This definition is perfectly rigorous. (One can show that there really is a unique smallest such set; it is equal to the infinite intersection of all sets $S$ with those two properties.) Intuitively, it defines the natural numbers as the set of strings

\{\mathsf{z},\mathsf{sz},\mathsf{ssz},\mathsf{sssz},\ldots\}

(though the definition doesn’t appeal to informal ideas like ”…”). Since this is basically unary notation, all the usual operations like + and < can be defined on these strings; this set really is equivalent to what we think of as the natural numbers.

The cool thing about this definition is that we can prove that induction works!

Theorem (Induction Works)

If $P(\mathsf{z})$ and $\bigl(\forall n{\in}\mathbb{N},\ \ P(n)\to P(\mathsf{s}n)\bigr)$ , then $\forall n{\in}\mathbb{N}\ \ P(n)$ .

Proof:

Suppose $P(\mathsf{z})$ and that $\forall n\in\mathbb{N}\ \ \bigl(P(n)\to P(\mathsf{s}n)\bigr)$ .
Define

Y \ :=\ \{\ n\in\mathbb{N}\ |\ P(n)\ \}.

Obviously $Y \subseteq \mathbb{N}$ .
But $Y$ contains $\mathsf{z}$ (because we assumed $P(\mathsf{z})$ is true),
and $Y$ is closed under successor (because if $n\in Y$ then $P(n)$ so $P(\mathsf{s}n)$ and hence $\mathsf{s}n\in Y$ .
Since $\mathbb{N}$ was defined as the smallest such set, it must be that $\mathbb{N}\subseteq Y$ .
Since $Y \subseteq \mathbb{N}$ and $\mathbb{N}\subseteq Y$ , we conclude $Y = \mathbb{N}$ .
But all the members of $Y$ of satisfy $P$ , so

\forall n{\in}\mathbb{N}\ \ P(n).

QED

Mathematical Induction

Example

What is Induction?

Example

Definition

Why Does Induction Work? Argument 1

Why Does Induction Work? Argument 2

Definition

Induction Variations

Sets isomorphic to N\mathbb{N}N

Strong Induction

Example

Definition

Example

Example

Why Does Induction Work? Argument 3

Definition

Theorem (Induction Works)

Sets isomorphic to $\mathbb{N}$