2.2: Mathematical Induction - Proof Techniques

# 2.2: Mathematical Induction

## Motivation

Mathematical induction, the last proof technique we will look at, has many parallels to recursion. As an introduction, consider the following situation:

Suppose you’re sitting in a massive lecture hall, and want to find out how many rows you’re sitting from the front of the room. You could sit there and count, but consider this basic principle:

• The person sitting in the first row knows their row number by default: they’re in the first row!
• If one knows the row number of the person in front of them, they add 1 to get their own row number

With this principle, the first person can pass their row number to the second person, who “calculates” their row number (by adding 1) and passes it to the third person, and so on and so fourth. This is exactly how induction (and recursion, to an extent) works.

With induction, we want to prove some property about all natural numbers (it doesn’t matter if we start with 0 or 1, as you will see).

## Formalization

Suppose the expression we want to prove is in terms of the variable $n$ (which is typically used for natural numbers). We follow the following three steps, in every single induction proof:

• Base Case: Establish that the statement holds for $n = 0$ or $n = 1$ (or whatever makes the most sense in the situation)
• Induction Hypothesis: Assume that the statement holds true for $n = k$, for some arbitrary $k$
• Induction Step: Given the fact that the statement holds true for $n = k$, show that it holds for $n = k + 1$

### Example 1

Let’s work out an example. Sure, we could technically use induction to prove that $(x + 1)^2 = x^2 + 2x + 1$ for all natural numbers, but induction is overkill in such an example. A common example of something we may prove with induction is the following fact:

$\sum_{i = 1}^n i = \frac{n(n+1)}{2}, \forall n \in \mathbb{N}$

(The last part specifies that we want all natural numbers.)

Base Case
$\sum_{i = 1}^1 i = 1 = \frac{1(2)}{2}$, therefore, the statement holds for $n = 1$.

Induction Hypothesis
Assume that $\sum_{i = 1}^k i = \frac{k(k+1)}{2}$, for some arbitrary integer $k$.

Induction Step
Now, we need to show that $\sum_{i = 1}^{k+1} i = \frac{(k+1)(k+2)}{2}$, somehow using the information in the induction hypothesis.

\begin{aligned} \sum_{i = 1}^{k + 1} &= \sum_{i = 1}^k + (k + 1) \\ &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{aligned}

By assuming that the statement held true for $n = k$, we were able to come to the conclusion that the statement holds true for $n = k + 1$. Therefore, induction holds, and the statement holds true for all natural numbers.

For another proof (and derivation) of this statement, take a look at the Appendix article on Sequences. We will also provide another proof when we look at combinatorics.

Let’s introduce a more concise notation for writing out the steps of induction. Suppose that $P(i)$ means that the statement we are trying to prove holds true for the value $n = i$. Then, we have:

• Base Case: Show $P(0)$ or $P(1)$ (or whatever other appropriate value)
• Induction Hypothesis: Assume $P(k)$
• Induction Step: Show $P(k) \implies P(k+1)$

Essentially, what we have is a domino effect.

$P(1) \implies P(2) \implies P(3) \implies … \implies P(k) \implies …$

(We told you implications would be important!)

A few things to note:

• The majority of the work in an induction proof is in the induction step. Proving the base case is usually trivial, and in the induction hypothesis you simply state your assumption.
• The example we gave is relatively straight forward. Most of the time, you’ll have to do slightly more work in order to show the implication $P(k) \implies P(k+1)$.

## More Examples

In order to reinforce the concept of induction, we present a few examples below. A good way to practice would be to attempt each problem on your own, and then compare your proof with the solution.

### Example 2

Show that $1 + 3 + 9 + 27 + … + 3^n = \frac{3^{n+1} - 1}{2}, \forall : n \in \mathbb{N}_0$.

Base Case
$3^0 = 1 = \frac{3^1 - 1}{2}$, therefore the base case holds.

Induction Hypothesis
Assume $\sum_{i = 0}^k 3^i = \frac{3^{k + 1} - 1}{2}$ for some arbitrary natural number $k$.

Induction Step

\begin{aligned} \sum_{i = 0}^{k + 1} 3^i &= \sum_{i = 0}^{k} 3^i + 3^{k + 1} \\ &= \frac{3^{k + 1} - 1}{2} + \frac{2 \cdot 3^{k + 1}}{2} = \frac{3 \cdot 3^{k + 1} - 1}{2} \\ &= \frac{3^{k + 2} - 1}{2} \end{aligned}

as required. Therefore, induction holds, and the statement is true.

### Example 3

The Fibonacci sequence $1, 1, 2, 3, 5, 8, 13, 21, 34, …$ is defined by:
$F_1 = 1, F_2 = 1, F_n = F_{n-2} + F_{n-1}$.

Prove that $F_1 + F_2 + … F_n = F_{n + 2} - 1$.

Base Case
$F_1 = 1, F_3 - 1 = 2 - 1 = 1$, therefore the base case holds.

Induction Hypothesis
Assume $F_1 + … + F_k = F_{k + 2} - 1$, for some arbitrary natural number $k$.

Induction Step

\begin{aligned} F_1 + … + F_{k + 1} &= (F_1 + … + F_k) + F_{k + 1} \\ &= F_{k+2} - 1 + F{k+1} \\ &= F_{k + 3} - 1 \end{aligned}

Therefore, induction holds, and the statement is true.

### Example 4

This example will illustrate the fact that not all induction proofs need be algebraic.

Suppose that there are $2n+1$ airports where $n$ is a positive integer. The distances between any two airports are all different. For each airport, there is exactly one airplane departing from it, and heading towards the closest airport. Prove by induction that there is an airport which none of the airplanes are heading towards.

Base Case
$n = 1$: If there are 3 airports, the closest pair of airports will exchange planes. The third airport will then send a plane to one of the first two, meaning this third airport will have no incoming planes.

Induction Hypothesis
Assume for some $k$, in $2k+1$ airports one airport has no incoming planes.

Induction Step
For $2(k+1) + 1 = 2k + 3$ airports, consider the two airports that are closest to one another. This is necessarily unique, given the problem statement. These airports will exchange planes, thus reducing the problem to $2k + 1$ airports. We know the $2k+1$ case holds from the induction hypothesis.

QED.