Induction is often introduced with dominoes. If the first domino falls, and each falling domino knocks over the next one, then all dominoes fall. The analogy is useful, but only if students understand both parts.
A proof by induction has two jobs:
- Prove the statement is true at the starting point.
- Prove that truth at one step forces truth at the next step.
The first job is the base case. The second is the inductive step.
Why examples are not enough
Suppose we want to prove that
1 + 2 + 3 + ... + n = n(n + 1)/2
Testing n = 1, n = 2, and n = 3 is useful, but it is not proof. A pattern can survive many examples and still fail later.
Induction gives a way to prove infinitely many statements using a finite argument. We do not check every domino. We prove the chain mechanism.
The inductive assumption
The most common student mistake is using the inductive assumption too loosely. In the example above, the assumption is not “the formula is true for everything.” It is specifically:
Assume 1 + 2 + ... + k = k(k + 1)/2 for some particular k.
Then we must prove:
1 + 2 + ... + k + (k + 1) = (k + 1)(k + 2)/2
Start with the left side:
1 + 2 + ... + k + (k + 1)
Use the assumption only for the part it covers:
= k(k + 1)/2 + (k + 1)
Then factor:
= (k + 1)(k/2 + 1)
= (k + 1)(k + 2)/2
That proves the next case.
What the proof really says
The base case proves the first domino falls. The inductive step proves that any fallen domino knocks over the next one. Together, they imply every domino falls.
Without the base case, the chain may never start. Without the inductive step, the first domino may fall alone.
This is why both parts matter.
Strong induction
Sometimes the next case depends on more than the previous case. Strong induction lets us assume all earlier cases are true in order to prove the next one.
For example, to prove that every integer greater than 1 can be written as a product of primes, we may need to break a number into two smaller factors. Those factors are not necessarily exactly one less than the original number. Strong induction allows us to use the statement for all smaller numbers.
The logic is still domino-like, but each domino may rely on several earlier dominoes.
Common mistakes
One mistake is proving something that already assumes the result. If a student starts the inductive step by writing the formula for k + 1, they may be assuming what they need to prove.
Another mistake is forgetting the base case. A beautiful inductive step does not prove the statement if the chain has no starting point.
A third mistake is changing the statement mid-proof. The statement for k and the statement for k + 1 must match the original claim exactly.
A COSMO practice routine
Have students annotate induction proofs with three colors:
- base case
- inductive assumption
- target statement
This forces them to see the structure rather than only the algebra.
Then ask them to write a one-sentence explanation of why the proof covers all natural numbers. If they cannot explain the chain logic in words, the symbols may be floating.
The deeper habit
Induction teaches students to prove a pattern by proving its method of continuation. That is a powerful habit. In math and computer science, many objects are built step by step: sequences, trees, algorithms, recursions, and definitions.
Induction is the proof technique that matches that construction.