Math Core

How can you prove that a formula like $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ is true for every positive integer $n$ ? Checking $n = 1, 2, \dots, 1000$ is evidence, not proof, since there are infinitely many cases left. Mathematical induction lets you cover all of them with just two finite arguments.

The domino idea

Picture an endless row of dominoes. To be sure every one falls, you need two facts:

The first domino falls.
Whenever any domino falls, it knocks over the next one.

Neither fact alone is enough. A push with no chain reaction topples one domino; a perfect chain that nobody pushes does nothing. Together they guarantee that domino $1$ knocks down $2$ , which knocks down $3$ , and so on forever.

The principle of mathematical induction

Let $P(n)$ be a statement about the positive integer $n$ . If

Base case: $P(1)$ is true, and
Inductive step: for every $k \ge 1$ , if $P(k)$ is true, then $P(k+1)$ is true,

then $P(n)$ is true for every positive integer $n$ .

The assumption " $P(k)$ is true" in the inductive step is called the inductive hypothesis. You are not assuming what you want to prove. You are proving an implication: if the statement holds at $k$ , then it holds at $k + 1$ . The base case is what starts the chain.

A template for induction proofs

Every induction proof has the same skeleton:

State $P(n)$ clearly.
Base case: verify $P(1)$ directly (or $P(n_0)$ if the claim starts at some other integer $n_0$ ).
Inductive hypothesis: assume $P(k)$ is true for some integer $k \ge 1$ .
Inductive step: using that assumption, show $P(k + 1)$ is true. Write down exactly what $P(k+1)$ says before you start, so you know your target.
Conclude: by induction, $P(n)$ holds for all $n \ge 1$ .

Worked example: Sum of the first n odd numbers

Prove that $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ for every positive integer $n$ .

Base case. When $n = 1$ , the left side is $1$ and the right side is $1^2 = 1$ . ✓

Inductive hypothesis. Assume that for some $k \ge 1$ ,

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

Target. $P(k+1)$ says $1 + 3 + \cdots + (2k - 1) + (2k + 1) = (k + 1)^2$ . The new last term is $2(k+1) - 1 = 2k + 1$ .

Inductive step. Start from the left side of the target and use the hypothesis on everything but the last term:

\begin{aligned} \underbrace{1 + 3 + \cdots + (2k - 1)}_{= \,k^2} + (2k + 1) &= k^2 + 2k + 1 \\ &= (k + 1)^2. \end{aligned}

That is exactly $P(k+1)$ . By induction, the formula holds for every positive integer $n$ .

Notice the move in the middle: you find a copy of the $k$ case inside the $k+1$ case, replace it using the hypothesis, and then do algebra to reach the target. Almost every induction proof works this way.

Worked example: Proving the sum of squares formula

Prove that $\displaystyle\sum_{j=1}^{n} j^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \ge 1$ .

Base case. $n = 1$ : the left side is $1$ ; the right side is $\dfrac{1 \cdot 2 \cdot 3}{6} = 1$ . ✓

Inductive hypothesis. Assume $\displaystyle\sum_{j=1}^{k} j^2 = \frac{k(k+1)(2k+1)}{6}$ for some $k \ge 1$ .

Target. $\displaystyle\sum_{j=1}^{k+1} j^2 = \frac{(k+1)(k+2)(2k+3)}{6}$ , which is the formula with $n$ replaced by $k + 1$ .

Inductive step.

\begin{aligned} \sum_{j=1}^{k+1} j^2 &= \sum_{j=1}^{k} j^2 + (k+1)^2 \\ &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ &= \frac{(k+1)\left[k(2k+1) + 6(k+1)\right]}{6} \\ &= \frac{(k+1)(2k^2 + 7k + 6)}{6} \\ &= \frac{(k+1)(k+2)(2k+3)}{6}. \end{aligned}

This is the target, so the formula holds for all $n \ge 1$ .

Tip

Factor out common pieces (like $k + 1$ above) instead of expanding everything. You know what the answer should look like, so steer the algebra toward it.

Divisibility proofs

Induction also proves statements like " $4^n - 1$ is divisible by $3$ for every $n \ge 1$ ." The trick is to rewrite the $k + 1$ expression so the $k$ expression appears inside it.

Worked example: A divisibility statement

Prove that $4^n - 1$ is divisible by $3$ for every positive integer $n$ .

