Mathematical Induction — Principle, Steps & Examples

Mathematical induction is the method you reach for when a statement depends on an integer parameter and each case connects naturally to the one before it. That pattern shows up constantly: sums, divisibility statements, inequalities, recurrence relations, and algorithm proofs. If a claim is supposed to hold for every integer $n \ge n_0$, induction is usually the right tool.

The setup question is always the same. First, identify the correct starting value, since some claims begin at $n = 0$, some at $n = 1$, and some only make sense for larger integers. Then decide what the next valid case is. The usual step is from $k$ to $k+1$, but if the statement is only about even integers, a step from $k$ to $k+2$ may be the right version.

The Steps of an Induction Proof

Write the claim as $P(n)$. Then the proof has this structure:

1. State the claim clearly. Write the statement as $P(n)$ and specify the integers it should hold for, such as all $n \ge 1$.
2. Prove the base case. Show that $P(n_0)$ is true by checking the first required value directly.
3. Assume an arbitrary case. For some integer $k$ in the valid range, assume $P(k)$ is true.
4. Prove the next case. Use that assumption to show $P(k+1)$ is true.
5. State the conclusion. If the base case and induction step are both valid, conclude $P(n)$ holds for all integers in the stated range.

The logic is sequential. The base case gives you the first true statement; the induction step says truth passes from one integer to the next. So $P(n_0)$ true forces $P(n_0+1)$, which forces $P(n_0+2)$, and so on. Induction does not skip the starting point, and it does not skip the link from one case to the next.

A Full Worked Proof

A standard example is the formula

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

for all integers $n \ge 1$. Let

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Base case

Take $n = 1$. The left side is $1$, and the right side is

$$\frac{1(1+1)}{2} = 1$$

So $P(1)$ is true.

Induction step

Assume $P(k)$ is true for some arbitrary integer $k \ge 1$:

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Now prove $P(k+1)$. Start with the left side for $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Using the induction hypothesis,

$$\frac{k(k+1)}{2} + (k+1)$$

Factor out $(k+1)$:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Then simplify:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

That is exactly the formula with $n = k+1$, so $P(k+1)$ is true. Since the base case and induction step are both proved, the formula holds for all integers $n \ge 1$.

Where Proofs Get Stuck, and How to Check Each Step

Each step in the structure has a matching failure mode. Use these as a self-check:

• Proving only the base case. The base case checks the first value only. By itself it does not prove the statement for later integers.
• Using the wrong starting value. If the claim is meant for all $n \ge 2$, proving only $P(1)$ does not help. The base case must match the actual range of the claim.
• Treating the induction hypothesis carelessly. In the step you assume $P(k)$ for one arbitrary integer $k$ in the valid range. You do not assume the full theorem is already proved.
• Proving the wrong next case. If your theorem needs a $k \to k+1$ step, proving a different step does not finish the argument unless you explain why that different step is enough.

When the Step Needs More: Strong Induction

Sometimes proving $P(k+1)$ needs more than just $P(k)$. In that situation, strong induction lets you assume all earlier cases up to $k$ and then prove the next one. The idea is closely related, but the assumption is stronger. It is useful, for example, when a proof depends on splitting a number into smaller parts.

Practice on a Parallel Claim

Now run the same procedure on a new statement. Take

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

and prove it for all integers $n \ge 1$: base case first, then the step from $k$ to $k+1$. If you can write that proof cleanly, the method has clicked.