Mathematical Induction
A formula like 1 + 2 + 3 + ... + n = n(n+1)/2 claims to hold for every positive integer, but no one can check infinitely many cases by hand. Mathematical induction settles all of them with two checks: confirm the first case, then show each case forces the next.
By the end of this page you can:
- State the base case of a claim P(n) and verify it.
- Assume P(k) and use it to prove P(k+1).
- Conclude that P(n) is true for all positive integers n.
The floor. Prove P(1), then prove that P(k) implies P(k+1). Those two steps together prove P(n) for every positive integer n.
Quick Reference
| Field | Value |
|---|---|
| Textbook | Stewart, Redlin, Watson, Precalculus 7e |
| Chapter | 12 |
| Section | 12.5 Mathematical Induction |
| Open alternate | OpenStax Precalculus 2e, 11.4 Series and Their Notations |
| Difficulty | Core |
| Time | About 30 minutes |
Before You Start
The Idea
A statement P(n) about positive integers is like a row of dominoes. The base case knocks over the first domino. The inductive step proves the spacing is right, so any domino that falls knocks over the next one. Once both are in place, every domino falls, which means P(n) holds for all n.
The inductive step is where the work lives. You get to assume P(k) is true for one unspecified integer k (this is the inductive hypothesis), and your job is to show P(k+1) follows from it. You never assume P(k+1) itself; that is the thing being proved.
Key Formulas
The principle of mathematical induction: if P(n) is a statement about positive integers, and
\[ \text{(base case) } P(1) \text{ is true, and (inductive step) } P(k) \implies P(k+1) \text{ for every } k \geq 1, \]
then P(n) is true for all positive integers n.
Source: Stewart 7e, Section 12.5 Mathematical Induction.
The summation identity most often proved this way:
\[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}. \]
Source: Stewart 7e, Section 12.5 Mathematical Induction.
Worked Example
Prove by induction that for every positive integer n, \[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}. \]
Set this up as two steps: check the base case, then run the inductive step.
Show the proof
Base case (n = 1). The left side is 1. The right side is \[ \frac{1(1+1)}{2} = \frac{2}{2} = 1. \] Both sides equal 1, so P(1) holds.
Inductive step. Assume P(k) is true for some positive integer k: \[ 1 + 2 + \cdots + k = \frac{k(k+1)}{2}. \] Show P(k+1), that is, that the sum up to k+1 equals (k+1)(k+2)/2. Add (k+1) to both sides of the hypothesis: \[ 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1). \] Factor (k+1) out of the right side: \[ \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}. \] This is exactly P(k+1).
Conclusion. The base case holds and P(k) implies P(k+1), so by the principle of mathematical induction the formula holds for all positive integers n.
Connections
This builds on sequences and summation notation, since the claims you prove are usually finite sums written with sigma notation. It leans on the arithmetic-sequence and geometric-sequence sum formulas, which are the classic statements induction confirms. It does not cover the binomial theorem; that result is stated separately. The same two-step pattern, base case then inductive step, reappears whenever a claim is indexed by the positive integers.
Resources
- Primary: Stewart, Redlin, Watson, Precalculus 7e, Section 12.5 Mathematical Induction.
- Alternate: OpenStax Precalculus 2e, Section 11.4 Series and Their Notations.
Last updated: 2026-06-24