Visual walkthrough — Substitution method for recurrences
Before line one, three plain words we will use constantly:
Step 1 — Read the recurrence as a picture
WHAT. Our recurrence is
Read left to right: to do a job of size , I make two smaller jobs of size , then pay units of my own work to stitch them together.
WHY read it this way. A formula full of letters hides its meaning. Turning it into "a box that spawns two half-boxes plus glue" is what lets us guess an answer at all. This exact shape — split, recurse, combine — is Divide and Conquer, and the classic example is Merge Sort Analysis.
PICTURE. One box of size opening into two boxes of size , with the red glue cost labelled.
Step 2 — Make the guess
WHAT. We guess an answer of the form Here means " base 2 of " = "how many times you can halve before reaching 1". The red curve is the ceiling we hope holds.
WHY this shape. Look back at Step 1's picture. Each box splits into halves, so there are levels of splitting before boxes hit size 1. At every level the glue work adds up to about . So the total looks like (per level) (levels) . That reasoning is the Recursion Tree Method — it hands us the guess; substitution's job is only to verify it.
PICTURE. The messy staircase of true values sitting underneath the smooth red ceiling.
Step 3 — Assume the guess for the smaller boxes
WHAT. Induction lets us pretend the guess is already proven for every size below . The two sub-boxes have size , so we are allowed to assume:
This assumed statement is the inductive hypothesis (IH).
WHY we may assume it. This is the engine of Mathematical Induction: to prove a claim for , you are handed the claim for everything smaller for free. Since is strictly smaller than , it qualifies. We are not cheating — we will pay for it with the base case in Step 7.
PICTURE. The two child boxes, each already wearing its red ceiling label .
Step 4 — Substitute the assumption into the recurrence
WHAT. Take the real recurrence and replace each by its assumed ceiling:
The two 2's cancel: .
WHY this is legal. We swapped a quantity for something at least as big. Raising a term on the right side of a keeps the true. This is the move that names the method: we substituted our guess back in.
PICTURE. The two child ceilings flowing up and merging into the parent expression .
Step 5 — Massage the log and expose the leftover
WHAT. Use the log rule (dividing by 2 removes exactly one halving-step). Then:
The piece is the residual: everything not part of our target .
WHY split the log. Before splitting, the target was tangled inside . Splitting cleanly separates "the ceiling we want" from "the crumbs left over". Now we can look straight at the crumbs.
PICTURE. The expression torn into two labelled pieces: the target (black) and the residual (red).
Step 6 — Absorb the residual (choose )
WHAT. Force the residual to be : Pick any . Then
The same we assumed in Step 3 reappears in the conclusion — that is what makes the induction close.
WHY this matters. Contrast with the failed guess : assuming gives . The residual is , which is positive and grows with — no choice of can push it below zero. The constant would have to grow by 1 at each of the levels, secretly rebuilding the we were trying to avoid.
PICTURE. Two number lines of residuals: the winning case (residual dips to zero/below, red arrow points down) versus the failing case (residual stays stuck above zero).
Step 7 — Ground it with a base case
WHAT. Induction is a chain of "pretends"; the base case is the floor it stands on. Check the smallest size, : is some fixed constant, so pick large enough that — and from Step 6. Both demands are satisfiable at once (just take the larger ).
WHY start at 2, not 1. At , , so the ceiling . A ceiling of zero cannot sit above a positive . So we start the induction at , where and the ceiling has room.
PICTURE. The red ceiling curve pinned above the dot at ; a grey warning marker at where the ceiling collapses to 0.
The one-picture summary
Everything above, compressed: the guess (red ceiling), the substitution flowing up from the children, the log-split exposing the residual, the residual absorbed to , and the base case pin.
Recall Feynman: tell it to a 12-year-old
A magic box handles a big job by asking two smaller boxes (each half the size) to help, then does units of gluing itself. We want to know how long the whole thing takes.
First we guess the answer is "about " — because the boxes halve times, and every layer glues about . That guess is a ceiling we draw in red.
Then we play pretend: assume the two little boxes already stay under the ceiling. We plug that into the rule, do a tiny bit of log arithmetic, and look at whatever is left over. If we can pick our fixed number so the leftover is zero or negative, the ceiling holds for the big box too — and we used the same , so the pretending is honest.
Finally we check the tiniest box by hand (at , not , because leaves no room) so the whole tower of pretends stands on solid ground. That's the entire proof — guess a ceiling, feed it to the little boxes, watch the crumbs vanish, nail down the floor.