Mathematical Induction: Steps & Examples

Mathematical induction proves that a statement is true for every positive whole number n. First, show it is true for n = 1 (the base case). Next, assume it is true for some n = k and use that to show it is true for n = k + 1 (the inductive step). Together, these prove it for all n.

Before this lesson: Sigma Notation, Arithmetic Series, Geometric Series and Algebraic Proofs

How induction works

Picture a long row of dominoes. Two facts guarantee that every domino falls: the first domino is pushed over, and any falling domino knocks over the next one. You never have to watch each domino.

Induction works the same way. The base case knocks over the first domino. The inductive step shows that if the statement is true for one number k, it must be true for the next number, k + 1. The assumption that it is true for k is called the inductive hypothesis.

Checking a few values, like n = 1, 2 and 3, is not a proof. It only shows the first few dominoes fall. The inductive step is what covers every n.

The base case starts the chain, and the inductive step keeps it going, so the statement holds for every n.

Steps of a proof by induction

Base case: show the statement is true for n = 1 (or for the first value the problem names).
Inductive hypothesis: assume the statement is true for n = k, for some whole number k ≥ 1.
Goal: write out what the statement says for n = k + 1.
Inductive step: start from one side of the goal, use the inductive hypothesis, and do algebra until you reach the other side.
Conclusion: by mathematical induction, the statement is true for every whole number n ≥ 1.

In sum proofs, it helps to name the sum. If $S_n = 1 + 2 + \cdots + n$ , then the next sum is the old sum plus one more term: $S_{k+1} = S_k + (k + 1)$ .

Mathematical induction examples

Example 1: The sum of the first n whole numbers

Prove that $1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}$ for every whole number n ≥ 1.

1 = \frac{1(1 + 1)}{2}

Base case: for n = 1, the left side is 1 and the right side is $\frac{1 \cdot 2}{2} = 1$ . They match.

S_k = \frac{k(k + 1)}{2}

Inductive hypothesis: let $S_n = 1 + 2 + \cdots + n$ and assume the formula works for n = k.

S_{k+1} = \frac{(k + 1)(k + 2)}{2}

Goal: show the formula works for n = k + 1. Replace n with k + 1.

S_{k+1} = S_k + (k + 1)

Start the inductive step. The sum to k + 1 is the sum to k plus the next term.

S_{k+1} = \frac{k(k + 1)}{2} + (k + 1)

Use the inductive hypothesis to replace $S_k$ .

S_{k+1} = \frac{k(k + 1)}{2} + \frac{2(k + 1)}{2}

Write k + 1 over a common denominator of 2.

S_{k+1} = \frac{k(k + 1) + 2(k + 1)}{2}

Add the fractions.

S_{k+1} = \frac{(k + 1)(k + 2)}{2}

Factor out the common factor k + 1 (see factoring out the GCF). This is the goal.

Conclusion: the formula is true for n = 1, and whenever it is true for k it is true for k + 1. By mathematical induction, it is true for every n ≥ 1.

Example 2: The sum of the first n odd numbers

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

1 = 1^2

Base case: for n = 1, both sides equal 1.

S_k = k^2

Inductive hypothesis: let $S_n = 1 + 3 + \cdots + (2n - 1)$ and assume $S_k = k^2$ .

S_{k+1} = (k + 1)^2

Goal for n = k + 1.

S_{k+1} = S_k + (2(k + 1) - 1)

Add the next odd number, $2(k + 1) - 1$ .

S_{k+1} = k^2 + 2k + 1

Use the hypothesis, and simplify $2(k + 1) - 1 = 2k + 1$ .

S_{k+1} = (k + 1)^2

Factor the perfect square trinomial (see perfect square trinomials). This is the goal.

Conclusion: by induction, the sum of the first n odd numbers is $n^2$ for every n ≥ 1.

Example 3: A divisibility proof

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

4^1 - 1 = 3

Base case: 3 is divisible by 3.

4^k - 1 = 3m

