Proof by Mathematical Induction

Quick answer

Mathematical induction proves a statement about every positive integer in two steps. The base case checks the statement for n = 1. The inductive step assumes it for one unnamed value k and derives it for k + 1. Together they reach every integer, the way one falling domino topples the whole line. The method proves sum formulas, divisibility claims and inequalities, and both steps are needed: without a base case the step can carry a false statement forever.

What you'll learn

State the base case and the inductive step of a proof
Prove a sum formula by induction
Prove a divisibility claim or an inequality by induction
Explain why both steps are needed

A line of dominoes

Some statements are about every positive integer at once:

1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}

There are infinitely many cases, so checking them one at a time never finishes. Mathematical induction proves them all with two steps, the way a line of dominoes falls:

Base case. Knock over the first domino: prove the statement for $n = 1$ .
Inductive step. Show each domino topples the next: assume the statement for some value $k$ , then prove it for $k + 1$ .

The assumption in step 2 is the inductive hypothesis. It is assumed for one unnamed $k$ , not for every $n$ , which is what keeps the argument honest.

y = n(n + 1)/2

The sums 1 + 2 + ⋯ + n against the formula

Why two steps are enough

Suppose the statement failed somewhere. Then among the values where it fails there is a smallest one, call it $m$ . The base case rules out $m = 1$ , so $m - 1$ is a positive integer where the statement holds. But the inductive step carries truth from $m - 1$ to $m$ , so the statement holds at $m$ after all. A counterexample would have to be the first one, and the base case and the step together leave no room for a first one, so there is no counterexample.

The same idea read forward: to reach $n = 57$ , start at the base case and use the step $56$ times.

Both steps carry weight

Drop the base case and the reasoning collapses. Take the false claim $n = n + 1$ . Assuming $k = k + 1$ and adding $1$ to both sides gives $k + 1 = k + 2$ , so the inductive step is fine. No base case is available, because $1 = 2$ is false, and nothing is proved.

Skipping the step is no better. The expression $n^2 + n + 41$ is prime for every $n$ from $0$ to $39$ , which is forty successful checks, and at $n = 40$ it equals $1681 = 41^2$ .

Worked examples

Common mistakes

Practice problems

Prove $2 + 4 + 6 + \cdots + 2n = n(n + 1)$ .

Answer

Base: $2 = 1(2)$ . Step: $k(k + 1) + 2(k + 1) = (k + 1)(k + 2)$ .

Full solution

At $n = 1$ both sides are $2$ . Assuming the sum of the first $k$ even numbers is $k(k + 1)$ , adding the next one, $2(k+1)$ , gives $(k + 1)(k + 2)$ , which is the formula at $k + 1$ .
Prove $1 + 4 + 7 + \cdots + (3n - 2) = \tfrac{n(3n - 1)}{2}$ .

Answer

Base: $1 = \tfrac{1(2)}{2}$ . Step: $\tfrac{k(3k - 1)}{2} + (3k + 1) = \tfrac{(k + 1)(3k + 2)}{2}$ .

Full solution

The next term after $3k - 2$ is $3(k + 1) - 2 = 3k + 1$ . Adding it: $\tfrac{3k^2 - k + 6k + 2}{2} = \tfrac{3k^2 + 5k + 2}{2} = \tfrac{(k + 1)(3k + 2)}{2}$ , the formula at $k + 1$ .
Prove $1^2 + 2^2 + \cdots + n^2 = \tfrac{n(n + 1)(2n + 1)}{6}$ .

Answer

Base: $1 = \tfrac{1(2)(3)}{6}$ . Step: add $(k + 1)^2$ and factor out $\tfrac{k + 1}{6}$ .

Full solution

$\tfrac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 = \tfrac{(k + 1)\left[k(2k + 1) + 6(k + 1)\right]}{6} = \tfrac{(k + 1)\left(2k^2 + 7k + 6\right)}{6} = \tfrac{(k + 1)(k + 2)(2k + 3)}{6}$ , which is the formula at $k + 1$ .
Prove $1^3 + 2^3 + \cdots + n^3 = \left[\tfrac{n(n + 1)}{2}\right]^2$ .

Answer

Base: $1 = 1^2$ . Step: $\tfrac{k^2(k + 1)^2}{4} + (k + 1)^3 = \tfrac{(k + 1)^2(k + 2)^2}{4}$ .

Full solution

