= Substitution method for a recurrence
Prove a proposed bound by <mathematical induction>, substituting the <inductive hypothesis> for smaller arguments into the <recurrence relation>. Choose its constants so the resulting inequality implies the proposed bound at the current argument, and verify all base cases. A leading-order guess may need an additional lower-order term to make the induction close. The <entropy potential for a divide-and-conquer recurrence> is an example using a linear correction to an $n\log n$ bound.
Back to article page
