Strong induction and ordinary induction

Mar 4, 2018 • mathematics • Permalink

One of my UKMT Mentoring scheme mentees was asking me about induction, and we were discussing how strong induction and ordinary induction are related to each other. In the end, I ended up writing this piece, which I’m sharing here for general interest.

Our aim in this note is to prove the equivalence of “ordinary” induction and strong induction. For concreteness, let us assume that we are trying to prove the statement $P(n)$ (which is a statement about the integer $n$) is true for all $n\ge n_0$, where $n_0$ is some integer. (Typically we will have $n_0=0$ or $n_0=1$, but not necessarily.)

For example, we might be trying to prove that the sum of the first $n$ positive integers is $\frac12 n(n+1)$, in which case we could take $P(n)$ to be the statement $1+2+\cdots+n=\frac12 n(n+1)$ and $n_0=1$. Or we might be trying to prove some statement about all finite graphs, in which case $P(n)$ might be “blah is true for all graphs with $n$ vertices” and $n_0=1$ again.

The principle of mathematical induction

$P(n)$ is true for all $n\ge n_0$ if the following two conditions hold:

(a) $P(n_0)$ is true (the base case), and

(b) if $k\ge n_0$ and $P(k)$ is true, then $P(k+1)$ is true (the induction step).

The principle of strong (mathematical) induction can be useful when the proof of $P(k)$ depends on more than one smaller case.

The principle of strong induction

$P(n)$ is true for all $n\ge n_0$ if the following conditions hold:

(a) $P(n_0)$ is true (the base case), and

(b) if $k>n_0$ and $P(j)$ is true for all $n_0\le j<k$, then $P(k)$ is true (the induction step).

For example, if we are trying to prove a result about Fibonacci numbers, we might use the definition $F_n=F_{n-1}+F_{n-2}$ and have to make use of properties of two smaller numbers. Or we might be arguing about graphs with $n$ vertices, and split a graph up into two smaller graphs with $m$ and $n-m$ vertices; in this case, we may need to assume that whatever result we are trying to show holds not just for graphs with $n-1$ vertices but also for graphs with $m$ and $n-m$ vertices for any $1\le m<n$. In cases such as these, this “stronger” version of induction is very useful.

It turns out that we can actually combine these two conditions into the single condition:

if $k\ge n_0$ and $P(j)$ is true for all $n_0\le j<k$, then $P(k)$ is true.

The induction step where $k>n_0$ is exactly as before, and the base case is where $k=n_0$. In this case, this condition becomes “if $P(j)$ is true for all $n_0\le j<n_0$, then $P(n_0)$ is true”. But there is no $j$ with $n_0\le j<n_0$, so it is vacuously true that $P(j)$ is true for all such $j$, and hence $P(n_0)$ is true. It is easy to overlook this special vacuous case, though, or to argue about it incorrectly within a general argument, so it is often wise, in practice, to handle the base case separately as above.

We are now in a position to prove the equivalence of these two formulations of induction. We first need to be clear what we mean by these being equivalent. What we mean is as follows: if we assume that the principle of mathematical induction is true, then the principle of strong induction follows from this, and vice versa.

Theorem

The principle of mathematical induction and the principle of strong induction are equivalent to each other.

Proof

Let us assume first that the principle of strong induction is true, and aim to prove that the principle of mathematical induction follows from this.

So let $P(n)$ be a statement, $n_0$ an integer, and assume that $P(n)$ satisfies the conditions for mathematical induction, namely:

(i) $P(n_0)$ is true, and

(ii) if $k\ge n_0$ and $P(k)$ is true, then $P(k+1)$ is true.

We wish to show that $P(n)$ is true for all $n\ge n_0$, and we do this by showing that it also satisfies the conditions for strong induction. Now, the base case (i) is the same as the base case (a) for strong induction on $P(n)$. Furthermore, $P(n)$ satifies condition (b) for strong induction, for if $k>n_0$ and $P(j)$ is true for all $n_0\le j<k$, then in particular $P(k-1)$ is true, so by (ii), it follows that $P(k)$ is true. (And note that $k-1\ge n_0$.) Thus the induction step for strong induction also holds, and so by strong induction, $P(n)$ is true for all $n\ge n_0$, as we required.

We now prove the converse: we assume that the principle of mathematical induction is true, and aim to prove that the principle of strong induction follows from this.

So let $P(n)$ be a statement, $n_0$ an integer, and assume that $P(n)$ satisfies the conditions for strong induction, namely:

(i) $P(n_0)$ is true, and

(ii) if $k>n_0$ and $P(j)$ is true for all $n_0\le j<k$, then $P(k)$ is true.

We wish to show that $P(n)$ is true for all $n\ge n_0$. We define a new statement $Q(n)$ for $n\ge n_0$, which states “$P(k)$ is true for all $n_0\le k\le n$”. Then (i) is equivalent to stating that $Q(n_0)$ is true, and we can rewrite (ii) as: if $k>n_0$ and $Q(k-1)$ is true, then $P(k)$ is true. But if $Q(k-1)$ is true and $P(k)$ is true, then $Q(k)$ is true (as now $P(j)$ is true for all $n_0\le j\le k$). So (ii) becomes: if $k>n_0$ and $Q(k-1)$ is true, then $Q(k)$ is true. If we now replace $k-1$ by $k$, we get: if $k\ge n_0$ and $Q(k)$ is true, then $Q(k+1)$ is true.

These are now the base case and induction step for the principle of mathematical induction, and so it follows that $Q(n)$ is true for all $n\ge n_0$. But if $Q(n)$ is true, then $P(n)$ is true (by the definition of $Q(n)$), and so $P(n)$ is true for all $n\ge n_0$, as we required.

This argument shows that the principle of mathematical induction and the principle of strong induction are equivalent and can be used interchangeably.

It is also worth noting that these principles are axioms of arithmetic: it is impossible to “prove” the principle of mathematical induction or the principle of strong induction, though we have proven them to be equivalent to each other. More about them can be found in articles on Peano arithmetic or books on mathematical logic.