Factor $\tfrac{(k + 1)^2}{4}$ out of the left side: $\tfrac{(k + 1)^2\left(k^2 + 4k + 4\right)}{4} = \tfrac{(k + 1)^2(k + 2)^2}{4}$ , the formula at $k + 1$ .
Prove that $5^n - 1$ is divisible by $4$ for every $n \ge 1$ .

Answer

Base: $5 - 1 = 4$ . Step: $5^{\,k+1} - 1 = 5\left(5^k - 1\right) + 4$ .

Full solution

Assume $5^k - 1 = 4m$ . Then $5^{\,k+1} - 1 = 5 \cdot 5^k - 1 = 5\left(5^k - 1\right) + 4 = 20m + 4 = 4(5m + 1)$ .
Prove that $n^3 - n$ is divisible by $6$ for every $n \ge 1$ .

Hint

Expand $(k + 1)^3 - (k + 1)$ and look for $k^3 - k$ .

Answer

Step: $(k + 1)^3 - (k + 1) = \left(k^3 - k\right) + 3k(k + 1)$ , and $k(k + 1)$ is even.

Full solution

Base: $1 - 1 = 0$ , a multiple of $6$ . For the step, expanding gives $k^3 + 3k^2 + 2k = \left(k^3 - k\right) + 3k^2 + 3k$ . The first part is a multiple of $6$ by assumption, and $3k(k + 1)$ is a multiple of $6$ because one of $k$ and $k + 1$ is even.
Prove $\displaystyle\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1}$ .

Answer

Base: $\tfrac{1}{2} = \tfrac{1}{2}$ . Step: $\tfrac{k}{k + 1} + \tfrac{1}{(k + 1)(k + 2)} = \tfrac{k + 1}{k + 2}$ .

Full solution

Over the denominator $(k + 1)(k + 2)$ the left side is $\tfrac{k(k + 2) + 1}{(k + 1)(k + 2)} = \tfrac{k^2 + 2k + 1}{(k + 1)(k + 2)} = \tfrac{(k + 1)^2}{(k + 1)(k + 2)} = \tfrac{k + 1}{k + 2}$ .
Prove $2^n \ge n + 1$ for every $n \ge 1$ .

Answer

Base: $2 \ge 2$ . Step: $2^{\,k+1} = 2 \cdot 2^k \ge 2(k + 1) \ge k + 2$ .

Full solution

Doubling the assumption gives $2^{\,k+1} \ge 2k + 2$ , and $2k + 2 \ge k + 2$ because $k \ge 1$ .
A proof shows that if a statement holds for $k$ then it holds for $k + 1$ , and stops there. What is missing, and why does it matter?

Answer

The base case. Without it the statement need never be true: $n = n + 1$ passes the step.

Full solution

Assuming $k = k + 1$ and adding $1$ gives $k + 1 = k + 2$ , a valid step for a false claim. The step only passes truth along, so some case has to be true to begin with.
In the step of a proof, a student writes “assume the statement holds for every $n$ , and show it holds for $n + 1$ .” What went wrong?

Hint

What is left to prove once you assume it for every $n$ ?

Answer

Assuming it for every $n$ assumes the conclusion. The hypothesis covers one value, $k$ .

Full solution

Induction proves a statement for every positive integer, so assuming that at the start leaves nothing to prove. The step is a conditional: if the statement holds at one value $k$ , then it holds at $k + 1$ . That conditional, plus the base case, gives every case.

Frequently asked questions

What are the two steps of a proof by induction?

The base case, which checks the statement for the first value, usually n = 1. Then the inductive step, which shows that if the statement holds for k, it holds for k + 1.

What is the inductive hypothesis?

The assumption that the statement holds for one unnamed value k. It is assumed for a single k, not for every n.

Why is the base case necessary?

The step only passes truth along; something has to be true to start with. The false claim n = n + 1 survives the step but has no base case.

Can the base case be a number other than 1?

Yes. To prove a statement for every n ≥ 4, start the base case at 4. The proof then covers 4 and everything above it.

Isn't checking many cases enough?

No. n² + n + 41 is prime for every n from 0 to 39 and composite at n = 40, where it equals 41².

Standards alignment

This lesson covers the following Common Core State Standards for Mathematics.

CCSS.MATH.CONTENT.HSA.SSE.B.4Seeing Structure in ExpressionsDerive the formula for the sum of a finite geometric series (when the common ratio is not 1), and use the formula to solve problems.

For teachersPrint problems onlyTick to print a blank worksheet; leave it clear to print the lesson with the full answer key.