The same move you already made
In the previous guide you proved a loop invariant in three parts: it holds before the loop starts (initialization), each pass keeps it true (maintenance), and at exit it hands you the result (termination). If that felt like one trick reused three times, you were noticing something real. The first two parts are exactly mathematical induction, just wearing the clothes of a loop. This guide pulls off the disguise and meets induction directly, because once you see it bare, you can use it on recursion too — where there is no loop boundary to lean on.
The classic picture is an infinite line of dominoes. You want them all to fall, but you cannot push each one — there are infinitely many. So you show two things: the first domino falls, and each domino, whenever it falls, knocks over the next. Those two facts together force the whole line down. That is the entire idea of proof by induction: prove a statement P(n) for the smallest n, then prove that P(n) being true forces P(n+1) to be true, and you have proved P(n) for every n at once, with a single finite argument.
The two obligations, stated cleanly
To prove "P(n) holds for all n at least n0", you owe exactly two things. The base case: prove P(n0) outright, by direct checking. The inductive step: prove that for every n at least n0, if P(n) holds then P(n+1) holds. That word "if" matters — inside the step you are allowed to assume P(n) for free; this assumption is called the induction hypothesis. You are not assuming what you want to prove for the final answer; you are only assuming it for the immediately smaller case, and using it as a stepping stone to the next.
Here is the smallest honest example, worked end to end. Claim: 1 + 2 + ... + n = n(n+1)/2 for all n at least 1. Base case n = 1: the left side is 1, the right side is 1 times 2 over 2, which is 1. They match, so P(1) holds. Inductive step: assume P(n), that 1 + 2 + ... + n equals n(n+1)/2. Then 1 + 2 + ... + n + (n+1) equals n(n+1)/2 + (n+1), and factoring out (n+1) gives (n+1)(n+2)/2 — which is precisely P(n+1). Both obligations met, so the formula holds for every n. Notice the step did real algebra; it did not just restate the goal.
When one domino is not enough: strong induction
Ordinary induction lets case n+1 lean on exactly case n — each domino is knocked over by the one right before it. But many algorithms do not split that way. A divide-and-conquer method on size n recurses on size n/2; some recursions call sizes n-1 and n-2; others call several smaller sizes at once. For these, leaning on "the immediately previous case" is the wrong shape entirely — the case you need might be half as big, not one smaller.
Strong induction widens the hypothesis to fit. To prove P(n), you may assume P(k) for every smaller k at once — all of them, not just k = n-1. It is as if each domino can be toppled by any combination of the dominoes before it. A clean example: every integer n at least 2 factors into primes. If n is prime, done. If n = a times b with both a and b strictly between 1 and n, then by the strong hypothesis a and b already factor into primes (each is smaller than n), so stitching their factorizations together factors n. We used two cases smaller than n, neither of them n-1 — which plain induction would never have handed us.
Two honest notes. First, with the strong form a separate base case is often unnecessary on the surface, because the smallest n has no smaller k, so the hypothesis is empty and you must still establish that smallest case directly — the obligation does not vanish, it just hides. Second, strong induction is no more powerful than ordinary induction (each can simulate the other), it is merely more convenient when a case leans on several or far-away smaller cases. Reach for it when the recursion does not step down by exactly one.
Trusting a recursion: induction over input size
Strong induction is the natural way to trust a recursive algorithm, and the framing is wonderfully practical: treat each recursive call like a colleague you trust. Assume every recursive call returns the correct answer for its smaller input (that is the induction hypothesis), then prove only that you combine those correct answers into a correct answer for the whole. This is induction on the recursive calls — induction over the size of the input, with the recursive calls playing the role of the hypothesis. You never reason about the entire call tree at once; you check just one level and let induction sweep up the rest.
- Base case: the non-recursive inputs (small enough to answer directly — an empty or one-element list) return the right answer outright. For merge sort, a list of length at most 1 is already sorted.
- Inductive hypothesis: assume every recursive call, made on a strictly smaller input, returns the correct result. Treat each returned value as a black box that is simply correct.
- Inductive step: prove the combine step turns those correct sub-answers into the correct answer for the current input. For merge sort, merging two sorted halves yields one sorted whole.
- Check the inputs really shrink: every recursive call must be on a strictly smaller input, so the chain of assumptions bottoms out at the base case rather than circling forever.
Put it together on merge sort and the proof is two lines. Base: length at most 1 is sorted. Step: by the hypothesis the two recursive calls correctly sort the left and right halves; the merge routine correctly interleaves two sorted sequences into one sorted sequence; therefore the result is sorted. Because each half is strictly smaller than the whole, the assumptions descend all the way to the base case and the argument is sound. That is the whole correctness proof — short because induction carried the infinite part for you.
The shrinking is not optional. If a recursive call were on an input that is not strictly smaller (say, recursing on the same size), the induction would be circular and the procedure might never halt. That same strictly-decreasing size is also a well-founded measure — so this single fact does double duty, justifying the hypothesis AND proving termination, the subject of the next guide.
More flavors, and the honest fine print
Numbers are not the only thing that comes in "a smallest one, plus bigger ones built from smaller ones". A tree is a node holding smaller subtrees; a list is a head plus a smaller tail; an arithmetic expression is a number or two smaller expressions joined by an operator. Structural induction reasons over exactly these: prove the property for the base shapes, then prove that each building rule preserves it. It is really strong induction over the size of the structure, which is why it is sound for the very same reason — the parts are always strictly smaller, so the recursion bottoms out. It is the cleanest framing whenever a recursion mirrors the shape of its data.
Induction also runs underneath the running-time analysis you met earlier, not only correctness. To solve a recurrence like T(n) = 2 T(n/2) + O(n) by the substitution method, you guess a bound — here T(n) = O(n log n) — and then verify it by induction: assume the bound for all smaller inputs, plug those into the recurrence, and check the algebra closes for n. The bound is not pulled from thin air; induction is what certifies the guess. Even the master theorem, which lets you skip this work for common divide-and-conquer recurrences, is proved by an induction over the recursion's levels.
T(n) = 2 T(n/2) + O(n) guess: T(n) <= c * n log n verify: assume T(n/2) <= c*(n/2)*log(n/2), substitute, show T(n) <= c*n*log n
Two pieces of honest fine print. First, induction proves a statement is true, but gives no intuition for why it is true or how to discover the right statement to prove — that creative leap (the right invariant, the right bound) is on you; the induction only audits it. Second, a single gap silently voids everything: a missing base case, a structural-induction proof that forgets a constructor (most often the empty tree or empty list), or a step that secretly needs a smaller case you never assumed. A proof that overlooks one case is not a slightly-weaker proof — it is no proof. That care is exactly what separates a real argument from a plausible-looking one, the theme this whole rung is built on.