Mathematical Induction – Foundations of Mathematics

千里之行，始於足下

The journey of a thousand miles starts with a single step.

Lao Tzu

Many statements in mathematics are true {\em for any natural number}. For example.

Fundamental Theorem of Arithmetic. Every natural number has a unique prime decomposition.

Theorem. Every natural number is either even or odd.

Power Rule for Differentiation. For any natural number $n$ , $\frac{d}{dx}\left[x^n\right]=nx^{n-1}$ .

Our first use of the definition of $\mathbb{N}$ (other than to prove facts about arithmetic) will be to establish a way to prove statements like this. But to do that, we need to make sure our definition of $\mathbb{N}$ is formal enough to serve as the backbone of a proof. To do this, we'll focus on the structure of the open sentences involved. Since we are interested only in statements that involve the natural numbers somehow, we're going to assume that the variables we're dealing with represent natural numbers unless otherwise specified. That is, we're taking the universe for everything to be $\mathbb{N}$ until further notice.

Definition. We call an open sentence $P(n)$ inductive if it has the property: $\forall n, P(n)\Rightarrow P(n+1)$ .

We can think of inductive sentences as representing hereditary properties -- that is, they pass down to successors. Being royal, for example, is an inductive property.

Equipped with this definition, we can state axiom 5 of the natural numbers as a formal symbolic sentence. (If you recall, we stated the first four axioms as formal symbolic sentences, but left the fifth axiom just in terms of words.) Here goes:

The Inductive Axiom. Let $P(n)$ be an open sentence whose variable $n$ represents a natural number. Suppose that:

$P(1)$ is true, and
$P$ is inductive.

Then $\forall n, P(n)$ .

This version still has a few words in it, but we could make it purely symbolic:

$\left(P(1)\wedge \left[\forall n, P(n)\Rightarrow P(n+1)\right]\right)\Rightarrow \forall k,P(k)$

To see that this version is the same as the wordier version we gave before, let's take $P(n)$ to be " $n$ can be reached from 1 by a sequence of successions". It's clear that this $P$ is inductive: if $n$ can be reached from 1 by successions, so can its successor. Clearly 1 can be reached from 1 by a(n extremely short) sequence of successions. So $P$ meets both criteria -- the Inductive Axiom says "any natural number can be reached from 1 by a sequence of successions".

The Inductive Axiom is also known as the Principle of Mathematical Induction, or PMI for short. It's the engine that will let us prove lots of statements of the form $\forall n, P(n)$ , because that's the conclusion of PMI.

To use PMI in this way, you need to a few things:

identify what $P(n)$ is
verify that $P(1)$ is true (we call this the "base case")
show that $P(n)$ is inductive, which means to prove $\forall n, P(n)\Rightarrow P(n+1)$ (we call this the "inductive step")

Luckily, we already know how to prove universal claims, and we already know how to prove conditionals. So a general outline of a proof by induction goes like this:

Proof. (by induction)
base case: $n=1$ . [Establish $P(1)$ ]

inductive step: Let $n$ be a natural number. Assume $P(n)$ is true.
[. . . some work goes here . . .] Conclude $P(n+1)$ .

$\Box$

Let's write an example proof by induction to show how this outline works. I'll put my commentary in blue parentheses.

Claim. I can reach any rung of any ladder which is standing on the ground.

Proof. Given a ladder, we'll show that for any $n$ , I can reach the $n^{th}$ rung of that ladder. (Here $P(n)$ is the statement "I can reach the $n^{th}$ rung of the ladder.")

I can reach the first rung by taking a step -- after all, the ladder is standing on the ground. (We've just proved $P(1)$ .)

Now suppose I'm standing on the $n^{th}$ rung. (This is assuming $P(n)$ .) Then I can take a step (These are the "juicy bits" of the proof.), and get to the $(n+1)^{th}$ step. (We've concluded $P(n+1)$ .)

By the Principle of Mathematical Induction, this shows we can reach any rung of the ladder. $\Box$

Here's an example where $P(n)$ is "more mathematical".

Claim. For any natural number $n$ , $1+4+7+\cdots+(3n+1)=\frac{3}{2}n^2+\frac{5}{2}n+1$ .

