Mathematical Induction, precalculus lesson

Picture a long row of dominoes. You do not need to watch every one of them fall to know that all of them will. It is enough to know that the first one falls and that each falling domino knocks over the next. Mathematical induction turns this picture into a way of proving a statement for every whole number at once, something that no amount of checking cases can do.

Key terms

Statement indexed by integers

Definition A statement indexed by integers is a family of statements $P(n)$ , one for each integer $n$ in a set such as $\{1, 2, 3, \dots\}$ or $\{n_0, n_0 + 1, n_0 + 2, \dots\}$ . For each such $n$ the statement $P(n)$ is a definite claim that is either true or false. Induction proves results that say $P(n)$ is true for every integer $n \ge n_0$ .

In plain words One formula stands for an infinite list of claims, one claim for each whole number. Any single claim can be checked, but there are infinitely many of them.

Example Let $P(n)$ be the claim that the first $n$ odd numbers add up to $n^2$ ,

1 + 3 + 5 + \cdots + (2n - 1) = n^2.

Then $P(3)$ is the claim $1 + 3 + 5 = 9$ , which is true, and $P(4)$ is the claim $1 + 3 + 5 + 7 = 16$ , which is also true. Each value of $n$ gives a different claim.

Principle of mathematical induction

Definition Let $n_0$ be an integer and let $P(n)$ be a statement for each integer $n \ge n_0$ . Suppose that

the statement $P(n_0)$ is true, and
for every integer $k \ge n_0$ , if $P(k)$ is true then $P(k + 1)$ is true.

Then $P(n)$ is true for every integer $n \ge n_0$ . Part 1 is the base case and part 2 is the inductive step. The reason is that the base case gives $P(n_0)$ , the step with $k = n_0$ then gives $P(n_0 + 1)$ , the step with $k = n_0 + 1$ gives $P(n_0 + 2)$ , and no integer from $n_0$ on is ever skipped. This principle is a basic property of the integers. It is equivalent to the fact that every nonempty set of integers that are all at least $n_0$ has a smallest element.

In plain words Knock over the first domino, and make sure that every domino knocks over the next one. Then every domino falls.

Example Here is a complete proof that $1 + 3 + \cdots + (2n - 1) = n^2$ for every integer $n \ge 1$ . For the base case $n = 1$ the left side is $1$ and the right side is $1^2 = 1$ . For the inductive step, let $k \ge 1$ and assume that $1 + 3 + \cdots + (2k - 1) = k^2$ . The next odd number is $2(k + 1) - 1 = 2k + 1$ , so

\begin{aligned} &1 + 3 + \cdots + (2k - 1) + (2k + 1) \\[0.4em] &\quad = k^2 + 2k + 1 \\[0.4em] &\quad = (k + 1)^2, \end{aligned}

which is the claim for $n = k + 1$ . By induction the formula holds for every $n \ge 1$ .

Base case

Definition The base case is the proof of the first statement $P(n_0)$ , usually by direct computation. It cannot be skipped. An inductive step on its own shows only that each statement implies the next one, and a chain of implications proves nothing unless its first link is true. Some proofs need two base cases. When the statement is about a sequence whose rule uses the two previous terms, as the Fibonacci rule does, the step usually shows that $P(k)$ and $P(k + 1)$ together give $P(k + 2)$ for every $k \ge n_0$ . Then both $P(n_0)$ and $P(n_0 + 1)$ must be checked directly, and after that each case follows from the two before it.

In plain words The step makes sure the dominoes stand close enough together. The base case is the push that starts them falling, and without it nothing has to fall.

Example Consider the false claim that $n^2 + n$ is odd for every $n \ge 1$ . Its inductive step actually works. If $k^2 + k$ is odd, then

\begin{aligned} &(k + 1)^2 + (k + 1) \\[0.4em] &\quad = (k^2 + k) + 2(k + 1) \end{aligned}

is an odd number plus an even number, so it is odd. But the base case fails, since $1^2 + 1 = 2$ is even. In fact $n^2 + n = n(n + 1)$ is a product of two consecutive integers, one of which is even, so it is even for every $n$ . Only the base case catches the error.