Inductive hypothesis: assume $4^k - 1$ is a multiple of 3, so it equals 3m for some whole number m.

4^{k+1} - 1 = 4 \cdot 4^k - 1

Goal: show $4^{k+1} - 1$ is a multiple of 3. Rewrite $4^{k+1}$ as $4 \cdot 4^k$ (see exponent rules).

4^{k+1} - 1 = 4(4^k - 1) + 3

Write it so the expression from the hypothesis appears: $4 \cdot 4^k - 4 + 3$ .

4^{k+1} - 1 = 4(3m) + 3

Use the inductive hypothesis.

4^{k+1} - 1 = 3(4m + 1)

Factor out 3. Since 4m + 1 is a whole number, this is a multiple of 3.

Conclusion: by induction, $4^n - 1$ is divisible by 3 for every n ≥ 1. For example, $4^3 - 1 = 63 = 3 \cdot 21$ .

Example 4: An inequality

Prove that $2^n \gt n$ for every n ≥ 1.

2^1 = 2

Base case: for n = 1, $2 \gt 1$ is true.

2^k \gt k

Inductive hypothesis: assume $2^k \gt k$ .

2^{k+1} = 2 \cdot 2^k

Start the inductive step from the left side of the goal, $2^{k+1} \gt k + 1$ .

2 \cdot 2^k \gt 2k

Multiply both sides of the hypothesis by 2.

2k = k + k \ge k + 1

Since k ≥ 1, adding k is at least adding 1.

2^{k+1} \gt k + 1

Chain the steps together. This is the goal.

Conclusion: by induction, $2^n \gt n$ for every n ≥ 1. Inequality proofs often need one extra step like $k \ge 1$ to finish.

Example 5: Word problem with handshakes

At a meeting, every pair of people shakes hands once. When one more person arrives, that person shakes hands with everyone already there. Prove that n people make $H(n) = \frac{n(n - 1)}{2}$ handshakes.

H(1) = \frac{1(0)}{2} = 0

Base case: one person makes 0 handshakes, and the formula gives 0.

H(k) = \frac{k(k - 1)}{2}

Inductive hypothesis: assume the formula works for k people.

H(k + 1) = H(k) + k

Person k + 1 arrives and shakes hands with the k people already there.

H(k + 1) = \frac{k(k - 1)}{2} + \frac{2k}{2}

Use the hypothesis and write k over 2.

H(k + 1) = \frac{k^2 - k + 2k}{2}

Distribute and add the fractions.

H(k + 1) = \frac{k^2 + k}{2} = \frac{(k + 1)k}{2}

Combine like terms and factor. This is the formula with n = k + 1.

Conclusion: by induction, n people make $\frac{n(n - 1)}{2}$ handshakes. A class of 30 makes $\frac{30 \cdot 29}{2} = 435$ handshakes. This is also $C(30, 2)$ , the number of pairs (see combinations).

Common mistakes

Mistake	Example of the error	Fix
Skipping the base case	Proving only “if true for k, then true for k + 1”	Without the first domino, nothing falls. Always check n = 1.
Assuming what you want to prove	Writing the k + 1 statement as a fact at the start	Assume only the k statement; the k + 1 statement is the goal.
Never using the inductive hypothesis	Expanding $S_{k+1}$ from scratch	Split off the last term so $S_k$ appears, then replace it.
Wrong next term	Adding 2k − 1 instead of 2(k + 1) − 1 in Example 2	Replace n with k + 1 everywhere in the last term.
Treating examples as a proof	“It works for n = 1, 2, 3, 4, so it is true”	Checking cases is a test, not a proof. Do the inductive step.
Forgetting to state the conclusion	Ending with the algebra	Finish with “By mathematical induction, the statement is true for every n ≥ 1.”

Related methods

Starting at a different number

If a statement is only true from some number on, start the base case there. For example, $2^n \gt n^2$ is true for n ≥ 5, so the base case is n = 5: $32 \gt 25$ .