Proof. (base case) When $n=1$ , the left-hand side is $1+4=5$ . The right-hand side is $\frac{3}{2}\cdot 1^2+\frac{5}{2}\cdot 1+1=\frac{3}{2}+\frac{5}{2}+1=4+1=5$ . So the equality is true when $n=1$ .

(inductive step) Let $n$ be a natural number. Assume $1+4+7+\cdots+(3n+1)=\frac{3}{2}n^2+\frac{5}{2}n+1$ . Consider the left-hand side of $P(n+1)$ :

$\begin{align*} 1+4+7+\cdots+(3(n+1)+1)&=1+4+7+\cdots+3n+(3(n+1)+1)\\ &=\frac{3}{2}n^2+\frac{5}{2}n+1+3(n+1)+1\\&=\frac{3}{2}n^2+\frac{5}{2}n+3n+5\end{align*}$

Here we have used the assumption $P(n)$ .

Now we work on the right-hand side of $P(n+1)$ :

$\begin{align*} \frac{3}{2}(n+1)^2+\frac{5}{2}(n+1)+1&=\frac{3}{2}(n^2+2n+1)+\frac{5}{2}(n+1)+1\\&=\frac{3}{2}n^2+\frac{5}{2}n+3n+\frac{3}{2}+\frac{5}{2}+1\\&=\frac{3}{2}n^2+\frac{5}{2}n+3n+5\end{align*}$

Since the left-hand side of $P(n+1)$ and the right-hand side of $P(n+1)$ are both equal to $\frac{3}{2}n^2+\frac{5}{2}n+3n+5$ , they are equal to each other. That is, $P(n+1)$ is true. This completes the inductive step.

By the Principle of Mathematical Induction, we have established the claim. $\Box$ .

A few things to note here. First, the base case is usually pretty obvious. Second, the fun (i.e. hard) part of the proof is figuring out how to use $P(n)$ to get $P(n+1)$ .

It's not always obvious what the natural number (or inductive variable) is. Often it's the size of something (since the natural numbers are for counting!). If your inductive variable isn't obvious from the problem statement, it's good form to let the reader know what you'll be inducting on.

Claim. Every finite set of real numbers has a least element.

Proof. We will proceed by induction on the size of the set.

(base case) Suppose the set has exactly one element. Then that element is least.

(inductive step) Assume we've proved that any set of real numbers with exactly $n$ distinct elements has a least element. We'll show that any set of real numbers with exactly $n+1$ distinct elements has a least element.

Let $S$ be such a set, and label its elements $a_1,a_2,\ldots, a_n,a_{n+1}$ . There are two possibilities for how $a_{n+1}$ is related to the other elements of the set.

case: $a_{n+1}<a_k$ for all $k\leq n$ . Then $a_{n+1}$ is least.

case: There is some $k\leq n$ with $a_k<a_{n+1}$ . Then consider the set $S'$ which consists of all of the $a$ s except $a_{n+1}$ . $S'$ has exactly $n$ elements, so by our inductive assumption, there is a least element of $S'$ (call it $b$ ). Then $b\leq a_k<a_{n+1}$ , so $b$ is also least in $S$ .

In either case, $S$ has a least element, thus completing the inductive step, hence (by PMI) the proof. $\Box$

"Generalized" induction

Now consider the following:

Claim. If I am standing in a second story window, I can get to any rung of any ladder standing on the ground, provided that rung is at least the $15^{th}$ rung.

The form of this claim is: $\forall n, \left(n\geq 15\Rightarrow P(n)\right)$ , or $\forall n\geq 15,P(n)$ .

Proof. Since I'm in the second story window, I can step out onto the $15^{th}$ rung. (Prove $P(15)$ .)

Now if I'm on any rung, I can take a step to get to the next rung. (Prove that $P(n)$ guarantees $P(n+1)$ .)

So no matter what rung (above the $15^{th}$ ) I want to get to, I can. $\Box$ .

This technique of starting someplace other than 1 is sometimes called generalized induction, but it really doesn't deserve such a fancy name. It's just regular induction, but starting from some number other than 1.