Induction Process

Mathematical induction allows us to prove that every nonnegative integer satisfies a certain property. In this chapter, we will use mathematical induction to prove several mathematical claims. When we reach the next several chapters on programming logic, we will see that mathematical induction is very similar to the process of proving correctness for programs with loops.

Domino effect

To prove that a property $P(n)$ is true for an arbitrary nonnegative integer $n$ using mathematical induction, we must show two things:

1. Base case. We must prove that $P(n)$ is true for the smallest possible value of $n$. Usually this is $n = 0$ or $n = 1$, but occasionally we will define a property for all values greater than or equal to 2, or some bigger number.

2. Inductive step. We assume the inductive hypothesis – that $P(k)$ holds for some arbitrary nonnegative integer $k$. Then, we must show that the property still holds for $k + 1$. In other words, we must prove that $P(k) \rightarrow P(k + 1)$ – that IF $P(k)$ holds for some arbitrary nonnegative integer $k$, THEN $P(k + 1)$ holds as well.

How do these two steps prove anything at all? Suppose we are proving that a property holds for all positive integers $n$. In the base case, we prove that the property holds when $n = 1$. Proving the inductive step allows us to say that whenever the property holds for some number, then it also holds for the number right after that. Since we already know the the property holds when $n = 1$, then the inductive step allows us to infer that the property still holds when $n = 2$. And at that point we know the property holds for $n = 2$, so the inductive step again allows us to infer that the property holds for $n = 3$, etc.

Think of mathematical inductive like a line of dominoes. The “base case” tells us that the first domino will fall, and the “inductive step” tells us that if one domino falls, then the one right after it will fall as well. From these two pieces, we can conclude that the entire line of dominoes will fall (i.e., that the property will hold for the entire set of numbers).

Summation property

There is a well-known formula for adding all positive integers up to some bound, $n$:

To see how this works, suppose $n = 3$. We have that $1 + 2 + 3 = 6$, and also that $\dfrac{3(3+1)}{2} = 6$.

Suppose instead that $n = 7$. We have that $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$, and also that $\dfrac{7(7+1)}{2} = 28$.

First induction proof

Let $P(n)$ be the equation:

We wish to use mathematical induction to prove that $P(n)$ holds for all positive integers $n$.

We will refer to $1 + 2 + ... + n$ as $LHS(n)$ and we will refer to $\dfrac{n(n+1)}{2}$ as $RHS(n)$. To prove that $P(n)$ holds for some positive integer $n$, we must prove that $LHS(n) = RHS(n)$.

Base case

We must prove that $P(n)$ holds for the smallest positive integer, $n = 1$, that is, that $LHS(1) = RHS(1)$. The sum of all integers from 1 to 1 is just 1, so we have that $LHS(1) = 1$. We also have that:

We have that $LHS(1) = RHS(1)$. Thus $P(1)$ is true, so the base case holds.

Inductive step

We assume the inductive hypothesis - that $P(k)$ holds for some arbitrary positive integer $k$. In other words, we assume that $LHS(k) = RHS(k)$ for our arbitrary $k$. We must prove that $P(k+1)$ also holds – i.e., that $LHS(k+1) = RHS(k+1)$. We have that:

Thus $LHS(k+1) = RHS(k+1)$, so we have proved $P(k+1)$. The inductive step holds.

We conclude that for all positive integers $n$, $P(n)$ holds – that is, that:

Inductive step explanation

In line 2 of the proof above we saw that $1 + 2 + ... + k$ was really $LHS(k)$, so we made that substitution. Then in line 3, we used our inductive hypothesis - that $LHS(k) = RHS(k)$, and substituted $RHS(k)$ for $LHS(k)$. Since we had that $RHS(k) = \dfrac{k(k+1)}{2}$, we made that substitution on line 4.

From lines 5 to 7, we did algebraic manipulations to combine our terms and work towards the form of $RHS(k+1)$.

Algebra example

Claim: The sum of the first $n$ odd numbers is $n^2$. We will refer to this claim as $P(n)$.

Try it out

Before proving $P(n)$ with mathematical induction, let’s see if the property holds for some sample values. The sum of the first 3 odd numbers is $1 + 3 + 5 = 9$. We also have that $3^2 = 9$.

The sum of the first 7 odd numbers is $1 + 3 + 5 + 7 + 9 + 11 + 13 = 49$. We also have that $7^2 = 49$.

Another way to express the sum of the first $n$ odd numbers is: $1 + 3 + ... + (2n - 1)$. For example, when $n$ is 4, we have that $2n - 1 = 7$. The sum of the first $4$ odd numbers is $1 + 3 + 5 + 7$.

Induction proof

We wish to use mathematical induction to prove that $P(n)$ holds for all positive integers $n$ That is, that the sum of the first $n$ odd numbers is $n^2$:

