I’ve been teaching algorithms and data structures for many years and recently was shown a way to solve recurrences that, at least superficially, seems pretty different than the approaches I’ve seen used in the past.
To illustrate, suppose you want to solve this recurrence that comes up in the analysis of mergesort:
$$T(n) = 2T \left(\frac{n}{2} \right) + n.$$
Imagine you (somehow) prove that $T(n) \le n^2$. Feeding that into this recurrence gives that
$$\begin{aligned}T(n) &= 2T \left(\frac{n}{2} \right) + n \\ &\le 2\left( \frac{n^2}{4} \right) + n \\ &= \frac{n^2}{2} + n\end{aligned}$$
We now have a new bound of $T(n) \le \frac{n^2}{2} + n$. If we feed that back into the original recurrence, we get that
$$\begin{aligned}T(n) &= 2T \left(\frac{n}{2} \right) + n \\ &\le 2\left( \frac{n^2}{8} + \frac{n}{4} \right) + n \\ &= \frac{n^2}{4} + 2n\end{aligned}$$
And we now have an even better bound. More generally, we can prove that if $T(n) \le \frac{n^2}{2^k} + kn$, then we also know that $T(n) \le \frac{n^2}{2^{k+1}} + (k+1)n$. This provides a family of bounds of the form $T(n) \le \frac{n^2}{2^r} + rn$ to choose from, and the “tightest” is if we pick $r = \log_2 n$, which bounds the recurrence at $T(n) \le n \log_2 n + n$.
Here’s another example that comes from the analysis of the van Emde Boas tree. Suppose we want to solve the recurrence
$$T(n) = T(\sqrt{n}) + 1.$$
We begin with the very weak bound that $T(n) \le n$. Feeding that into the recurrence gives us
$$\begin{aligned} T(n) &= T(\sqrt{n}) + 1 \\ &\le \sqrt{n} + 1\end{aligned}$$
Now feed that bound back into the recurrence:
$$\begin{aligned} T(n) &= T(\sqrt{n}) + 1 \\ &\le n^{1/4} + 2\end{aligned}$$
And more generally, if $T(n) \le n^{2^{-k}} + k$, then $T(n) \le n^{2^{-(k+1)}} + (k+1)$. This gives a family of bounds of the form $T(n) \le n^{2^{-r}} + r$, and picking $r = \lg \lg n$ gives a bound of $T(n) \le \lg \lg n + 2$.
One final example recurrence that comes from succinct binary rank data structures. Let $T(n)$ be defined as
$$T(n) = n + \frac{n}{\log n} T(\log n).$$
Begin with the bound $T(n) \le n \log n$ and feed it back into the recurrence to get
$$\begin{aligned} T(n) &= n + \frac{n}{\log n} T(\log n) \\ &\le n + \frac{n}{\log n} (\log n \log \log n) \\ &= n + n \log \log n.\end{aligned}$$
Feed the bound $T(n) \le n + n \log \log n$ back into the recurrence to get
$$\begin{aligned} T(n) &= n + \frac{n}{\log n} T(\log n) \\ &\le n + \frac{n}{\log n} (\log n + \log n \log \log \log n \\ &= 2n + n \log \log \log n.\end{aligned}$$
This gives a family of bounds of the form $T(n) \le nr + n \log^{(r+1)}{n},$ which is minimized when $r = \log^\star n$ to give $T(n) \le n\log^\star n.$
The closest I’ve seen to someone doing this is in the paper Top Down Analysis of Path Compression by Seidel and Sharir, which proves a result of this form called the “shifting lemma” that provides a family of bounds on a recurrence by feeding weaker bounds back into a recurrence until the tightest bound is reached.
Is this a well-known strategy for solving recurrences? Does it have a name?
In "An Introduction to the Analysis of Algorithms" by Robert Sedgewick and Philippe Flajolet this method is called "Bootstrapping" (page 67, second edition).
This name is also used by an earlier book "Concrete Mathematics" by Ronald Graham, Donald Knuth, and Oren Patashnik (page 463, second edition).