4.1: Introduction to Induction

In this chapter, we introduce mathematical induction, which is a proof technique that is useful for proving statements of the form (∀n ∈ \(\mathbb{N}\))P (n), or more generally (∀n ∈ \(\mathbb{Z}\))(n ≥ a =⇒ P (n)), where P (n) is some predicate and a ∈ \(\mathbb{Z}\).

Consider the claims:

1. For all \(n\in\mathbb{N}\), \(\displaystyle 1+2+3+\cdots +n=\frac{n(n+1)}{2}\).
2. For all \(n\in\mathbb{N}\), \(n^{2}+n+41\) is prime.

Let’s take a look at potential proofs.

“Proof” of (a). If \(n=1\), then \(1=\frac{1(1+1)}{2}\). If \(n=2\), then \(1+2=3=\frac{2(2+1)}{2}\). If \(n=3\), then \(1+2+3=6=\frac{3(3+1)}{2}\), and so on.

“Proof” of (b). If \(n=1\), then \(n^{2}+n+41=43\), which is prime. If \(n=2\), then \(n^{2}+n+41=47\), which is prime. If \(n=3\), then \(n^{2}+n+41=53\), which is prime, and so on.

Are these actual proofs? No! In fact, the second claim isn’t even true. If \(n=41\), then \(n^{2}+n+41=41^{2}+41+41=41(41+1+1)\), which is not prime since it has 41 as a factor. It turns out that the first claim is true, but what we wrote cannot be a proof since the same type of reasoning when applied to the second claim seems to prove something that isn not actually true. We need a rigorous way of capturing “and so on” and a way to verify whether it really is “and so on.”

Recall that an axiom is a basic mathematical assumption. The following axiom is one of the Peano Axioms, which is a collection of axioms for the natural numbers introduced in the 19th century by Italian mathematician Giuseppe Peano (1858–1932).

Axiom 4.1. Let \(S\subseteq \mathbb{N}\) such that both

1. \(1\in S\), and
2. if \(k\in S\), then \(k+1\in S\).

Then \(S=\mathbb{N}\).

We can think of the set \(S\) as a ladder, where the first hypothesis as saying that we have a first rung of a ladder. The second hypothesis says that if we are on any arbitrary rung of the ladder, then we can always get to the next rung. Taken together, this says that we can get from the first rung to the second, from the second to the third, and in general, from any \(k\)th rung to the \((k+1)\)st rung, so that our ladder is actually \(\mathbb{N}\). Do you agree that the Axiom of Induction is a pretty reasonable assumption?

At the end of Section 3.2, we briefly discussed ZFC, which is the standard choice for axiomatic set theory. It turns out that one can prove the Axiom of Induction as a theorem in ZFC. However, that will not be the approach we take. Instead, we are assuming the Axiom of Induction is true. Using this axiom, we can prove the following theorem, known as the Principle of Mathematical Induction. One approach to proving this theorem is to let \(S=\{k\in \mathbb{N}\mid P(k) \text{ is true}\}\) and use the Axiom of Induction. The set \(S\) is sometimes called the truth set. Your job is to show that the truth set is all of \(\mathbb{N}\).

Theorem 4.2. Let \(P(1), P(2), P(3), \ldots\) be a sequence of statements, one for each natural number. Assume

1. \(P(1)\) is true, and
2. if \(P(k)\) is true, then \(P(k+1)\) is true.

Then \(P(n)\) is true for all \(n\in\mathbb{N}\).

The Principle of Mathematical Induction provides us with a process for proving statements of the form: “For all \(n\in\mathbb{N}\), \(P(n)\),” where \(P(n)\) is some predicate involving \(n\). Hypothesis (i) above is called the base step (or base case) while (ii) is called the inductive step.

You should not confuse mathematical induction with inductive reasoning associated with the natural sciences. Inductive reasoning is a scientific method whereby one induces general principles from observations. On the other hand, mathematical induction is a deductive form of reasoning used to establish the validity of a proposition.

Skeleton Proof 4.3. Here is the general structure for a proof by induction.

We proceed by induction.

1. Base step: [Verify that \(P(1)\) is true. This often, but not always, amounts to plugging \(n=1\) into two sides of some claimed equation and that both sides are actually equal.]
2. Inductive step: [Your goal is to prove “For all \(k\in\mathbb{N}\), if \(P(k)\) is true, then \(P(k+1)\) is true.”] Let \(k\in\mathbb{N}\) and assume that \(P(k)\) is true. [Do something to derive that \(P(k+1)\) is true.] Therefore, \(P(k+1)\) is true.

Thus, by induction, \(P(n)\) is true for all \(n\in\mathbb{N}\).

Prove the next few theorems using induction. The first result may look familiar from calculus. Recall that \(\displaystyle \sum_{i=1}^{n}i=1+2+3+\cdots +n\), by definition.

Theorem 4.4. For all \(n\in\mathbb{N}\), \(\displaystyle \sum_{i=1}^{n}i=\frac{n(n+1)}{2}\).

Theorem 4.5. For all \(n\in\mathbb{N}\), 3 divides \(4^{n}-1\).

Theorem 4.6. For all \(n\in\mathbb{N}\), 6 divides \(n^{3}-n\).

Theorem 4.7. Let \(p_{1}, p_{2}, \ldots, p_{n}\) be \(n\) distinct points arranged on a circle. Then the number of line segments joining all pairs of points is \(\frac{n^{2}-n}{2}\).

Problem 4.8. Consider a grid of squares that is \(2^n\) squares wide by \(2^n\) squares long, where \(n\in\mathbb{N}\). One of the squares has been cut out, but you do not know which one! You have a bunch of L-shapes made up of \(3\) squares. Prove that you can perfectly cover this chessboard with the L-shapes (with no overlap) for any \(n\in\mathbb{N}\). Figure 4.1 depicts one possible covering for the case involving \(n=2\).

Figure 4.1: One possible covering for the case involving n = 2 for Problem 4.8.