Discrete MathDiscrete MathematicsCollege

Mathematical Induction

Prove a base case and an inductive step.

Mathematical induction proves that a statement $P(n)$ holds for every whole number $n \ge n_0$ . It works like dominoes: show the first case is true (the base case), then show that whenever one case is true, the next one must be too (the inductive step). Together these push the truth through every integer.

The inductive step assumes $P(k)$ , the inductive hypothesis, and uses it to derive $P(k + 1)$ . Induction proves summation formulas, divisibility facts and inequalities, and its cousin, recursion, is how programs process lists and trees.

Key ideas

State $P(n)$ clearly before starting.
Base case: verify $P(n_0)$ directly.
Inductive step: assume $P(k)$ , then prove $P(k + 1)$ using it.
Strong induction assumes all earlier cases, not just $P(k)$ .

Worked example

Prove $1 + 2 + \cdots + n = \frac{n(n + 1)}{2}$ for all $n \ge 1$ .

Base: $n = 1$ gives $1 = \frac{1 \cdot 2}{2}$ . True.
Assume $1 + \cdots + k = \frac{k(k + 1)}{2}$ .
Then $1 + \cdots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1) = \frac{(k + 1)(k + 2)}{2}$ .
That is $P(k + 1)$ , so the formula holds for all $n \ge 1$ .

Answer: Proved by induction

Common mistakes

Skipping the base case.
Assuming $P(k + 1)$ instead of proving it.
Checking several cases and calling that a proof.

Practice questions

Try each one, then open the answer. Numerical answers on this page are verified by an automated calculation check.

1.Use the formula to compute $1 + 2 + \cdots + 100$ .
Show answer
$5050$
2.Use $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ for $n = 10$ .
Show answer
$385$
3.What is the remainder when $4^5 - 1$ is divided by 3?
Show answer
$0$

Key ideas

Worked example

Common mistakes

Practice questions

More in Discrete Mathematics