Induction and series formulas

Induction proves the sum formulas you used earlier, such as the arithmetic series and geometric series formulas. It checks a formula; it does not find one. To guess a formula, look for a pattern first.

Practice problems

Check the formula $1 + 2 + \cdots + n = \frac{n(n + 1)}{2}$ for n = 1 and for n = 4.
For $2 + 4 + 6 + \cdots + 2n = n(n + 1)$ , write the inductive hypothesis and the goal.
Prove that $2 + 4 + 6 + \cdots + 2n = n(n + 1)$ for every n ≥ 1.
Prove that $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$ for every n ≥ 1.
Prove that $1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ for every n ≥ 1.
Prove that $5^n - 1$ is divisible by 4 for every n ≥ 1.
Prove that $3^n \ge 2n + 1$ for every n ≥ 1.
Complete the proof: for $S_n = 1 + 3 + 9 + \cdots + 3^{n-1} = \frac{3^n - 1}{2}$ , the base case and hypothesis are done. Finish the inductive step.
Prove that $n^2 + n$ is even for every n ≥ 1.
The Tower of Hanoi puzzle with n disks takes M(n) moves, where M(1) = 1 and M(k + 1) = 2M(k) + 1. Prove that $M(n) = 2^n - 1$ .

Show answers

1 = \frac{1(2)}{2}

For n = 1, both sides equal 1.

1 + 2 + 3 + 4 = 10

For n = 4, add the left side.

\frac{4(5)}{2} = 10

Find the right side. They match.

Answer: both checks work, but checks are not a proof.

S_k = k(k + 1)

Hypothesis: assume $2 + 4 + \cdots + 2k = k(k + 1)$ .

S_{k+1} = (k + 1)(k + 2)

Goal: replace n with k + 1.

Answer: hypothesis $S_k = k(k + 1)$ ; goal $S_{k+1} = (k + 1)(k + 2)$ .

2 = 1(1 + 1)

Base case: n = 1 gives 2 = 2.

S_{k+1} = S_k + 2(k + 1)

Add the next even number to the sum.

S_{k+1} = k(k + 1) + 2(k + 1)

Use the hypothesis $S_k = k(k + 1)$ .

S_{k+1} = (k + 1)(k + 2)

Factor out k + 1. This is the goal.

Answer: true for n = 1, and true for k implies true for k + 1, so by induction it is true for every n ≥ 1.

1 = 2^1 - 1

Base case: n = 1 gives 1 = 1.

S_{k+1} = S_k + 2^k

The next term is $2^{(k+1)-1} = 2^k$ .

S_{k+1} = 2^k - 1 + 2^k

Use the hypothesis $S_k = 2^k - 1$ .

S_{k+1} = 2 \cdot 2^k - 1

Combine like terms: $2^k + 2^k = 2 \cdot 2^k$ .

S_{k+1} = 2^{k+1} - 1

Use an exponent rule. This is the goal.

Answer: by induction, the formula holds for every n ≥ 1.

1 = \frac{1(2)(3)}{6}

Base case: both sides equal 1.

S_{k+1} = S_k + (k + 1)^2

Add the next square.

S_{k+1} = \frac{k(k + 1)(2k + 1)}{6} + \frac{6(k + 1)^2}{6}

Use the hypothesis and write $(k + 1)^2$ over 6.

S_{k+1} = \frac{(k + 1)[k(2k + 1) + 6(k + 1)]}{6}

Factor out k + 1.

S_{k+1} = \frac{(k + 1)(2k^2 + 7k + 6)}{6}

Expand and combine inside the brackets.

S_{k+1} = \frac{(k + 1)(k + 2)(2k + 3)}{6}

Factor the trinomial (see factoring trinomials when a is not 1). This is the formula with n = k + 1, since 2(k + 1) + 1 = 2k + 3.

Answer: by induction, the formula holds for every n ≥ 1.

5^1 - 1 = 4

