1.6. Induction

Why induction works

Induction is a proving technique. The most elementary version of induction is used to prove statements of the form

$$\text{for all }n\in \mathbb{N},P(n),$$

where $\mathbb{N}$ is the set of natural numbers, that is $\mathbb{N}=\{0,1,2,\dots \}$ and $P(n)$ is a statement about $n$. For example, $P(n)$ could be

$$\text{if }n>2,\text{ then }n\text{ is the sum of two prime numbers}.$$

That this particular statement is true for all $n$ is known as the Goldbach Conjecture and it remains a famous open problem.

The well-ordering principle

The property that makes induction possible is the well-ordering principle:

Axiom (Well-ordering principle).

Every non-empty subset of the naturals has a least element.

Proving this is beyond the scope of the course, but the curious reader will verify that the next two corollaries of the theorem are indeed logically equivalent to it. What this means meta-mathematically is that any statement provable by one technique is provable by all. Knowing which one to pick is a skill acquired by practice.

Some questions to deepen your understanding of the well-ordering principle follow.

Exercises.

1. Is it true that every non-empty subset of the naturals has a maximal element?
2. Is the well-ordering principle true if you replace the naturals with the integers?

First example: Gauss summation formula

The way this principle is applied is that, whenever some natural number has a property, there must always be a first natural number with that property. Let us start with a simple example often attributed to Gauss.

Theorem (Gauss summation formula).

For any natural number $n$,

$$\sum _{k=0}^{n}k=\frac{n(n+1)}{2}.$$

Proof:

Let $A$ be the set of natural numbers for which the statements does not hold. That is, $A$ is the set of all counterexamples, which I now show must be empty.

By contradiction, suppose that $A\ne \varnothing$. Then the well-ordering principle dictates that there must be a smallest natural $n$ inside of $A$. First, notice that $n$ cannot be zero, because zero does satisfy the proposition: ${\sum }_{k=0}^{0}k=0=\frac{0(0+1)}{2}.$

Then it makes sense to consider the natural number $n-1$, which by minimality (meaning, by the fact that $n$ is the smallest element of $A$) cannot be in $A$, and thus must satisfy the proposition. That is,

$$\sum _{k=0}^{n-1}k=\frac{(n-1)n}{2}.$$

But then, if I add $n$ on both sides of that equality,

$$\sum _{k=0}^{n}k=\sum _{k=0}^{n-1}k+n=\frac{(n-1)n}{2}+n=\frac{(n-1)n+2n}{2}=\frac{n(n+1)}{2},$$

which is the conclusion of the proposition but for $n$. This is a contradiction. Hence, such an $n$ cannot exist and thus $A=\varnothing$ or, in words, all naturals satisfy the proposition.

The principle of mathematical induction

There is an easier way of writing the previous proof, namely using the following principle instead.

Corollary (Principle of mathematical induction).

Suppose that $A\subseteq \mathbb{N}$ satisfies that

1. $0\in A$; and that
2. for all $n$, $n\in A$ implies $n+1\in A$.

Then, $A$ must contain every natural number. That is, $A=\mathbb{N}$.

Proof:

By contradiction, suppose that $A\subseteq \mathbb{N}$ satisfies (1.) and (2.) but that the conclusion is wrong, that is, that $A⊊\mathbb{N}$. Then, there exists some natural number not in $A$. By the well-ordering principle, there is a smallest natural $m$ not in $A$.

By the assumption (1.), $m>0$. Then, by the choice of $m$, $m-1\in A$. But then, applying the assumption (2.), $m\in A$, which is a contradiction.

Therefore, such an $m$ cannot exist and hence $A=\mathbb{N}$.

Reflect.

How would the conclusion change if (1.) is changed to $3\in A$ instead? What about $m\in A$?

How to write proofs by induction

This principle offers a sort of “cooking recipe” for writing proofs: First, verify that $0$ (or whatever natural the induction starts at) has the property you want to prove for all $n$. This is called the Base case. Then, assume the Inductive hypothesis, or the fact that $n\in A$. Finally, perform the Inductive step, where you use the fact that $n$ has the sought property to show that $n+1\in A$ and thus you are done.

Exercise.

Rewrite the proof of the Gauss summation formula using this form.

Warning:

A common mistake is having an inductive hypothesis that assumes what you want to prove in the first place. For example, assuming that for all $n$, ${\sum }_{k=0}^{n}k=n(n+1)/2$ as part of the inductive hypothesis.

While this structure is useful for standardizing solutions and learning how to write proofs, I discourage rote memorization, as it hinders understanding more complicated proofs that might not be easily written in this format.

Example of an incorrect proof by induction

Warning:

Careful when applying the inductive hypothesis to the inductive step. The following example illustrates one possible complication.

Fallacious claim.

All trains have just one type of car.

Fallacious proof:

By induction on $n$, the length of the train.

Base case: When $n=1$, the train has just one car, and thus all cars are the same type.

Inductive hypothesis: Suppose that for $n$, all trains of length $n$ just have one type of car.

Inductive step: Let $C_1,C_2,\dots ,C_{n+1}$ be the cars of an arbitrary train of length $n+1$. By the inductive hypothesis, $C_1,C_2,\dots C_n$ are the same type and $C_2,C_3,\dots ,C_{n+1}$ are the same type (given that they both are trains of length $n$). Since $C_1$ and $C_2$ are the same type and $C_2$ and $C_3$ are the same type, then all cars must be the same type. Thus, the train has just one type of car.

