Mathematical Induction

The Domino Principle

Mathematical induction proves statements for infinitely many natural numbers all at once, like $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ . Think of a line of dominoes: if the first falls, and each falling domino knocks the next, all fall.

Induction requires two strictly enforced parts:

Part	Role	Action
Base case	Starts the chain	Prove the statement for $n = 1$ (or $0$ )
Inductive step	Spreads the chain	Prove $n = k+1$ assuming $n = k$

Neither part alone works: base without step proves only one value; step without base proves nothing.

A chain that actually falls, paired with the sum it proves as it goes

Variants and Pitfalls

Strong induction lets the inductive step assume the statement for all values up to $k$ , not just $k$ . This mirrors recursion in programming, where a base case and smaller step ensure termination.

Pitfall	Why it fails
Missing base case	Never starts the chain of dominoes
Ignoring inductive hypothesis	Re-proves $k+1$ from scratch instead of assuming $k$

The inductive hypothesis is your bridge. You must use the assumption for $k$ to establish $k+1$ .

The Domino Principle

Variants and Pitfalls

Practise this lesson

Discrete Mathematics