Proof by induction

This is a default technique to use when we want to prove that a certain statement holds for infinitely many values of a certain variable. For instance, if we want to find a closed form for $\sum_{i=0}^n 2^i$, by looking at the pattern, we can see that it should be $2^{n+1} -1$. But how can we show that this holds for all $n \in \mathbb{N}$? In this case, we can proceed as follows:

1. When $n = 1$, we have that the sum is $1 + 2 = 3$ and the closed form $2^{n+1} - 1$ is also $3$. Therefore, the formula is correct.

2. Otherwise, assume that the formula $P(n): \sum_{i=0}^n 2^i = 2^{n+1} - 1$ is correct for $n = n_0$ and we want to argue that it is true for $n_0 + 1$. Indeed, $\sum_{i=0}^{n_0+1} 2^i = \sum_{i=0}^{n_0} 2^i + 2^{n_0+1}$ . By the assumption that $P(n_0)$ holds, we can reduce this to $2^{n_0+1} - 1 + 2^{n_0+1} = 2^{n_0+2} - 1$. This implies that $P(n_0 + 1)$ also holds.

Now let us try to understand what we have done. We prove that $P(1)$ holds and that $P(n_0) \Rightarrow P(n_0 + 1)$ for all $n_0$. The latter would imply that $P(2)$ also holds, and again $P(3)$ and so on. This will establish the validity of $P(n)$ for all $n \in \mathbb{N}$. The statement $P(n)$ is called induction hypothesis. Coming up with the right hypothesis to prove is the key.

In the next example, we will see something more surprising. Consider a chessboard in Figure 1 that has one square removed from it. We claim that any such chessboard (with one square removed, regardless of which square) can be covered by non-overlapping L-shapes without a gap.

Figure 1: A standard chessboard with one square removed. On the right, an L-shape that can be used (in any rotation) to cover the board.

It would seem like proving this statement requires going over all $64$ cases of potential choice of a removed square, and for each such case, show how to cover it with L-shapes. In fact, the easiest way to prove this statement is via mathematical induction! We encourage the students to try proving this fact before reading on.

The following is the induction hypothesis:

$P(n)$: Every $2^n\times 2^n$ chessboard with one square missing can be covered by L-shapes.

Notice that the statement when $n = 1$ is trivial (case analysis has only four cases), so we established the validity of $P(1)$. Now assume that we know $P(n_0)$ is true. To prove $P(n_0 +1)$, consider a $2^{n_0+1} \times 2^{n0+1}$ chessboard $B$ with a missing square. We can cut this board into four equal boards by halving horizontally and vertically. Let $B_{tl}, B_{tr}, B_{bl}, B_{br}$ be those chessboards of size $2^{n_0}$-by-$2^{n_0}$ (corresponding to the top-left, top-right, bottom-left and bottom-right chessboards). Assume, without loss of generality (WLOG), that a missing square is in $B_{tl}$.¹ We invoke the induction hypothesis $P(n_0)$ for $B_{tl}$ and (i) $B_{tr}$ with the lower-left corner missing, (ii) $B_{bl}$ with the upper-right corner missing, and (iii) $B_{br}$ with the upper-left corner missing. Combining these coverings allows us to cover the whole board $B$.

Exercise 2

Let us draw $n$ (infinite) lines in the plane in such a way that no two are parallel and no three intersect in a common point. Prove that the plane is divided into exactly $\frac{n(n+1)}{2} + 1$ parts by these lines.

Exercise 3

Let $n_1, \ldots , n_k$ be natural numbers, each of them at least one, and $\sum_{i=1}^k n_i = n$. Prove by induction that $\sum_{i=1}^k n_i^2 \le (n - k + 1)^2 + k - 1$.

Exercise 4

A straight-line map is a map created by a rectangle, which is partitioned into regions by straight lines, such that each line divides the rectangle into two regions. Prove that such a map can always be colored so that each region is colored red or blue, and that no two bordering regions have the same color. See Figure 2.

Figure 2: A straight-line map with four regions created by drawing two straight lines.

This exercise is closely related to the celebrated Four Color Theorem, which says that every map (regardless of how you draw the regions) can be colored by at most four colors.

📄️ Finding the right hypothesis

In many cases, the induction follows immediately from the statement we want to prove, but often it helps to make the induction hypothesis stronger than the targeted statement. This might sound counter-intuitive, so let us try to absorb this idea via a few examples.

📄️ Strong induction

Another way to use a stronger induction hypothesis is called strong induction: To prove $P(k)$, instead of assuming that $P(k-1)$ is true, we assume that $P(1),\ldots, P(k-1)$ are all true and try to derive the validity of $P(k)$.

Footnotes

1. We will very often use this term in this lecture note. ↩