We will refer to $1 + 3 + ... + (2n - 1)$ as $LHS(n)$ and we will refer to $n^2$ as $RHS(n)$. To prove that $P(n)$ holds for some positive integer $n$, we must prove that $LHS(n) = RHS(n)$.

Base case

We must prove that $P(n)$ holds for the smallest positive integer, $n = 1$, that is, that $LHS(1) = RHS(1). $ The sum the first 1 odd integer is just 1, so we have that $LHS(1) = 1$. We also have that $RHS(1) = 1^2 = 1$.

We have that $LHS(1) = RHS(1)$. Thus $P(1)$ is true, so the base case holds.

Inductive step

We assume the inductive hypothesis - that $P(k)$ holds for some arbitrary positive integer $k$. In other words, we assume that $LHS(k) = RHS(k)$ for our arbitrary $k$. We must prove that $P(k+1)$ also holds – i.e., that $LHS(k+1) = RHS(k+1)$. We have that:

Thus $LHS(k+1) = RHS(k+1)$, so we have proved $P(k+1)$. The inductive step holds.

We conclude that for all positive integers $n$, $P(n)$ holds – that is, that:

Divisibility example

Claim: If $n$ is a positive integer, then $6^{n} - 1$ is divisible by 5. We will refer to this claim as $P(n)$.

Try it out

Before proving $P(n)$ with mathematical induction, let’s see if the property holds for some sample values. When $n = 3$ we have that $6^{3} - 1 = 216 - 1 = 215$. Since $215$ ends with a 5, it is clearly divisible by 5.

As another test, suppose $n = 5$. We have that $6^{5} - 1 = 7776 - 1 = 7775$, which is also divisible by 5.

Induction proof

We wish to use mathematical induction to prove that $P(n)$ holds for all positive integers $n$. That is, that $6^{n} - 1$ is divisible by 5.

Base case

We must prove that $P(n)$ holds for the smallest positive integer, $n = 1$, that is, that $6^{1} - 1$ is divisible by 5. We have that $6^{1} - 1 = 6 - 1 = 5$ is divisible by 5, so $P(1)$ is true. The base case holds.

Inductive step

We assume the inductive hypothesis - that $P(k)$ holds for some arbitrary positive integer $k$. In other words, we assume that $6^{k} - 1$ is divisible by 5 for our arbitrary $k$. We must prove that $P(k+1)$ also holds – i.e., that $6^{k+1} - 1$ is also divisible by 5. We have that:

Since $6^{k} - 1$ is divisible by 5 from our inductive hypothesis, any multiple of it is also divisible by 5. Thus, $6(6^{k} - 1)$ is divisible by 5. Adding 5 to a number that is a multiple of 5 yields another multiple of 5. Thus $6(6^{k} - 1) + 5$ is divisible by 5, we have proved $P(k+1)$. The inductive step holds.

We conclude that for all positive integers $n$, $P(n)$ holds – that is, that $6^{n} - 1$ is divisible by 5.

Set example

Claim: If $n$ is a positive integer greater than or equal to 2, then a set with $n$ elements has $\dfrac{n(n-1)}{2}$ possible subsets of size 2. We will refer to this claim as $P(n)$.

Try it out

Suppose $n = 3$, and our set contains the elements $(a, b, c)$. There are 3 possible subsets of size 2: $(a, b)$, $(a, c)$, and $(b, c)$. We also have that $\dfrac{3(3-1)}{2} = 3$.

Induction proof

We wish to use mathematical induction to prove that $P(n)$ holds for all integers $n \geq 2$. That is, that a set with $n$ elements has $\dfrac{n(n-1)}{2}$possible subsets of size 2.

Base case

We must prove that $P(n)$ holds for the smallest such integer, $n = 2$. We must show that a set with two elements contains $\dfrac{2(2-1)}{2} = 1$ possible subsets of size 2. If a set has just two elements, then there is only one possible subset of size 2 – the subset that contains both elements. This proves $P(2)$, so the base case holds.

Inductive step

We assume the inductive hypothesis - that $P(k)$ holds for some arbitrary integer $k \geq 2$. In other words, we assume that a set with $k$ elements has $\dfrac{k(k-1)}{2}$ possible subsets of size 2. We must prove that $P(k+1)$ also holds – i.e., that a set with $k + 1$ elements has:

possible subsets of size 2.

Introducing a new element to a set with $k$ elements yields $k$ additional 2-element subsets, as the new element could pair with each of the original elements.

A set with $k+1$ elements contains all the original $\dfrac{k(k-1)}{2}$ size-2 elements from the size- $k$ set, plus the $k$ new subsets described above.

We have that:

We have proved $P(k+1)$. Thus the inductive hypothesis holds.

We conclude that for all positive integers $n \geq 2$, $P(n)$ holds – that is, that a set with $n$ elements has $\dfrac{n(n-1)}{2}$ possible subsets of size 2.