Base case: 4 is divisible by 4.

5^{k+1} - 1 = 5(5^k - 1) + 4

Rewrite: $5 \cdot 5^k - 5 + 4$ .

5^{k+1} - 1 = 5(4m) + 4

Use the hypothesis $5^k - 1 = 4m$ .

5^{k+1} - 1 = 4(5m + 1)

Factor out 4. It is a multiple of 4.

Answer: by induction, $5^n - 1$ is divisible by 4 for every n ≥ 1.

3^1 = 3

Base case: $3 \ge 2(1) + 1 = 3$ is true.

3^{k+1} = 3 \cdot 3^k

Start from the left side of the goal $3^{k+1} \ge 2k + 3$ .

3 \cdot 3^k \ge 3(2k + 1)

Multiply the hypothesis $3^k \ge 2k + 1$ by 3.

3(2k + 1) = 6k + 3 \ge 2k + 3

Distribute; 6k is at least 2k because k ≥ 1.

Answer: so $3^{k+1} \ge 2(k + 1) + 1$ , and by induction the inequality holds for every n ≥ 1.

S_{k+1} = S_k + 3^k

The next term is $3^{(k+1)-1} = 3^k$ .

S_{k+1} = \frac{3^k - 1}{2} + \frac{2 \cdot 3^k}{2}

Use the hypothesis and write $3^k$ over 2.

S_{k+1} = \frac{3 \cdot 3^k - 1}{2}

Add the fractions: $3^k + 2 \cdot 3^k = 3 \cdot 3^k$ .

S_{k+1} = \frac{3^{k+1} - 1}{2}

Use an exponent rule. This is the goal.

Answer: the formula holds for k + 1, which completes the proof.

1^2 + 1 = 2

Base case: 2 is even.

(k + 1)^2 + (k + 1) = k^2 + k + 2k + 2

Expand and regroup so $k^2 + k$ appears.

(k + 1)^2 + (k + 1) = 2j + 2(k + 1)

Use the hypothesis $k^2 + k = 2j$ for some whole number j.

(k + 1)^2 + (k + 1) = 2(j + k + 1)

Factor out 2. It is even.

Answer: by induction, $n^2 + n$ is even for every n ≥ 1.

10.

M(1) = 2^1 - 1 = 1

Base case: matches M(1) = 1.

M(k + 1) = 2M(k) + 1

Use the rule for one more disk.

M(k + 1) = 2(2^k - 1) + 1

Use the hypothesis $M(k) = 2^k - 1$ .

M(k + 1) = 2^{k+1} - 2 + 1

Distribute.

M(k + 1) = 2^{k+1} - 1

Combine. This is the goal.

Answer: by induction, $M(n) = 2^n - 1$ . A 10-disk tower takes $2^{10} - 1 = 1023$ moves.

Mathematical induction FAQ

What are the steps of mathematical induction?

Prove the base case (usually n = 1), assume the statement for n = k, then use that assumption to prove it for n = k + 1. Finish by stating that it holds for all n.

What is the inductive hypothesis?

It is the assumption that the statement is true for n = k. You use it in the inductive step to prove the statement for n = k + 1.

Why does mathematical induction work?

The base case makes the statement true for 1. The inductive step then passes truth from 1 to 2, from 2 to 3, and so on, so no whole number is skipped.

Can the base case be something other than n = 1?

Yes. Start at the first value the problem names, such as n = 0 or n = 5, and the proof covers every whole number from there on.

Summary

Induction proves a statement for every whole number n ≥ 1 (or from any starting value).
Base case: check the first value.
Inductive hypothesis: assume it for n = k. Goal: write it for n = k + 1.
Inductive step: start from the k + 1 side, use the hypothesis, and reach the goal.
For sums, use $S_{k+1} = S_k + (\text{next term})$ ; for divisibility, rewrite so the hypothesis expression appears.

Previous lesson: Binomial Theorem

Next lesson: Introduction to Limits

Back to the Precalculus Index