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)$.