Inductive hypothesis

Definition In the inductive step one fixes an arbitrary integer $k \ge n_0$ and assumes that $P(k)$ is true. This assumption is the inductive hypothesis, and the task is to deduce $P(k + 1)$ from it. Since $k$ was arbitrary, this proves that $P(k)$ implies $P(k + 1)$ for every $k \ge n_0$ . The hypothesis is about one value $k$ only and never claims that $P(n)$ holds for all $n$ , so the argument is not circular.

In plain words You do not assume what you want to prove. You assume one case and show that the next case follows from it.

Example Take the formula

\begin{gathered} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \\[0.8em] \text{for } n \ge 1. \end{gathered}

The base case is $1 = \frac{1 \cdot 2}{2}$ . Before doing anything else in the step, write down what you may assume and what you must reach. The hypothesis and the goal are

\begin{gathered} 1 + 2 + \cdots + k = \frac{k(k + 1)}{2} \\[0.8em] \text{and} \\[0.4em] \begin{aligned} &1 + 2 + \cdots + (k + 1) \\[0.4em] &\quad = \frac{(k + 1)(k + 2)}{2}. \end{aligned} \end{gathered}

The sum in the goal is the sum in the hypothesis plus one more term, so

\begin{aligned} &1 + 2 + \cdots + k + (k + 1) \\[0.4em] &\quad = \frac{k(k + 1)}{2} + (k + 1) \\[0.8em] &\quad = \frac{(k + 1)(k + 2)}{2}, \end{aligned}

which is the goal. The hypothesis was used at the first equals sign, where the sum of the first $k$ terms was replaced by $\frac{k(k + 1)}{2}$ .

Inductive step

Definition The inductive step is the proof that for every integer $k \ge n_0$ , the truth of $P(k)$ implies the truth of $P(k + 1)$ . A typical step writes out $P(k + 1)$ , finds $P(k)$ or a piece of it inside, replaces that piece using the inductive hypothesis, and simplifies until $P(k + 1)$ appears. The step must work for every $k \ge n_0$ , with $k$ kept as a letter, and not just for a few numbers.

In plain words The step is a recipe that turns any true case into the next true case. You show that the recipe works in general.

Example Here is a proof that $4^n - 1$ is divisible by $3$ for every integer $n \ge 1$ . For $n = 1$ the number is $3$ . Now let $k \ge 1$ and suppose that $4^k - 1 = 3m$ for some integer $m$ . Then

\begin{aligned} 4^{k+1} - 1 &= 4 \cdot 4^k - 1 \\[0.4em] &= 4(4^k - 1) + 3 \\[0.4em] &= 4 \cdot 3m + 3 \\[0.4em] &= 3(4m + 1), \end{aligned}

and $4m + 1$ is an integer, so $4^{k+1} - 1$ is divisible by $3$ . The main move was to rewrite $4^{k+1} - 1$ so that the old number $4^k - 1$ appears inside it.

Starting index

Definition The starting index is the integer $n_0$ of the base case. It need not be $1$ . It can be $0$ , or any integer from which the statement is meant to hold. The base case is checked at $n_0$ , and the inductive step may use the assumption $k \ge n_0$ . The conclusion then covers exactly the integers $n \ge n_0$ and says nothing about smaller ones.

In plain words Start the dominoes where the statement starts being true. The step is allowed to use the fact that $k$ is at least that large, and often it needs to.

Example The inequality $n! > 2^n$ fails for small $n$ and then holds.

$n$	$1$	$2$	$3$	$4$	$5$
$n!$	$1$	$2$	$6$	$24$	$120$
$2^n$	$2$	$4$	$8$	$16$	$32$

So take $n_0 = 4$ , where $24 > 16$ . If $k \ge 4$ and $k! > 2^k$ , then

\begin{aligned} (k + 1)! &= (k + 1) \cdot k! \\[0.4em] &> (k + 1) \cdot 2^k \\[0.4em] &> 2 \cdot 2^k \\[0.4em] &= 2^{k+1}, \end{aligned}