Exercise.

Find the first mistake in the previous fallacious proof.

Strong induction

As I move to more complicated proofs by induction, one might run into the following situation where reducing the statement from $n+1$ to $n$ is unhelpful or tricky. In this case, it would be much better to reduce it to say $n-2$ or some other (or even multiple!) natural $k\le n$. Here is an example of this scenario.

Claim.

Alice has an infinite amount of $6 coins and $10 and $15 bills. Use induction to prove that Alice can form any amount of at least $30 using these. For example, Alice can form $31 by taking one of each, or she can form $32 by taking two $10 bills and two coins.

Hint.

The formal statement is: for every natural $n$, if $n\ge 30$, then there exist naturals $s,t,u$ such that $n=15s+10t+6u$.

Proof by "weak" induction:

Base case: Indeed, notice that $30=15+15$.

Inductive hypothesis: Suppose that $n=15s+10t+6u\ge 30$.

Inductive step: If $s>0$, then

$$15(s-1)+10(t+1)+6(u+1)=15s+10t+6u-15+10+6=n+1.$$

Suppose, on the other hand, that $s=0$. If $t=0$, then $n=6u$ where $u\ge 5$ (because $n\ge 30$). Thus, $n+1=6u+1=24+6(u-4)+1=15(1)+10(1)+6(u-4)$. Similarly, if $t=1$ and hence $n=10+6u$, I conclude that $u\ge 4$ and write $n+1=10+24+6(u-4)+1=15(1)+10(2)+6(u-4)$. Therefore, from now on I assume that $t\ge 2$.

Now, I consider the possible values of $u$. If $u=0$, then $n=10t$ where $t\ge 3$. I write $n+1=30+10(t-3)+1=15(1)+10(t-2)+6(1)$. The case when $u=1$ means that $n=10t+6$ with $t\ge 3$. Hence, $n+1=30+10(t-3)+6+1=15(1)+10(t-2)+6(2)$. Similarly, whenever $u=2$, $n=10t+6(2)$ for $t\ge 2$. Thus, $n+1=20+10(t-2)+6(2)+1=15(1)+10(t-2)+6(3)$. Also, if $u=3$, $n=10t+6(3)$ where $t\ge 2$. So, $n+1=20+12+10(t-2)+6(1)+1=15(1)+10(t-2)+6(4)$. Hence, I assume that $u\ge 4$, since otherwise I am done.

Since I am assuming that $s=0$, $t\ge 2$ and $u\ge 4$, it follows that

$$n+1=10t+6u+1=44+10(t-2)+6(u-4)+1$$ $$=45+10(t-2)+6(u-4)=15(3)+10(t-2)+6(u-4).$$

The principle of strong mathematical induction

You can strengthen the hypothesis by not just assuming that the property you want to prove holds for the previous natural but indeed all smaller naturals:

Corollary (Principle of strong mathematical induction).

Suppose that $A\subseteq \mathbb{N}$ satisfies that

1. for every $n$, if for all $k<n$, $k\in A$, then $n\in A$.

Then, $A=\mathbb{N}$.

There is no need to add the assumption that $0\in A$ in this case, since this is a consequence of property (1.). Indeed, by vacuous truth, any natural $k<0$ (of which there are none) satisfies that $k\in A$.

Warning:

This does not mean that, in general, proofs by strong induction do not need a base case.

Proof:

Suppose that $A\ne \mathbb{N}$. Then, by the well-ordering principle, there must be a least natural $n\notin A$. By minimality, any natural $k<n$ must be in $A$. But by property (1.), this would imply that $n\in A$, a contradiction.

I illustrate the fact that, in many cases, you still need to provide the base case to complete the proof by rewriting the proof of the Claim from above.

Proof of Claim by strong induction:

Base cases: $30=15+15$, $31=15+10+6$, $32=10+10+6+6$, $33=15+6+6+6$, $34=10+6+6+6+6$, $35=15+10+10$.

Inductive hypothesis: Let $n\in \mathbb{N}$ with $n\ge 30$ and suppose that for all $k<n$ such that $k\ge 30$, there exist $s,t,u\in \mathbb{N}$ with $k=15s+10t+6u$.

Inductive step: If $n<36$, then it falls into the base cases considered above. Otherwise, I apply the inductive hypothesis to $n-6\ge 36-6=30$ to get $s,t,u$ such that $n-6=15s+10t+6u$. But then $n=15s+10t+6(u+1)$, and so I am done.

# Can you write a computer program that
# explicitly finds these parameters?
# Something like this:
 
def money(n: int):
	# {YOUR CODE HERE}
	return s, t, u

Implementing this particular idea in code produces a greedy algorithm that attempts to maximize the number of coins. Find similar proofs/algorithms that maximize the bills instead. This makes the proof longer to write. Why? An important insight to be gained is that from a deep mathematical perspective:

Induction and recursion are the same phenomenon.

Moreover, the attentive reader will verify that the base cases were tacitly used in the original proof, hinting the fact that both induction types are really just different ways of writing the same proof.

Reflect.

In this section I showed you an example of how a proof by strong induction can be much shorter than the “weak” variant. Can you find a problem that is much harder to solve by weak induction than by strong induction? See here.