Mathematical Induction — Principle, Steps & Examples

Mathematical induction is a proof method for showing that a statement is true for every integer from some starting point onward. To prove a claim for all $n \ge n_0$, you show the first case is true and then show that truth at one integer forces truth at the next integer.

If both parts are correct, the statement holds for every integer in the stated range. That is the whole idea.

How mathematical induction works

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

1. Prove the base case: show that $P(n_0)$ is true.
2. Prove the induction step: show that if $P(k)$ is true for an arbitrary integer $k \ge n_0$, then $P(k+1)$ is also true.

Once those are done, you can conclude that $P(n)$ is true for every integer $n \ge n_0$.

The logic is sequential. The base case starts the chain, and the induction step keeps the chain moving one integer at a time.

Why the base case and induction step both matter

The base case gives you the first true statement. The induction step says truth passes from one integer to the next.

So if $P(n_0)$ is true, then $P(n_0 + 1)$ is true. Then $P(n_0 + 2)$ is true, and so on. Induction does not skip the starting point, and it does not skip the link from one case to the next.

Worked example: proving a sum formula by induction

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$. That means

$$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$.

When to use mathematical induction

Induction is useful when a statement depends on an integer parameter and each case naturally connects to an earlier one. This happens often with sums, divisibility statements, inequalities, recurrence relations, and algorithm proofs.

First, identify the correct starting value. Some claims begin at $n = 0$, some at $n = 1$, and some only make sense for larger integers.

Then check 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.

Common mistakes in induction proofs

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 induction 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.

A useful extension: 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.

Try your own version

Take the claim

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

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