Solving Recurrences by Change of Variable (n = 2^m)

When a recurrence shrinks $n$ by a constant factor (e.g. $n\to n/2$ or $n\to\sqrt{n}$), the substitution $n=2^{m}$ converts division into subtraction, turning a hard recurrence in $n$ into an easy one in $m$ that you can unroll or hit with the Master Theorem.