Mathematical Induction — Definition, Formula & Examples

Mathematical induction is a proof technique that shows a statement is true for every natural number. You prove it holds for the first case, then prove that whenever it holds for one number, it must hold for the next.

Let $P(n)$ be a proposition defined for integers $n \geq n_0$ . If (1) $P(n_0)$ is true (base case), and (2) for every integer $k \geq n_0$ , $P(k) \implies P(k+1)$ (inductive step), then $P(n)$ is true for all integers $n \geq n_0$ .

How It Works

Think of induction like an infinite line of dominoes. First, you knock over the first domino (the base case). Then you show that any domino falling will knock over the next one (the inductive step). Together, these guarantee every domino falls. In practice, the inductive step begins by assuming

P(k)

is true — this assumption is called the inductive hypothesis — and then using it to prove

P(k+1)

Worked Example

Problem: Prove that for all natural numbers n ≥ 1, the sum 1 + 2 + 3 + ... + n equals n(n+1)/2.

Base Case: Check the statement for n = 1. The left side is 1. The right side is 1(1+1)/2 = 1. They match, so P(1) is true.

P(1): \quad 1 = \frac{1(1+1)}{2} = 1 \quad \checkmark

Inductive Hypothesis: Assume the formula holds for some arbitrary integer k ≥ 1.

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

Inductive Step: Show P(k+1) is true. Add (k+1) to both sides of the hypothesis and simplify the right side.

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

Answer: The result matches the formula with n = k+1, so by mathematical induction, the formula holds for all n ≥ 1.

Why It Matters

Induction is the standard way to prove formulas, divisibility properties, and inequalities involving natural numbers. It appears throughout discrete mathematics, computer science (proving algorithm correctness), and any course that requires formal proofs.

Common Mistakes

Mistake: Skipping the base case and only doing the inductive step.

Correction: Both parts are required. Without the base case, the inductive step has no starting point — like showing dominoes can topple each other without ever pushing the first one.