How would you prove that \(1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}\) for every natural number \(n\)? Checking case by case is impossible: there are infinitely many naturals. We need an argument that covers all of them at once.
That is the job of the Principle of Mathematical Induction, one of the most elegant proof tools in mathematics.
Why Mathematical Induction? #
Induction shows up whenever we want to state something about all natural numbers at the same time. In discrete mathematics and computer science, this happens often:
- Sum and product formulas: computing the sum of a progression, the product of a sequence, or the number of subsets of a set with \(n\) elements requires an argument that covers every \(n \geq 1\).
- Algorithm analysis: the complexity of nested loops, sums of geometric series and other formulas that appear in performance analysis are typically proved by induction.
- Correctness of recursive functions: a recursive function solves the base case directly and delegates the rest to a smaller call; proving that it returns the correct result for every \(n\) is, structurally, a proof by induction.
- Loop invariants: showing that a property holds after each iteration of a
fororwhilealso follows the logic of induction, with a base case (before the first iteration) and a step (from \(k\) to \(k+1\)). - Formal language theory: properties of grammars and automata are often proved by structural induction, a generalization of PMI to recursive structures.
This article presents the method and its fundamental examples. The connections with programming appear throughout the text.
The Intuition: Dominoes and a Staircase #
Imagine an infinite row of standing dominoes. If you know that:
- The first domino falls, and
- whenever a domino falls, the next one falls too,
then all the dominoes will fall, even though there are infinitely many of them.
The figure below shows this row with each domino labeled by the statement it represents: the first one has already fallen, and each arrow indicates that the fall of one domino knocks over the next.
Another image: an infinite staircase. If you can step onto the first stair and, standing on any stair, you can always step onto the next, then you reach any stair of the staircase, however high it is. There is no need to count the stairs or climb them all at once: the two guarantees are enough.
The resulting chain of implications propagates indefinitely:
flowchart LR P1["P(1)"] --> P2["P(2)"] P2 --> P3["P(3)"] P3 --> P4["P(4)"] P4 --> PN["..."]
That is the logic of mathematical induction.
The Principle of Mathematical Induction #
Let \(P(n)\) be a property about \(n \in \mathbb{N}\). If:
- Base case: \(P(1)\) is true
- Inductive hypothesis (IH): assume that \(P(k)\) is true for an arbitrarily fixed \(k \geq 1\)
- Inductive step: using the IH, prove that \(P(k+1)\) is true
Then \(P(n)\) is true for all \(n \in \mathbb{N}\).
PMI is a central technique for proving results involving natural numbers: sums, inequalities, divisibility and recurrent properties.
The idea is old. Proofs that use the method implicitly appear with the Persian mathematician al-Karaji, around the year 1000, and one of the first rigorous uses is attributed to Gersonides (Maasei Hoshev, 1321). In 1575, Francesco Maurolico used the technique to prove that the sum of the first \(n\) odd numbers is \(n^2\), the second example in this article. The first explicit formulation of the principle is by Blaise Pascal, in the Traité du triangle arithmétique, published in 1665, and the name “mathematical induction” was given by Augustus De Morgan in 1838, the same De Morgan of the laws seen in the article on operations between sets. The full history is in the Mathematical induction entry.
No: it is part of the very definition of the natural numbers. In the Peano axioms, published by Giuseppe Peano in 1889, induction is one of the axioms that characterize \(\mathbb{N}\), and Peano, like this series, started the naturals at 1. Whoever accepts the naturals with this structure accepts, along with them, that induction works.
Structure of a Proof by Induction #
Every proof by induction follows the same three-step structure:
| Step | What to do |
|---|---|
| 1. Base case | Verify that \(P(1)\) is true |
| 2. Inductive hypothesis (IH) | Assume that \(P(k)\) is true for an arbitrarily fixed \(k \geq 1\) |
| 3. Inductive step | Prove \(P(k+1)\) using the IH |
After verifying the base case and carrying out the inductive step, the conclusion follows automatically: \(P(n)\) holds for all \(n \in \mathbb{N}\).
Worked Examples #
Sum of the first \(n\) naturals #
The story goes that Carl Friedrich Gauss, still a child, was given the task by his teacher of adding the numbers from 1 to 100 and answered 5050 within moments: he paired the first with the last (\(1 + 100\)), the second with the second to last (\(2 + 99\)), and so on, forming 50 pairs that each add up to 101. The story is probably apocryphal (see Gauss’s Day of Reckoning, in American Scientist), but the trick works for any \(n\) and suggests the formula; induction proves that it holds for all \(n\).
$$P(n):\ 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$Base case (\(n = 1\)): \(1 = \dfrac{1 \cdot 2}{2} = 1\) ✓
IH: \(1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}\)
Inductive step (\(n = k+1\)):
$$1 + 2 + \cdots + k + (k+1) \stackrel{\text{IH}}{=} \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$$Therefore, \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\), which is what we wanted to prove. \(\blacksquare\)
Application: induction and recursive functions
The proof above has a direct correspondence with the recursive implementation of the sum in Python:
def sum_to(n):
if n == 1:
return 1
return sum_to(n - 1) + n
print(sum_to(100)) # 5050The three steps of induction map exactly to the three elements of the function:
| Induction | Code |
|---|---|
| Base case: \(P(1)\) is true | if n == 1: return 1 |
IH: assume that sum_to(n-1) returns \(\frac{(n-1)n}{2}\) |
recursive call sum_to(n - 1) |
Step: sum_to(n-1) + n produces \(\frac{n(n+1)}{2}\) |
return sum_to(n - 1) + n |
Proving the formula by induction is proving that the recursive function is
correct for all \(n \in \mathbb{N}\). Every well-formed recursive function
implicitly carries a proof by induction. There is also a practical
consequence: the recursive function and the equivalent for loop run in
\(O(n)\), that is, the time grows with \(n\). The closed-form formula
\(\frac{n(n+1)}{2}\) runs in \(O(1)\), constant time. The proof by
induction is the mathematical guarantee that this substitution is safe: both
sides are equivalent for all \(n\), without exception. In the article on
recurrence relations,
we will see how this same function generates the equation
\(S(n) = S(n-1) + n\) and how to solve it formally to obtain the
closed-form formula.
Sum of the first \(n\) odd numbers #
$$P(n):\ 1 + 3 + 5 + \cdots + (2n - 1) = n^2$$This formula has a geometric beauty: the sum of the first \(n\) odd numbers is always a perfect square. The figure below shows why: each new odd number is an L that completes the next square, which is exactly the step \(k^2 + (2k+1) = (k+1)^2\) that the proof does with algebra.
Base case (\(n = 1\)): \(1 = 1^2\) ✓
IH: \(1 + 3 + \cdots + (2k - 1) = k^2\)
Inductive step (\(n = k+1\)):
$$1 + 3 + \cdots + (2k-1) + (2(k+1)-1) \stackrel{\text{IH}}{=} k^2 + 2k + 1 = (k+1)^2$$Therefore, \(1 + 3 + \cdots + (2n-1) = n^2\), which is what we wanted to prove. \(\blacksquare\)
Divisibility #
$$P(n):\ 8 \mid (3^{2n} - 1)$$Base case (\(n = 1\)): \(3^2 - 1 = 8\), and \(8 \mid 8\) ✓
IH: \(8 \mid (3^{2k} - 1)\), that is, \(3^{2k} - 1 = 8m\) for some \(m \in \mathbb{Z}\)
Inductive step (\(n = k+1\)):
We want to show that \(8 \mid (3^{2(k+1)} - 1)\). First, we expand the exponent:
$$3^{2(k+1)} - 1 = 3^{2k+2} - 1 = 3^2 \cdot 3^{2k} - 1 = 9 \cdot 3^{2k} - 1$$Now we rewrite it to isolate \(3^{2k} - 1\), which appears in the IH:
$$9 \cdot 3^{2k} - 1 = 9 \cdot 3^{2k} - 9 + 8 = 9(3^{2k} - 1) + 8$$By the IH, \(3^{2k} - 1 = 8m\) for some \(m \in \mathbb{Z}\), so:
$$9(3^{2k} - 1) + 8 = 9 \cdot 8m + 8 = 8(9m + 1)$$Therefore, \(8 \mid (3^{2n} - 1)\), which is what we wanted to prove. \(\blacksquare\)
Application: loop invariants
The same logic of induction guarantees the correctness of iterative loops.
Consider the for below, which computes the running sum:
n = 100
total = 0
for k in range(1, n + 1):
total += k
print(total == n * (n + 1) // 2) # TrueDefine the invariant \(P(k)\): “after the \(k\)-th iteration,
total == k*(k+1)//2”. Then:
- Base case (\(k = 0\), before the loop):
total = 0and \(0 \cdot 1 / 2 = 0\) ✓ - Step (from \(k\) to \(k+1\)): if
total == k*(k+1)//2before iteration \(k+1\), then aftertotal += k+1we have \(\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}\) ✓
At the end of the loop, \(k = n\), so total == n*(n+1)//2. This argument
is induction in disguise, and it is the mechanism that formal verifiers
(such as those based on Hoare logic) use to prove the correctness of
iterative programs.
Generalized PMI: Base Case at \(n_0 \neq 1\) #
Not every property holds from \(n = 1\) on. When we want to prove \(P(n)\) for all \(n \geq n_0\), we use the generalized version:
To prove \(P(n)\) for all \(n \geq n_0\):
- Base case: verify that \(P(n_0)\) is true
- Inductive hypothesis (IH): assume that \(P(k)\) is true for an arbitrarily fixed \(k \geq n_0\)
- Inductive step: using the IH, prove that \(P(k+1)\) is true
When \(n_0 = 1\), we get the usual PMI as a special case.
Example: \(n^2 > 3n\) for \(n \geq 4\) #
The property \(n^2 > 3n\) does not hold for \(n = 1, 2, 3\):
- \(1^2 = 1 \not> 3\)
- \(2^2 = 4 \not> 6\)
- \(3^2 = 9 \not> 9\)
Induction can only start at \(n_0 = 4\).
Base case (\(n = 4\)): \(16 > 12\) ✓
IH: \(k^2 > 3k\) for some \(k \geq 4\)
Inductive step (\(n = k+1\)):
$$(k+1)^2 = k^2 + 2k + 1 \stackrel{\text{IH}}{>} 3k + 2k + 1 = 5k + 1 > 3(k+1) = 3k + 3$$(valid because \(5k + 1 > 3k + 3 \iff 2k > 2 \iff k > 1\), which is true for \(k \geq 4\))
Therefore, \(n^2 > 3n\), which is what we wanted to prove. \(\blacksquare\)
When Induction Fails #
The method is only as reliable as each of its parts. A famous example shows what happens when the inductive step has a hole: in a satirical article from 1961, the mathematician Joel E. Cohen “proved” that all horses are the same color.
$$P(n):\ \text{in any group of } n \text{ horses, all have the same color}$$Base case (\(n = 1\)): a group with a single horse has a single color ✓
IH: in any group of \(k\) horses, all have the same color.
“Inductive step” (\(n = k+1\)): number the horses of a group of \(k+1\) from 1 to \(k+1\). Without the last one, horses 1 to \(k\) remain, which by the IH have the same color. Without the first one, horses 2 to \(k+1\) remain, which by the IH also have the same color. Since the two groups have horses in common, the two colors are one and the same, and all \(k+1\) horses have the same color.
The base case is right, and the argument of the step works for \(k \geq 2\). The hole is at \(k = 1\): in a group of 2 horses, “horses 1 to \(k\)” is just horse 1 and “those from 2 to \(k+1\)” is just horse 2. There is no horse in common, and nothing connects the two colors. The implication \(P(1) \Rightarrow P(2)\) was never proved: the first domino falls, but nothing guarantees that it knocks over the second. The inductive step must hold for every \(k \geq n_0\), including the first one, precisely where this argument breaks down. More at All horses are the same color.
Exercises #
Practice by applying the three-step structure seen above. The proofs are available for checking after you try.
Exercise 1: Sum of powers of 2
Prove by induction that \(1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1\) for all \(n \in \mathbb{N}\).
Proof
Base case (\(n=1\)): \(1 = 2^1 - 1\) ✓
IH: \(1 + 2 + \cdots + 2^{k-1} = 2^k - 1\)
Inductive step:
$$1 + 2 + \cdots + 2^{k-1} + 2^k \stackrel{\text{IH}}{=} (2^k - 1) + 2^k = 2 \cdot 2^k - 1 = 2^{k+1} - 1$$Therefore, \(1 + 2 + \cdots + 2^{n-1} = 2^n - 1\), which is what we wanted to prove. \(\blacksquare\)
Exercise 2: Sum of squares
Prove that \(1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}\) for all \(n \in \mathbb{N}\).
Proof
Base case (\(n=1\)): \(1 = \dfrac{1 \cdot 2 \cdot 3}{6} = 1\) ✓
IH: \(1^2 + 2^2 + \cdots + k^2 = \dfrac{k(k+1)(2k+1)}{6}\)
Inductive step:
$$1^2 + \cdots + k^2 + (k+1)^2 \stackrel{\text{IH}}{=} \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left(\frac{k(2k+1)}{6} + (k+1)\right)$$$$= (k+1) \cdot \frac{2k^2+7k+6}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$$Therefore, \(1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}\), which is what we wanted to prove. \(\blacksquare\)
Exercise 3: Sum of consecutive products
Prove that \(\displaystyle\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}\) for all \(n \in \mathbb{N}\).
Proof
Base case (\(n=1\)): \(1 \cdot 2 = 2\) and \(\dfrac{1 \cdot 2 \cdot 3}{3} = 2\) ✓
IH: \(\displaystyle\sum_{i=1}^{k} i(i+1) = \dfrac{k(k+1)(k+2)}{3}\)
Inductive step:
$$\sum_{i=1}^{k+1} i(i+1) \stackrel{\text{IH}}{=} \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) = (k+1)(k+2)\left(\frac{k}{3}+1\right) = \frac{(k+1)(k+2)(k+3)}{3}$$Therefore, \(\displaystyle\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}\), which is what we wanted to prove. \(\blacksquare\)
Exercise 4: Arithmetic progression
Prove that \(2 + 5 + 8 + \cdots + (3n-1) = \dfrac{n(1+3n)}{2}\) for all \(n \in \mathbb{N}\).
Proof
Base case (\(n=1\)): \(3(1)-1 = 2\) and \(\dfrac{1 \cdot 4}{2} = 2\) ✓
IH: \(\displaystyle\sum_{i=1}^{k}(3i-1) = \dfrac{k(1+3k)}{2}\)
Inductive step:
$$\sum_{i=1}^{k+1}(3i-1) \stackrel{\text{IH}}{=} \frac{k(1+3k)}{2} + (3k+2) = \frac{k+3k^2+6k+4}{2} = \frac{3k^2+7k+4}{2} = \frac{(k+1)(3k+4)}{2}$$Therefore, \(2 + 5 + \cdots + (3n-1) = \dfrac{n(1+3n)}{2}\), which is what we wanted to prove. \(\blacksquare\)
Exercise 5: Telescoping product
Prove that \(\left(1+1\right)\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{3}\right)\cdots\left(1+\dfrac{1}{n}\right) = n+1\) for all \(n \in \mathbb{N}\).
Proof
Base case (\(n=1\)): \(1 + \dfrac{1}{1} = 2 = 1+1\) ✓
IH: \(\displaystyle\prod_{i=1}^{k}\left(1+\dfrac{1}{i}\right) = k+1\)
Inductive step:
$$\prod_{i=1}^{k+1}\left(1+\frac{1}{i}\right) \stackrel{\text{IH}}{=} (k+1)\left(1+\frac{1}{k+1}\right) = (k+1)\cdot\frac{k+2}{k+1} = k+2$$Therefore, \(\displaystyle\prod_{i=1}^{n}\left(1+\dfrac{1}{i}\right) = n+1\), which is what we wanted to prove. \(\blacksquare\)
Exercise 6: Divisibility
Prove that \(2 \mid n^2 + n\) for all \(n \in \mathbb{N}\).
Proof
Base case (\(n=1\)): \(1+1 = 2\), divisible by 2 ✓
IH: \(k^2 + k = 2q\) for some \(q \in \mathbb{N}\)
Inductive step:
$$(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = \underbrace{(k^2+k)}_{2q} + 2(k+1) = 2\bigl(q + k + 1\bigr)$$Therefore, \(2 \mid n^2 + n\), which is what we wanted to prove. \(\blacksquare\)
Remark: The factorization \(n^2 + n = n(n+1)\) reveals the intuition (a product of consecutive integers, one of them always even), but it is induction that formalizes the proof for all naturals.
Summary Table #
The results proved in this article, gathered for quick reference:
| Result | Statement |
|---|---|
| Sum of the naturals | \(1+2+\cdots+n = \dfrac{n(n+1)}{2}\) |
| Sum of the odd numbers | \(1+3+\cdots+(2n-1) = n^2\) |
| Divisibility | \(8 \mid (3^{2n}-1)\) |
| Inequality (\(n \geq 4\)) | \(n^2 > 3n\) |
| Powers of 2 | \(1+2+\cdots+2^{n-1} = 2^n - 1\) |
| Sum of squares | \(1^2+2^2+\cdots+n^2 = \dfrac{n(n+1)(2n+1)}{6}\) |
| Sum of consecutive products | \(\displaystyle\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}\) |
| Arithmetic progression | \(2+5+\cdots+(3n-1) = \dfrac{n(1+3n)}{2}\) |
| Telescoping product | \(\displaystyle\prod_{i=1}^{n}\left(1+\frac{1}{i}\right) = n+1\) |
| Simple divisibility | \(2 \mid n^2+n\) |
Next Steps #
Standard PMI uses only the case \(P(k)\) to prove \(P(k+1)\). But some problems require all the previous cases at once. Consider, for example, proving that every integer \(n \geq 2\) has a prime factor: to decompose \(n\), it may be necessary to invoke the hypothesis for values smaller than \(k\), not just for \(k\). Standard PMI does not reach that argument, and for that there is Strong Induction, the topic of the next article.
