Imagine an infinite row of dominoes. You do not need to push each one by hand. It is enough to know two things: the first domino falls, and whenever a domino falls, it knocks over the next one. Then every domino falls, no matter how far down the row it is.
That picture is mathematical induction, the most important proof technique for statements of the form "for every natural number n, P(n) is true". In the Proof Techniques chapter we learned direct proofs, contrapositive, contradiction and cases; none of them handles "1 + 2 + … + n = n(n + 1)/2 for every n" as cleanly as induction does.
Induction is also the mathematics behind recursion and loops. Every time you argue "the recursive call works on smaller inputs, so the whole function works", or "this loop invariant holds before and after each iteration", you are using induction. In this chapter we cover ordinary (weak) induction, strong induction, the well-ordering principle and structural induction, with many fully worked proofs and the classic traps.
The Principle of Mathematical Induction
Principle of Mathematical Induction. Let P(n) be a statement about integers n. If
1. (Basis step) P(n0) is true, and
2. (Inductive step) for every integer k ≥ n0, P(k) → P(k + 1) is true,
then P(n) is true for every integer n ≥ n0.
In the inductive step, the assumption "P(k) is true" is called the inductive hypothesis (IH). We do not assume P is true for all k; we assume it for one arbitrary k and show it then holds for k + 1.
In logic notation, with n ranging over integers ≥ n0:
[ P(n0) ∧ ∀k ≥ n0 ( P(k) → P(k+1) ) ] → ∀n ≥ n0 P(n)
Why it works
The basis gives P(n0). The inductive step with k = n0 and modus ponens give P(n0 + 1). Again with k = n0 + 1 we get P(n0 + 2), and so on. Any particular n is reached after finitely many steps.
P(n0) ──step──> P(n0+1) ──step──> P(n0+2) ──step──> P(n0+3) ──> ...
^
basis
Formally, the principle follows from the well-ordering principle (every non-empty set of positive integers has a least element), which we discuss later in this chapter.
A template for writing induction proofs
State P(n) clearly, and the starting value n0.
Basis step: verify P(n0) by direct computation.
Inductive hypothesis: "Assume P(k) is true for some arbitrary integer k ≥ n0." Write P(k) out in full.
Goal: write P(k + 1) out in full, so you know exactly what you must reach.
Inductive step: start from one side of P(k + 1), find P(k) inside it, apply the IH, and simplify to the other side.
Conclude: "By the principle of mathematical induction, P(n) holds for all n ≥ n0."
Worked Examples: Summation Formulas
Example 1: 1 + 2 + … + n = n(n + 1)/2
P(n): 1 + 2 + ⋯ + n = n(n + 1)/2, for n ≥ 1.
Basis (n = 1): left side = 1, right side = 1 · 2/2 = 1. True.
IH: assume 1 + 2 + ⋯ + k = k(k + 1)/2 for some k ≥ 1.
Goal: 1 + 2 + ⋯ + k + (k + 1) = (k + 1)(k + 2)/2.
Inductive step:
1 + 2 + ⋯ + k + (k+1) = k(k+1)/2 + (k+1) (by IH)
= (k+1)(k/2 + 1)
= (k+1)(k+2)/2 (the goal)
By induction, the formula holds for all n ≥ 1. ∎
This formula is why a nested loop like for i in 1..n: for j in 1..i runs n(n + 1)/2 times, i.e. Θ(n²).
Example 2: the sum of the first n odd numbers is n²
P(n): 1 + 3 + 5 + ⋯ + (2n − 1) = n².
Basis: n = 1: 1 = 1². True.
Step: assume 1 + 3 + ⋯ + (2k − 1) = k². The next odd number is 2(k + 1) − 1 = 2k + 1. Then
1 + 3 + ⋯ + (2k−1) + (2k+1) = k² + 2k + 1 = (k+1)²
which is P(k + 1). ∎
Example 3: 20 + 21 + ⋯ + 2n = 2n+1 − 1
Basis (n = 0): 20 = 1 and 21 − 1 = 1. True. (Note the basis is n0 = 0 here.)
Step: assume 20 + ⋯ + 2k = 2k+1 − 1. Then 20 + ⋯ + 2k + 2k+1 = (2k+1 − 1) + 2k+1 = 2 · 2k+1 − 1 = 2k+2 − 1. ∎
In binary this says 111…1 (n + 1 ones) = 1000…0 − 1, which is why the largest unsigned value that fits in 32 bits is 232 − 1. It is also why a perfect binary tree of height h (every level completely filled) has 2h+1 − 1 nodes.
Worked Examples: Divisibility
Example 4: 6 divides n³ − n for every n ≥ 0
Basis (n = 0): 0³ − 0 = 0, and 6 divides 0. True.
Step: assume 6 | (k³ − k). Expand the next term:
(k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1
= (k³ − k) + 3k² + 3k
= (k³ − k) + 3k(k + 1)
The first part is divisible by 6 by the IH. For the second, k(k + 1) is a product of two consecutive integers, so it is even, and 3k(k + 1) is a multiple of 3 · 2 = 6. A sum of two multiples of 6 is a multiple of 6. ∎
Trick to remember: in divisibility proofs, rewrite the (k + 1) expression so that the k expression appears as a piece, then show the leftover is also divisible.
Example 5: 7n − 1 is divisible by 6 for n ≥ 0
Basis: 70 − 1 = 0. True.
Step: 7k+1 − 1 = 7 · 7k − 7 + 6 = 7(7k − 1) + 6. By the IH, 6 | (7k − 1), so both terms are multiples of 6. ∎
Worked Examples: Inequalities and Choosing the Base
Example 6: 2n > n² for n ≥ 5
First, why n ≥ 5? Let us just compute:
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
2n | 2 | 4 | 8 | 16 | 32 | 64 | 128 |
n² | 1 | 4 | 9 | 16 | 25 | 36 | 49 |
2n > n²? | yes | no | no | no | yes | yes | yes |
It is true at n = 1, false for n = 2, 3, 4, and true from 5 on. So the basis must be n0 = 5.
Basis: 25 = 32 > 25 = 5².
Step: assume 2k > k² for some k ≥ 5. Then
2^(k+1) = 2 · 2^k > 2k² (by IH)
It remains to show 2k² ≥ (k + 1)², i.e. k² − 2k − 1 ≥ 0, i.e. (k − 1)² ≥ 2. For k ≥ 5, (k − 1)² ≥ 16 ≥ 2. So 2k+1 > 2k² ≥ (k + 1)². ∎
Notice where k ≥ 5 was used: the step itself only needs k ≥ 3, but the basis fails at 3 and 4, so the induction must start at 5.
Example 7: n! > 2n for n ≥ 4
Basis: 4! = 24 > 16 = 24.
Step: assume k! > 2k with k ≥ 4. Then (k + 1)! = (k + 1) · k! > (k + 1) · 2k ≥ 2 · 2k = 2k+1, using k + 1 ≥ 2. ∎
Checking claims by program before proving them
Before trying to prove a formula, it is smart to test it. A test cannot replace the proof, but it can save you from trying to prove something false or from choosing the wrong base:
def check(name, claim, start=1, upto=1000):
for n in range(start, upto + 1):
if not claim(n):
print(f"{name}: FAILS at n = {n}")
return
print(f"{name}: holds for n = {start}..{upto}")
check("1+2+...+n = n(n+1)/2",
lambda n: sum(range(1, n + 1)) == n * (n + 1) // 2)
check("1+3+...+(2n-1) = n^2",
lambda n: sum(2 * k - 1 for k in range(1, n + 1)) == n * n)
check("6 divides n^3 - n",
lambda n: (n**3 - n) % 6 == 0)
check("2^n > n^2", lambda n: 2**n > n * n, start=1, upto=100)
check("2^n > n^2", lambda n: 2**n > n * n, start=5, upto=100)
Output:
1+2+...+n = n(n+1)/2: holds for n = 1..1000
1+3+...+(2n-1) = n^2: holds for n = 1..1000
6 divides n^3 - n: holds for n = 1..1000
2^n > n^2: FAILS at n = 2
2^n > n^2: holds for n = 5..100
Strong Induction
Sometimes P(k + 1) does not follow from P(k) alone, but it does follow from some earlier case, like P(k − 3) or P(k/2). Strong induction lets you assume all earlier cases.
Strong induction (complete induction). If P(n0) is true, and for every k ≥ n0, [P(n0) ∧ P(n0 + 1) ∧ ⋯ ∧ P(k)] → P(k + 1), then P(n) is true for all n ≥ n0.
Strong induction is not more powerful than ordinary induction: each can be proved from the other (apply ordinary induction to Q(n) = "P(n0) ∧ ⋯ ∧ P(n)"). It is just more convenient when the step reaches back further than one.
Example 8: every integer n ≥ 2 is a product of primes
Basis: 2 is prime, so it is a product of one prime.
Step: assume every integer j with 2 ≤ j ≤ k is a product of primes. Consider k + 1.
If k + 1 is prime, it is a product of one prime.
Otherwise k + 1 = a · b with 2 ≤ a, b ≤ k. By the strong IH, a and b are both products of primes, so their product k + 1 is too. ∎
Ordinary induction would be useless here: knowing that k is a product of primes says nothing about k + 1. We needed the IH for a and b, which can be anything between 2 and k.
Example 9: postage with ₹4 and ₹5 stamps
Claim: every amount n ≥ 12 rupees can be paid exactly using only ₹4 and ₹5 stamps.
Basis (four cases):
12 = 4 + 4 + 4
13 = 4 + 4 + 5
14 = 4 + 5 + 5
15 = 5 + 5 + 5
Step: let k ≥ 15 and assume every amount from 12 to k can be paid. Then k + 1 ≥ 16, so k + 1 − 4 = k − 3 ≥ 12, and k − 3 can be paid by the IH. Add one ₹4 stamp. ∎
Why four base cases? The step jumps back by 4. If we only checked 12, the step for k + 1 = 13 would reach back to 13 − 4 = 9, which is below 12 and so not covered by the hypothesis; and for 15 it would reach back to 11, which cannot be paid at all. With bases 12–15, every n ≥ 16 reaches back to an amount in 12…k.
This kind of argument is also a dynamic-programming recurrence. The program below computes exactly which amounts are payable:
LIMIT = 40
payable = [False] * (LIMIT + 1)
payable[0] = True
for n in range(1, LIMIT + 1):
payable[n] = (n >= 4 and payable[n - 4]) or (n >= 5 and payable[n - 5])
print("Not payable:", [n for n in range(1, LIMIT + 1) if not payable[n]])
Output:
Not payable: [1, 2, 3, 6, 7, 11]
So 11 is the largest amount that cannot be paid, confirming that 12 is the right starting point. (For two coprime stamp values a and b, the largest unpayable amount is ab − a − b; here 20 − 4 − 5 = 11.)
Example 10: Fibonacci numbers grow slower than 2n
Let F0 = 0, F1 = 1 and Fn = Fn−1 + Fn−2 for n ≥ 2. Claim: Fn < 2n for all n ≥ 0.
Basis (two cases, because the recurrence looks back two steps): F0 = 0 < 1 = 20 and F1 = 1 < 2 = 21.
Step: for k ≥ 1, assume the claim for all values up to k. Then
F(k+1) = F(k) + F(k−1) < 2^k + 2^(k−1) < 2^k + 2^k = 2^(k+1)
∎ So Fn always fits in n bits. A similar induction shows that the naive recursive fib(n) makes exactly 2Fn+1 − 1 calls, so it makes O(2n) calls.
The Well-Ordering Principle
Well-ordering principle: every non-empty set of non-negative integers has a least element.
This is "obvious" for integers but false for other sets: the positive reals have no least element (for any x > 0, x/2 is smaller), and neither do the integers (no smallest negative number).
Well-ordering, ordinary induction and strong induction are all equivalent: each can be proved from the others. Well-ordering gives the popular minimal counterexample style of proof:
Suppose P(n) fails for some n ≥ n0.
Then the set of counterexamples is non-empty, so it has a smallest member m.
Use the fact that P holds for everything smaller than m to show P(m) holds after all. Contradiction.
Example 11 (induction from well-ordering). Suppose P(0) is true and P(k) → P(k + 1) for all k ≥ 0, but P fails somewhere. Let m be the least n with P(n) false. m ≠ 0 since P(0) is true, so m − 1 ≥ 0 and P(m − 1) is true (m is the least failure). By the step, P(m) is true. Contradiction. So P(n) holds for all n ≥ 0. This is exactly why induction is valid.
Structural Induction
Many objects in computer science are defined recursively: lists, trees, expressions, strings, well-formed formulas. To prove something about all of them, we induct on their structure instead of on a number.
Basis: prove the property for the base objects of the definition.
Recursive step: assuming the property for the parts, prove it for every object built from them by a construction rule.
Example 12: in a full binary tree, leaves = internal nodes + 1
Recursive definition. A full binary tree is either (a) a single node, or (b) a root node whose left and right subtrees are both full binary trees. (So every node has 0 or 2 children.) Let L(T) be the number of leaves and I(T) the number of internal nodes.
Basis: a single node is a leaf. L = 1, I = 0, and 1 = 0 + 1. True.
Recursive step: let T have root r with subtrees T1 and T2, and assume L(T1) = I(T1) + 1 and L(T2) = I(T2) + 1. The leaves of T are exactly the leaves of T1 and T2; the internal nodes are those of T1 and T2 plus r. So
L(T) = L(T1) + L(T2) = (I(T1) + 1) + (I(T2) + 1) = (I(T1) + I(T2) + 1) + 1 = I(T) + 1
∎ For example, a tournament (knockout) with 64 teams is a full binary tree with 64 leaves, so it has 63 internal nodes, i.e. 63 matches.
Example 13: balanced parentheses
Define the set B: (a) the empty string ε is in B; (b) if x ∈ B then (x) ∈ B; (c) if x, y ∈ B then xy ∈ B. Claim: every string in B has equally many "(" and ")".
Basis: ε has 0 of each. Step (b): (x) adds one of each to x, which was balanced by hypothesis. Step (c): counts of xy are sums of the counts of x and y, each equal by hypothesis. ∎
Induction and Programs
Loop invariants
A loop invariant is a statement that is true before the loop starts and stays true after each iteration. Proving it is an induction on the number of iterations.
def total(a):
s = 0
i = 0
# Invariant: s == a[0] + a[1] + ... + a[i-1]
while i < len(a):
s += a[i]
i += 1
return s
print(total([3, 1, 4, 1, 5]))
Output:
14
Basis (before the loop): i = 0 and s = 0, the empty sum. Invariant holds.
Step: if s = a[0] + ⋯ + a[i − 1] before an iteration, then after
s += a[i]; i += 1we have s = a[0] + ⋯ + a[i] with the old i, which is the invariant for the new i.Termination: the loop stops when i = len(a), and then the invariant says s is the sum of all elements.
Recursion: Tower of Hanoi
Moving n discs takes T(1) = 1 move and T(n) = 2T(n − 1) + 1 (move n − 1 discs aside, move the largest, move n − 1 discs back on top). Claim: T(n) = 2n − 1.
Basis: T(1) = 1 = 21 − 1. Step: T(k + 1) = 2T(k) + 1 = 2(2k − 1) + 1 = 2k+1 − 1. ∎ (So 10 discs need 1023 moves.)
Flawed Induction Proofs
Missing basis: "n² + n is odd for every n"
"Step: assume k² + k is odd. Then (k + 1)² + (k + 1) = (k² + k) + 2(k + 1), which is odd + even = odd." The step is perfectly valid! But no basis holds: 1² + 1 = 2 is even (in fact n² + n is always even, as the Proof Techniques chapter showed). A chain of dominoes where none is ever pushed knocks nothing over.
The step that breaks at one point: "all horses are the same colour"
"P(n): in any group of n horses, all have the same colour. Basis: one horse, trivially true. Step: take k + 1 horses. Remove the first: the remaining k have one colour by IH. Remove the last: those k also have one colour. The two groups overlap, so all k + 1 share a colour."
The error is the step from k = 1 to k + 1 = 2. With two horses, removing the first leaves {horse 2} and removing the last leaves {horse 1}. These groups do not overlap, so nothing links their colours. The step must work for every k ≥ n0, and it fails at k = 1.
Too few base cases in strong induction
If the step for k + 1 uses P(k − 3) (as in the postage example), then the step is only valid for k + 1 ≥ n0 + 4. All of P(n0), …, P(n0 + 3) must be checked directly.
Comparing the Forms of Induction
Form | What you assume in the step | Typical use |
|---|---|---|
Ordinary (weak) | P(k) only | Sums, simple divisibility, inequalities |
Strong (complete) | P(n0), …, P(k) | Prime factorisation, postage, recurrences looking back several steps, divide-and-conquer |
Well-ordering | A least counterexample exists | Minimal counterexample proofs, existence of remainders |
Structural | Property holds for the parts | Trees, lists, expressions, formulas, grammars |
Common Mistakes
Assuming what you want to prove. The IH is P(k) for one arbitrary k, not "P(n) for all n".
Skipping the basis or checking the wrong one (see "n² + n is odd").
Starting at the wrong n0 (2n > n² needs n0 = 5).
Working backwards from P(k + 1) to something true, without the steps being reversible.
Not using the IH at all. If your step never uses P(k), either the claim is easy to prove directly or something is wrong.
Too few base cases in strong induction when the step reaches back more than one.
Step that fails for small k (the horses).
Interview and GATE-Style Questions
Q1. Prove 1² + 2² + ⋯ + n² = n(n + 1)(2n + 1)/6.
Basis n = 1: 1 = 1·2·3/6. Step: assume it for k. Then the sum up to k + 1 is k(k+1)(2k+1)/6 + (k+1)² = (k+1)[k(2k+1) + 6(k+1)]/6 = (k+1)(2k² + 7k + 6)/6 = (k+1)(k+2)(2k+3)/6, which is the formula for n = k + 1.
Q2. Prove that 1/(1·2) + 1/(2·3) + ⋯ + 1/(n(n+1)) = n/(n + 1).
Basis: 1/2 = 1/2. Step: k/(k+1) + 1/((k+1)(k+2)) = [k(k+2) + 1]/((k+1)(k+2)) = (k+1)²/((k+1)(k+2)) = (k+1)/(k+2).
Q3. Prove 3 divides n³ + 2n for all n ≥ 0.
Basis: 0. Step: (k+1)³ + 2(k+1) = k³ + 3k² + 3k + 1 + 2k + 2 = (k³ + 2k) + 3(k² + k + 1). The first term is divisible by 3 by the IH, the second clearly is.
Q4. n lines are drawn in a plane, no two parallel and no three through one point. Into how many regions do they divide the plane? Prove it.
R(n) = (n² + n + 2)/2 (values 1, 2, 4, 7, 11, 16 for n = 0…5). Basis: R(0) = 1. Step: the (k+1)-th line meets the k old lines in k distinct points, which cut it into k + 1 pieces; each piece splits one old region into two. So R(k+1) = R(k) + k + 1 = (k² + k + 2)/2 + k + 1 = (k² + 3k + 4)/2 = ((k+1)² + (k+1) + 2)/2.
Q5. In a proof by strong induction that every n ≥ 8 is a sum of 3s and 5s, using "n = (n − 3) + 3", how many base cases are needed?
Three: n = 8, 9, 10 (8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5). The step for n ≥ 11 uses n − 3 ≥ 8.
Q6. A student says: "Strong induction can prove things ordinary induction cannot." True or false?
False. The two principles (and well-ordering) are logically equivalent. Strong induction is a convenience, not extra power.
Q7. Prove 1·1! + 2·2! + ⋯ + n·n! = (n + 1)! − 1.
Basis: 1 = 2! − 1. Step: (k+1)! − 1 + (k+1)(k+1)! = (k+1)!(1 + k + 1) − 1 = (k+2)! − 1. (Checked by program for n up to 19.)
Summary
Induction = basis P(n0) + step P(k) → P(k + 1) for all k ≥ n0. Together they give P(n) for all n ≥ n0.
Write P(k) and P(k + 1) out in full; find P(k) inside P(k + 1); apply the IH.
Choose the basis by checking small values; the step must work from that basis on.
Strong induction assumes all earlier cases; use enough base cases to cover how far back the step reaches.
Well-ordering (least element) is equivalent and gives minimal-counterexample proofs.
Structural induction proves properties of recursively defined objects like trees and strings.
Loop invariants and recursive algorithms are proved correct by induction.
Push the first domino, make sure each one knocks over the next, and you have proved infinitely many statements in a few lines.