Proof by Induction, Step by Step
7 min read · Free to read
Mathematical induction is the tool for proving that a statement holds for every natural number at once. Whenever you meet a claim that begins with for all n, or a formula that is supposed to work no matter how large n grows, induction is usually the intended method. It replaces the impossible task of checking infinitely many cases with two finite obligations, and once you internalize its shape you can apply it almost mechanically.
The idea rests on a simple picture. Imagine an infinite row of dominoes. If you knock over the first one, and if every domino is close enough that whenever one falls it topples the next, then all of them fall. Induction formalizes exactly this: prove the first case, prove that each case forces the one after it, and you have proved them all. This guide walks through both steps carefully and then works a complete example.
When induction is the right tool
Reach for induction when a statement is indexed by the natural numbers and you want it true for all of them from some starting point onward. Summation formulas, divisibility claims, inequalities that hold for all large n, and many facts about recursively defined structures all fit this shape. The giveaway is a universally quantified n ranging over 0, 1, 2, and beyond.
Induction does not help with a claim about a single fixed number, and it is not the natural choice when there is no notion of moving from one case to the next. But when the truth of the statement at n plus 1 can plausibly be built from its truth at n, induction is almost always the cleanest route.
The base case
The base case is where you knock over the first domino. You verify the statement directly for the smallest value of n in your claim, usually n equals 0 or n equals 1. This is normally a short computation: substitute the starting value into both sides of the claim and check that they agree.
Do not skip this step. The entire chain hangs from the base case, and a formula can fail at its starting value even when the inductive step is flawless. If your claim is meant to hold for all n greater than or equal to 1, your base case must be exactly n equals 1.
The inductive hypothesis and the inductive step
The inductive step is the engine. You assume the statement is true for an arbitrary value n equals k; this assumption is called the inductive hypothesis. Then, using it, you prove the statement for n equals k plus 1. If you can always do this, then truth at any value guarantees truth at the next, and combined with the base case every value is covered.
The single most important habit here is to actually use the inductive hypothesis. A correct inductive step almost always contains a moment where you replace an expression for the k case with what the hypothesis says it equals. If you finish the step without ever invoking the assumption, you have most likely proved the k plus 1 case from scratch, which usually means something is wrong or induction was unnecessary.
- Assume the claim holds at n equals k (the inductive hypothesis).
- Write down what you must prove: the same claim at n equals k plus 1.
- Start from the k plus 1 side and rewrite it to expose the k case.
- Substitute the inductive hypothesis, then simplify to the target.
A worked example: the sum 1 through n
Claim: for every integer n greater than or equal to 1, the sum 1 plus 2 plus 3 up through n equals n times the quantity n plus 1, all divided by 2. In symbols the target is the formula n(n+1)/2.
Base case, n equals 1. The left side is just 1. The right side is 1 times 2 divided by 2, which is 1. Both sides equal 1, so the base case holds.
Inductive step. Assume the formula holds at n equals k, so 1 plus 2 up through k equals k(k+1)/2. We must show the sum up through k plus 1 equals (k+1)(k+2)/2. Start from the left side for k plus 1: it is the sum up through k, plus the new term k plus 1. By the inductive hypothesis the sum up through k is k(k+1)/2, so the whole thing becomes k(k+1)/2 plus (k+1). Factor out (k+1) to get (k+1) times the quantity k/2 plus 1, which equals (k+1) times (k+2)/2. That is exactly (k+1)(k+2)/2, the formula at k plus 1.
Because the base case holds and the inductive step carries truth from k to k plus 1, the formula holds for all n greater than or equal to 1. The pivotal line was substituting the inductive hypothesis for the sum up through k; everything after it was ordinary algebra.
Strong induction
Ordinary induction assumes the claim only at n equals k when proving n equals k plus 1. Strong induction gives you a bigger assumption: you may assume the claim holds for all values from the base up to k, not just at k itself, and use any of them to prove the k plus 1 case. Logically the two forms are equivalent, but strong induction is far more convenient for certain problems.
It shines when the k plus 1 case naturally depends on an earlier case that is not the immediately preceding one. A classic example is proving that every integer greater than 1 has a prime factorization: factoring n into a times b lets you apply the hypothesis to a and b, both smaller than n but not necessarily equal to n minus 1. When a single-step hypothesis feels too weak, switch to the strong form.
A checklist for writing clean inductions
A well-written induction proof announces its structure so the reader never has to guess which step they are in. Label the base case, state the inductive hypothesis explicitly, and mark where you invoke it. This discipline also protects you: most errors surface the moment you write down what the k plus 1 case actually claims and compare it to what you can reach.
Practice by proving a small library of standard results with the same template: the sum of the first n odd numbers equals n squared, and simple inequalities such as 2 to the n exceeding n for n at least 1. Each reuses the identical skeleton, so the method becomes automatic while the algebra stays light.
- State and verify the base case at the exact starting value.
- Write the inductive hypothesis out in full before using it.
- Show the explicit line where the hypothesis is substituted.
- Conclude by citing the base case and the step together.
Frequently asked questions
How is the inductive hypothesis different from assuming what I want to prove?
You assume the claim only for the specific value n equals k, then prove the separate case n equals k plus 1. You are never assuming the k plus 1 case you are trying to establish, so there is no circular reasoning; you are chaining one case to the next.
When should I use strong induction instead of ordinary induction?
Use strong induction when proving the k plus 1 case naturally relies on an earlier case that is not k itself, such as factorization arguments where you split a number into two smaller factors. If the ordinary hypothesis feels too weak, the strong form usually resolves it.
What happens if I forget the base case?
The proof is invalid. The inductive step alone only shows that if the claim holds somewhere it holds at the next value; without a verified starting point the chain never begins, and you can even push through a false formula that has no valid base case.
Can the base case be a value other than 0 or 1?
Yes. The base case must match the smallest value in your claim. If a statement is asserted for all n greater than or equal to 5, you verify n equals 5 as the base case and the induction establishes it for every value from 5 upward.