Base case. $4^1 - 1 = 3$ , which is divisible by $3$ . ✓

Inductive hypothesis. Assume $4^k - 1 = 3m$ for some integer $m$ .

Inductive step. Rewrite $4^{k+1} - 1$ so that $4^k - 1$ appears:

\begin{aligned} 4^{k+1} - 1 &= 4 \cdot 4^k - 1 \\ &= 4 \cdot 4^k - 4 + 3 \\ &= 4(4^k - 1) + 3 \\ &= 4(3m) + 3 = 3(4m + 1). \end{aligned}

Since $4m + 1$ is an integer, $4^{k+1} - 1$ is divisible by $3$ . By induction, $4^n - 1$ is divisible by $3$ for all $n \ge 1$ .

Inequalities and other starting points

A statement doesn't have to start at $n = 1$ . If the claim is only true from $n_0$ on, use $P(n_0)$ as the base case and assume $k \ge n_0$ in the inductive step.

Worked example: An inequality that starts at n = 3

Prove that $2^n > 2n + 1$ for every integer $n \ge 3$ .

(It fails for small $n$ : $2^1 = 2 < 3$ and $2^2 = 4 < 5$ .)

Base case. $n = 3$ : $2^3 = 8 > 7 = 2(3) + 1$ . ✓

Inductive hypothesis. Assume $2^k > 2k + 1$ for some $k \ge 3$ .

Inductive step. We want $2^{k+1} > 2(k+1) + 1 = 2k + 3$ .

2^{k+1} = 2 \cdot 2^k > 2(2k + 1) = 4k + 2.

Now $4k + 2 \ge 2k + 3$ whenever $2k \ge 1$ , which is certainly true for $k \ge 3$ . So $2^{k+1} > 4k + 2 \ge 2k + 3$ . By induction the inequality holds for every $n \ge 3$ .

Common mistake

Don't skip the base case, and don't treat a pattern as a proof. The expression $n^2 + n + 41$ is prime for $n = 0, 1, 2, \dots, 39$ , which looks convincing, but at $n = 40$ it equals $1681 = 41^2$ . In the other direction, the "proof" that $n + 1 = n$ has a perfectly valid inductive step (add $1$ to both sides of $k + 1 = k$ ), yet the statement is never true, because the base case $2 = 1$ fails.

Practice

Practice 1

You want to prove $P(n)$ : $\;2 + 4 + 6 + \cdots + 2n = n(n+1)$ for all $n \ge 1$ . Which of these is the inductive step?

Practice 2

The formula $\displaystyle\sum_{j=1}^{n} j(j+1) = \frac{n(n+1)(n+2)}{3}$ can be proved by induction. As a check, compute both sides at $n = 3$ . What number do they equal?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 3

In proving $2 + 5 + 8 + \cdots + (3n - 1) = \dfrac{n(3n + 1)}{2}$ by induction, you assume the formula holds for $n = k$ . Which term do you add to the left side to get the sum for $n = k + 1$ ? Give your answer in terms of $k$ .

Enter an expression, e.g. 3x^2 - 2x + 1

Practice 4

To prove that $5^n - 1$ is divisible by $4$ for all $n \ge 1$ , you write $5^{k+1} - 1 = 5(5^k - 1) + c$ . What is the constant $c$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

The inequality $2^n > n^2$ is true for every integer $n$ from some starting value $n_0$ on (and it can be proved by induction from that base case). What is the smallest $n_0$ such that $2^n > n^2$ for all $n \ge n_0$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

A sequence has $a_1 = 1$ and $a_{n+1} = 2a_n + 1$ . Its first terms suggest $a_n = 2^n - 1$ , which can be proved by induction: if $a_k = 2^k - 1$ , then $a_{k+1} = 2(2^k - 1) + 1 = 2^{k+1} - 1$ . Use the formula to find $a_{10}$ .

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 7

To prove that $n^3 - n$ is divisible by $6$ for all $n \ge 1$ , you assume $6$ divides $k^3 - k$ and expand:

(k+1)^3 - (k+1) = (k^3 - k) + E.

What is $E$ , and why is it divisible by $6$ ?

Practice 8

Someone claims $n^2 + n + 41$ is prime for every nonnegative integer $n$ , having checked $n = 0$ through $n = 10$ . What is the smallest nonnegative $n$ for which $n^2 + n + 41$ is not prime?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.