Proof by Induction Explained Step by Step, Higher Math Guide

Proof by induction proves a statement \(P(n)\) for every whole number \(n\) from some starting value onward, using two checks. The base case shows \(P(1)\) is true (or \(P(n_0)\) for whatever start the problem uses). The inductive step shows that whenever \(P(k)\) is true, \(P(k+1)\) must be true as well. Once both checks pass, every later case follows, one after another, like an endless row of dominoes that has been pushed at the front and is spaced so each one knocks over the next.

The picture: a ladder you can always climb one more rung

The base case puts you on the first rung. The inductive step is a promise: from any rung you stand on, you can reach the next one. Neither check alone is enough. A promise to climb one more rung is useless if you never get on the ladder, and getting on the first rung tells you nothing about rung one hundred. Together they reach every rung, because any rung \(n\) is reached after finitely many single steps from the start.

The inductive step is a conditional statement. You do not prove \(P(k)\) is true. You assume it, as the inductive hypothesis, and show that \(P(k+1)\) follows. If conditional statements still feel slippery, the intro to proofs pathway builds that habit first.

The template, step by step

State \(P(n)\) clearly. Write the exact sentence or equation you will prove, and the starting value of \(n\).
Base case. Check \(P\) at the starting value by direct computation.
Inductive hypothesis. Write: assume \(P(k)\) is true for some fixed \(k\) at least the starting value.
Inductive step. Start from the left side of \(P(k+1)\), find a place to use the hypothesis, and simplify until you reach the right side of \(P(k+1)\).
Conclusion. Say that by induction \(P(n)\) holds for every \(n\) from the starting value onward.

Worked example 1: the sum of the first n whole numbers

Claim: for every \(n \ge 1\), \[ 1 + 2 + \cdots + n = \frac{n(n+1)}{2}. \] Base case. When \(n = 1\) the left side is \(1\) and the right side is \(\frac{1 \cdot 2}{2} = 1\). They match.

Inductive hypothesis. Assume \(1 + 2 + \cdots + k = \frac{k(k+1)}{2}\) for some \(k \ge 1\).

Inductive step. The sum up to \(k+1\) is the sum up to \(k\) plus one more term: \[ 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}. \] That last expression is exactly \(\frac{n(n+1)}{2}\) with \(n = k+1\). So \(P(k+1)\) holds, and by induction the formula is true for every \(n \ge 1\).

Spot check at \(n = 4\): \(1 + 2 + 3 + 4 = 10\), and \(\frac{4 \cdot 5}{2} = 10\). A spot check is not a proof, but it catches algebra slips before you write the argument up.

Worked example 2: a divisibility claim

Claim: for every \(n \ge 1\), the number \(4^n - 1\) is divisible by \(3\).

Base case. When \(n = 1\), \(4^1 - 1 = 3\), which is divisible by \(3\).

Inductive hypothesis. Assume \(4^k - 1 = 3m\) for some whole number \(m\).

Inductive step. Rewrite the next case so the hypothesis appears inside it: \[ 4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(4^k - 1) + 3 = 4(3m) + 3 = 3(4m + 1). \] The result is \(3\) times a whole number, so \(4^{k+1} - 1\) is divisible by \(3\). By induction the claim holds for every \(n \ge 1\). Spot check: \(4^3 - 1 = 63 = 3 \cdot 21\).

The trick in both examples is the same. Write the \(k+1\) case so the \(k\) case sits visibly inside it, then use the hypothesis on that piece.

Strong induction, briefly

Sometimes \(P(k+1)\) depends on several earlier cases, not just \(P(k)\). Strong induction lets you assume \(P\) holds for every value from the start up to \(k\), then prove \(P(k+1)\). It is no more powerful in what it can prove, but it is often easier to write, for example when every whole number above \(1\) is shown to be a product of primes by splitting it into two smaller factors. Richard Hammack's open textbook Book of Proof treats ordinary and strong induction in its Chapter 10.

Checkpoints

In your own words, why does the inductive step not assume what you are trying to prove?
Prove by induction that \(1 + 3 + 5 + \cdots + (2n - 1) = n^2\) for every \(n \ge 1\). (Base case: \(1 = 1^2\). In the step, add the next odd number, \(2k + 1\).)
Prove that \(2^n \ge n + 1\) for every \(n \ge 1\). Which base case do you need, and where does the inequality get used in the step?

Common mistakes

Skipping the base case. A false statement can still have a valid looking inductive step. For example, "\(n + 1 = n\)" would imply "\((n + 1) + 1 = n + 1\)", yet the statement is never true. The base case is what anchors the chain.
Assuming \(P(k+1)\). Start from one side of the \(k+1\) statement and work toward the other side. Do not write the \(k+1\) equation and manipulate both sides as if it were already known.
A step that silently fails for small \(k\). The classic "all horses are the same colour" argument breaks exactly when moving from \(1\) to \(2\), because the two overlapping groups it relies on share no horse. Check that your step works for the smallest \(k\) it is supposed to cover.
Never using the hypothesis. If the inductive step does not use \(P(k)\) anywhere, either the statement is easy enough for a direct proof or the step has a gap.

Related tools

The sequence calculator adds finitely many terms, which is handy for spot checking a sum formula at a few values of \(n\). Matching values for a few cases is evidence, not a proof. Only the induction argument covers every \(n\).

Sources

Frequently asked questions

What are the two steps of proof by induction?

The base case shows the statement is true for the first value, usually n = 1. The inductive step shows that if the statement is true for some n = k, it must also be true for n = k + 1. Together they cover every whole number from the start onward.

Why is assuming P(k) in the inductive step not circular?

You are not claiming P(k) is true for every k. You are proving a conditional: if P(k) holds, then P(k + 1) holds. Combined with the base case, that conditional pushes the truth forward one value at a time.

What is the difference between ordinary and strong induction?

Ordinary induction assumes only P(k) to prove P(k + 1). Strong induction assumes P holds for every value from the start up to k. Strong induction is convenient when the next case depends on several earlier ones, such as factoring a number into smaller factors.

Is checking many values of n the same as a proof?

No. Checking cases is evidence and a good way to catch algebra slips, but it covers only the values you tried. Induction is what covers every n.

Proof by induction, explained step by step