The Principle of Mathematical Induction

Mathematical induction is one of the most powerful and elegant proof techniques in mathematics. It allows us to prove that a statement is true for all natural numbers by establishing just two key facts: a starting point and a stepping rule.

The Principle

Suppose we are given a sequence of statements $Y_1, Y_2, Y_3, \ldots$ . If the first statement $Y_1$ is true, and if from the truth of $Y_k$ it follows that $Y_{k+1}$ is true, then all statements in this sequence are true.

This principle can be visualized like dominoes standing in a row: if you knock down the first domino (base case) and each domino knocks down the next one (inductive step), then all dominoes will eventually fall.

Key Components

Base Case

The base case of induction is the statement $Y_1$ . Sometimes several initial statements $Y_1, Y_2, \ldots, Y_k$ are taken as the base, but most commonly the base case is just the first statement.

The base case establishes that our statement is true for the smallest value we care about (often $n = 1$ , but it could be $n = 0$ or any other starting point).

Induction Hypothesis

The induction hypothesis is the assumption that the statement $Y_n$ is true for $n = k$ .

This is a critical step where we assume what we are trying to prove, but only for a specific value $k$ . This assumption is then used to prove the statement for $k+1$ .

Inductive Step

The inductive step is the proof that the truth of $Y_k$ implies the truth of $Y_{k+1}$ .

This is where the real work happens. We use the induction hypothesis (that $Y_k$ is true) to demonstrate that $Y_{k+1}$ must also be true.

When to Use Induction

Mathematical induction is particularly useful for proving statements that:

Involve formulas for sums (e.g., $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ )
Make claims about divisibility for all natural numbers
Involve inequalities that hold for all sufficiently large $n$
Describe properties that naturally build from smaller cases
Relate to recursive definitions or sequences

Common Variations

Strong Induction

In strong induction, instead of assuming just $Y_k$ is true, we assume that $Y_1, Y_2, \ldots, Y_k$ are all true, and use this to prove $Y_{k+1}$ .

This is useful when the $(k+1)$ -th case depends on multiple previous cases, not just the $k$ -th one.

Backward Induction

In some problems, especially in game theory and combinatorics, we work backwards from large values of $n$ to smaller ones, proving that if something holds for $n+1$ , it holds for $n$ .

Tips for Writing Induction Proofs

State clearly what you are proving: Write out the statement $Y_n$ explicitly
Verify the base case: Don't skip this! Compute both sides and check they are equal
State the induction hypothesis: Write "Assume that for $n = k$ , we have..."
Show your work in the inductive step: Clearly indicate where you use the hypothesis
Conclude: State that by the principle of mathematical induction, the statement holds for all $n$

Examples

The practice problems below demonstrate induction in action across different areas of mathematics:

Number theory: Proving divisibility properties
Algebra: Establishing formulas for sums and products
Geometry: Showing existence of certain constructions for all $n$
Combinatorics: Proving properties about partitions and configurations

Try solving these problems to develop your intuition for when and how to use induction!