where the last step uses $k + 1 > 2$ . So $n! > 2^n$ for every integer $n \ge 4$ .

Proof versus checking examples

Definition Checking $P(n)$ for finitely many values of $n$ , however many, does not prove that $P(n)$ holds for every $n$ . A pattern seen in examples is a conjecture. It becomes a theorem only through an argument that covers every $n$ at once, and induction is one such argument. On the other hand, a single value of $n$ for which $P(n)$ is false, called a counterexample, is enough to show that the general claim is false.

In plain words Examples tell you what might be true. Only a proof tells you that it is true, while one counterexample shows that it is not.

Example The numbers $n^2 + n + 41$ for $n = 0, 1, 2, 3, 4, 5$ are $41, 43, 47, 53, 61, 71$ , and all of them are prime. In fact $n^2 + n + 41$ is prime for every $n$ from $0$ to $39$ , forty cases in a row. Yet for $n = 40$ the value is

40^2 + 40 + 41 = 1681 = 41^2,

which is not prime. Forty confirmations were not a proof.

Check yourself

Prove that $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$ for every integer $n \ge 1$ .

Show the answer

For $n = 1$ both sides equal $1$ . Now assume that $1 + 2 + \cdots + 2^{k-1} = 2^k - 1$ for some $k \ge 1$ . Adding the next term $2^k$ gives

\begin{aligned} &1 + 2 + \cdots + 2^{k-1} + 2^k \\[0.4em] &\quad = (2^k - 1) + 2^k \\[0.4em] &\quad = 2^{k+1} - 1, \end{aligned}

which is the formula for $n = k + 1$ . By induction it holds for every $n \ge 1$ .

Prove that $2^n > n^2$ for every integer $n \ge 5$ . Why can the proof not start at $n = 1$ ?

Show the answer

For $n = 5$ the inequality reads $32 > 25$ . Now assume that $2^k > k^2$ for some $k \ge 5$ . Then $2^{k+1} = 2 \cdot 2^k > 2k^2$ , and

\begin{aligned} 2k^2 - (k + 1)^2 &= k^2 - 2k - 1 \\[0.4em] &= (k - 1)^2 - 2 \\[0.4em] &> 0 \quad \text{for } k \ge 3, \end{aligned}

so $2^{k+1} > 2k^2 > (k + 1)^2$ . By induction the inequality holds for every $n \ge 5$ . Starting lower fails because the inequality is true for $n = 1$ but false for $n = 2, 3, 4$ , where the two sides are $4$ and $4$ , then $8$ and $9$ , then $16$ and $16$ . So the claim for every $n \ge 1$ is false and has no proof. The chain breaks at the step from $k = 1$ to $k = 2$ , which fits the fact that the algebra above needs $k \ge 3$ . The smallest starting index from which every case is true is $5$ .

Prove that the formula below holds for every integer $n \ge 1$ .

\begin{aligned} &1^2 + 2^2 + \cdots + n^2 \\[0.4em] &\quad = \frac{n(n + 1)(2n + 1)}{6} \end{aligned}

Show the answer

For $n = 1$ both sides equal $1$ . Assume the formula for some $k \ge 1$ and add the next term $(k + 1)^2$ ,

\begin{aligned} &\frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 \\[0.8em] &\enspace = \frac{(k + 1)\bigl(k(2k + 1) + 6(k + 1)\bigr)}{6} \\[0.8em] &\enspace = \frac{(k + 1)(k + 2)(2k + 3)}{6}, \end{aligned}

since $2k^2 + 7k + 6 = (k + 2)(2k + 3)$ . This is the formula for $n = k + 1$ , because $2(k + 1) + 1 = 2k + 3$ . By induction it holds for every $n \ge 1$ .

Mathematical Induction

Key terms

Statement indexed by integers

Principle of mathematical induction

Base case

Inductive hypothesis

Inductive step

Starting index

Proof versus checking examples

Check yourself

How this lesson connects

Builds on

Where this leads in Calculus