guess and verify by induction

When you face a recurrence you do not immediately recognise, the workable strategy is to make an educated guess about its growth and then defend that guess rigorously. This is the heart of the substitution method, viewed as two separate skills: the creative leap of guessing, and the disciplined check by induction.

Verifying by induction means treating 'T(n) is at most (or at least) some formula g(n)' as a statement to prove for every n. The inductive hypothesis is that the bound holds for all smaller inputs (this is strong induction, since the recurrence may reference several smaller sizes). You substitute the hypothesis into the right-hand side of the recurrence and show the same bound g(n) re-emerges, and you separately verify the base case for small n. Where do good guesses come from? Three honest sources: a recursion tree that suggests the total; pattern-matching to the Master Theorem's three cases; or trying neighbours of a wrong guess — if T(n) <= c n is too weak, try c n log n; if it overshoots, try a subtracted lower-order term.

The value of separating 'guess' from 'verify' is that it stops you trusting a plausible-looking total without proof. A recursion tree gives a strong hint, but adding up the levels informally can miss a logarithmic factor or a boundary effect; the induction is the safety net that catches it. Conversely, if your verification fails, the failure usually tells you how to fix the guess — too weak, too strong, or off by a lower-order term — making this a productive loop rather than a dead end.