Solving or approximating recurrence relations for sequences of numbers

Question

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growth.

Examples are

1. The runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$:

   $\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$

2. The Fibonacci sequence:

   $\qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}$

3. The number of Dyck words with $n$ parenthesis pairs:

   $\qquad\begin{align} C_0 &= 1 \\ C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i} \end{align}$

4. The mergesort runtime recurrence on lists of length $n$:

   $\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

What are methods to solve recurrence relations? We are looking for

• general methods and
• methods for a significant subclass

as well as

• methods that yield precise solutions and
• methods that provide (bounds on) asymptotic growth.

^{This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.}

Answer 1

Converting Full History to Limited History

This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence $$ T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big) $$ which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the randomly chosen pivot.) For any integer $n$, the value of $T(n)$ depends on all $T(k)$ with $k<n$. Recurrences of this form are called full history recurrences.

To solve this recurrence, we can transform it into a limited history recurrence, where $T(n)$ depends on only a constant number of previous values. But first, it helps to simplify the recurrence a bit, to collect common terms and eliminate pesky fractions. \begin{align*} n T(n) &= n^2 + 2\sum_{k=1}^{n-1} T(k) \end{align*} Now to convert to a limited-history recurrence, we write down the recurrence for $T(n-1)$, subtract, and regather terms: \begin{align*} (n-1) T(n-1) &= (n-1)^2 + 2\sum_{k=1}^{n-2} T(k) \\ \implies nT(n) - (n-1)T(n-1) &= (2n-1) + 2T(n-1) \\[1ex] \implies n T(n) &= (2n-1) + (n+1) T(n-1) \\[1ex] \implies \frac{T(n)}{n+1} &= \frac{2n-1}{n(n+1)} + \frac{T(n-1)}{n} \end{align*}

Now if we define $t(n) = T(n)/(n+1)$ and replace the fraction $\frac{2n-1}{n(n+1)}$ with the simpler asymptotic form $\Theta(1/n)$, we obtain the much simpler recurrence $$ t(n) = \Theta(1/n) + t(n-1). $$ Expanding this recurrence into a summation immediately gives us $t(n) = \Theta(H_n) = \Theta(\log n)$, where $H_n$ is the $n$th harmonic number. We conclude that $\boldsymbol{T(n) = \Theta(n\log n)}$.

Answer 2

Generating Functions $\newcommand{\nats}{\mathbb{N}}$

Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.

This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this method to obtain asymptotics (even if the precise result can not be obtained).

The Method

Let $(a_n)_{n\in\nats}$ a series of numbers. Then, the formal power series

$\qquad \displaystyle A(z) = \sum_{n=0}^\infty a_nz^n$

is the ordinary generating function¹ of $(a_n)_{n\in\nats}$. The coefficients in the series expansion of $A(z)$ equal the sequence, i.e. $[z^n]A(z) = a_n$. For example, the ordinary generating function of the famous Catalan numbers $C_n$ is

$\qquad \displaystyle C(z) = \frac{1 - \sqrt{1 - 4z}}{2z}$.

The definition of $A$ is also our ansatz for solving a recurrence. This works best for linear recurrences, so assume for the sake of simplicity a recurrence of the form

$\qquad \begin{align} a_0 &= c_0 \\ &\vdots \\ a_{k-1} &= c_{k-1} \\ a_n &= f(n) + \sum_{i=1}^k b_i a_{n-i} \qquad , n \geq k \end{align}$

for some fixed $b_1, \dots, b_k \in \mathbb{R}$ and $f(n) : \nats \to \nats$ a function independent of all $a_i$. Now we simply insert both anchors and recursive part into the ansatz, that is

$\qquad \begin{align} A(z) &= \sum_{n=0}^\infty a_nz^n \\ &= c_0z^0 + c_1z^1 + \dots + c_{k-1}z^{k-1} + \sum_{n=k}^\infty \left[ f(n) + \left(\sum_{i=1}^k b_i a_{n-i}\right)\right] z^n \end{align}$

Using mechanics of sum manipulation, properties of formal power series and known identities², the last right-hand side has to be brought into closed forms, typically in terms of $A(z)$. The resulting equation can (often) be solved for $A(z)$. The series expansion of the result (which may be easily obtained, known or otherwise approachable) is essentially the solution.

Good introductions can be found in Wilf's book [3] and in GKP [4]. Advanced material has been collected by Flajolet and Sedgewick [5].

Example

Consider

$\qquad \begin{align} a_0 &= 1 \\ a_1 &= 2 \\ a_n &= 5n + 3a_{n-1} - 2a_{n_2} \qquad , n > 1 \end{align}$

We calculate:

$\qquad \begin{align} A(z) &= \sum_{n=0}^\infty a_n z^n \\ &= 1 + 2z + \sum_{n=2}^\infty \left[ 3a_{n-1} - 2a_{n-2} + 5n\right]z^n \\ &= 1 + 2z + 3\sum_{n=2}^\infty a_{n-1}z^n - 2\sum_{n=2}^\infty a_{n-2}z^n + 5\sum_{n=2}^\infty n z^n \\ &= 1 + 2z + 3z\sum_{n=1}^\infty a_nz^n - 2z^2\sum_{n=0}^\infty a_n z^n + 5\sum_{n=2}^\infty n z^n \\ &= 1 + 2z + 3z(A(z) - a_0) - 2z^2A(z) + 5 \left( \frac{z}{(1-z)^2} - z\right) \\ &= 1 - 6z + (3z - 2z^2)A(z) + \frac{5z}{(1-z)^2} \end{align}$

This solves to

$\qquad \begin{align} A(z) &= \frac{1 - 3z + 13z^2 - 6z^3}{(1-2z)(1-z)^3} \\ &= \frac{16}{1-2z} - \frac{5}{1-z} - \frac{5}{(1-z)^2} - \frac{5}{(1-z)^3} \\ &= 16\sum_{n=0}^\infty 2^n z^n - 5\sum_{n=0}^\infty z^n - 5 \sum_{n=0}^\infty (n+1) z^n - 5\sum_{n=0}^\infty \frac{(n+1)(n+2)}{2} z^n \end{align}$

Now we can finally read off

$\qquad \begin{align} a_n &= 16 \cdot 2^n - 5 - 5(n+1) - \frac{5}{2}(n+1)(n+2) \\ &= 2^{n+4} - \frac{5}{2}n^2 - \frac{25}{2}n - 15 \end{align}$

Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See here for a more involved, less mechanic example.

Also note that the general techniques also work if the objects sought are complex numbers, or even polynomials.

A Shortcut

For linear and homogeneous recurrences, i.e. such of the form

$\qquad \begin{align} a_0 &= c_0 \\ &\vdots \\ a_{k-1} &= c_{k-1} \\ a_n &= \sum_{i=1}^k b_i a_{n-i} \qquad , n \geq k \end{align}$

the above goes through in exactly the same way, every time. By performing above calculation symbolically, we find the following lemma. Let

$\qquad \displaystyle z^k - b_1 z^{k-1} - b_2 z^{k-2} - \dots - b_k$

be the characteristic polynomal (of the recurrence). Let furthermore $\lambda_1, \dots, \lambda_l$ the (pairwise distinct) zeros of said polynomial with multiplicity $r_i$, respectively. Then, the desired coefficient is given by

$\qquad \displaystyle a_n = \sum_{i=1}^l \sum_{j=1}^{r_i} b_{i,j} \cdot n^{j-1} \cdot \lambda_i^n$

with unknown $b_{i,j}$. As the characteristic polynomial has degree $k$, there are exactly $k$ (complex) zeros, i.e. the $r_i$ sum to $k$. Therefore, the missing coefficients can be determined by solving the linear equation system with $k$ equations obtained by equating above formula with any $k$ of the $a_n$ (e.g. the anchors).

Asymptotics

Getting to a closed form for $A(z)$ is usually the easy part. Expressing it in generating functions we know the coefficiencts of (as we did in the example) quickly becomes hard, though. Examples are $C(z)$ from above and the one for the number of Dyck words mentioned in the question.

One can employ complex analysis machinery, specifically singularity analysis, in order to obtain asymptotics for the coefficients; buzzwords include Darboux's method and saddle-point method. These are based on the residue theorem and Cauchy's integral formula. See [6] for details.

---

1. You can do similar things with exponential, Dirichlet and some other generating functions. Which works best depends on the sequence at hand and in particular whether you find the necessary closed forms.
2. For example from the TCS Cheat Sheet or [3].
3. generatingfunctionology by H. Wilf (1994, 2nd ed.) -- available for free download
4. Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik (1994, 2nd ed.)
5. Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd edition, 2013) -- available for free download
6. Analytic Combinatorics by P. Flajolet and R. Sedgewick (2009) -- available for free download

Answer 3

Master Theorem

The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is often incredibly easy to apply. On the other hand, it can only be applied to recurrences of the following form:

$\qquad \displaystyle T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n) $

with $a \geq 1, b > 1$. There are three cases

1. $\quad \displaystyle f \in O\left( n^{\log_b (a) - \varepsilon} \right)$

   for some $\varepsilon > 0$;

2. $\quad \displaystyle f \in \Theta\left( n^{\log_b a} \log^{k} n \right)$,

   for some $k \geq 0$;

3. $\quad \displaystyle f \in \Omega\left( n^{\log_b (a) + \varepsilon} \right)$

   for some $\varepsilon > 0$ and

   $\quad \displaystyle a f\left( \frac{n}{b} \right) \le c f(n)$

   for some $c < 1$ and $n \to \infty$.

which imply the asymptotics

1. $T \in \Theta\left( n^{\log_b a} \right)$,
2. $T \in \Theta\left( n^{\log_b a} \log^{k+1} n \right)$ and
3. $T \in \Theta \left(f \right)$,

respectively. Note that the base cases are not stated or used here; that makes sense, considering we are only investigating asymptotic behaviour. We silently assume that they are some constants (what else can they be. Which constants we don't see is irrelevant, they all vanish in the $\Theta$.

Examples

1. Consider the recurrence

   $\qquad \displaystyle T(n) = 4T\left(\frac{n}{3}\right) + n$.

   With $f(n) = n, a=4$ and $b=3$ -- note that $\log_b a \approx 1.26$ we see that case one applies with $\varepsilon = 0.25$. Therefore, $T \in \Theta(n^{\log_3 4}) = \Theta(n^{1.261\dots})$.

2. Consider the recurrence

   $\qquad \displaystyle T(n) = 2T(n/2) + n$.

   With $f(n) = n, a=2$ and $b=2$ -- note that $\log_b a = 1$ we see that case two applies with $k=0$. Therefore, $T \in \Theta(n \log n)$.

3. Consider the recurrence

   $\qquad \displaystyle T(n) = 3T\left(\frac{n}{4}\right) + n$.

   With $f(n) = n, a=3$ and $b=4$ -- note that $\log_b a \approx 0.79$ we see that case three applies with $\varepsilon = 0.2$ and $c=1$. Therefore, $T \in \Theta(n)$.

4. Consider the recurrence

   $\qquad \displaystyle T(n) = 16T\left(\frac{n}{4}\right) + n!$

   Here we have $a = 16$, $b=4$ and $f(n) = n!$ - many standard examples will have polynomial $f$, but this is not a rule. We have $\log_b a = 2$, and case three applies again. In this instance though, we can choose any $\varepsilon$ and $c > 0$ as $n! \in \Omega(n^{k})$ for all $k$. Hence $T \in \Theta(n!)$.

Further reading

• It is well possible that none of the Master theorem's cases applies. For example, the subproblems may not have equal size or have a more complex form. There are some extensions to the Master theorem, for instance Akra-Bazzi [1] or Roura [2]. There is even a version that works for discrete recurrences (i.e. floors and ceils are used on the recursive parameters) and provides sharper results [3].

• Usually, you have to massage the actual recurrence relation you have into shape before you can apply the Master theorem. Common transformations that preserve asymptotics include dropping floors and ceils as well as assuming $n=b^k$. Take care not to break things here; refer to [4] section 4.6 and this question for details.

---

1. On the Solution of Linear Recurrence Equations by M. Akra and L. Bazzi (1998)
2. An improved master theorem for divide-and-conquer recurrences by S. Roura (1997)
   ^{Refers to other improved master theorems.}
3. A master theorem for discrete divide and conquer recurrences by M. Drmota and W. Szpankowski (2011)
4. Introduction to Algorithms by Cormen et al. (2009, 3rd edition)

Answer 4

Guess & Prove

Or how I like to call it, the "$\dots$ technique". It can be applied to all kinds of identities. The idea is simple:

Guess the solution and prove its correctness.

This is a popular method, arguably because it usually requires some creativity and/or experience (good for showing off) but few mechanics (looks elegant). The art here is to make good, educated guesses; the proof is (in our case) usually a more or less simple induction.

When applied to recurrences, "guessing" is typically done by

• expanding the recurrence a couple of times,
• figuring out the anchor and
• guessing the pattern for the intermediate (the $\dots$).

Simple Example

$\qquad \begin{align} s_0 &= s_1 = s_2 = 1 \\ s_n &= 5s_{n-3} + 6 \qquad\qquad n \geq 2 \end{align}$

Let us expand the definition of $s_n$ a few times:

$\qquad \begin{align} s_n &= 5s_{n-3} + 6 \\ &= 5(5s_{n-6} + 6) + 6 \\ &= 5(5(5s_{n-9} + 6) + 6) + 6 \\ &\ \vdots \\ &= \underbrace{5(5(5( \dots 5\cdot 1}_{n \div 3 \text{ times}} + \underbrace{6 \dots ) + 6) + 6) + 6}_{n \div 3 \text{ times}} \end{align}$

Here, the pattern is easy to spot and it leads us to the claim:

$\qquad \begin{align} s_n &= 5^{\left\lfloor\frac{n}{3}\right\rfloor} + 6\cdot \sum_{i=0}^{\left\lfloor\frac{n}{3}\right\rfloor - 1} 5^i \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor} - \frac{6}{4} \end{align}$

Now we prove the identity by induction. For $n \in \{0,1,2\}$, we can establish correctness by a plugging in the respective value. Assuming the identity holds for all $n' \leq n$ for an arbitrary but fixed $n \geq 3$, we calculate

$\qquad \displaystyle \begin{align} s_{n+3} &= 5s_n + 6 \\ &= 5\cdot \left( \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor} - \frac{6}{4} \right) + 6 \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor + 1} - \frac{6}{4} \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n+3}{3}\right\rfloor} - \frac{6}{4} \end{align}$

which proves the identity by the power of induction.

If you try to use this on more involved recurrences, you quickly encounter the prime disadvantage of this method: it can be hard to see the pattern, or condense it to a nice closed form.

Asymptotics

It is possible to use this method for asymptotics, too. Be aware, though, that you have to guess the constants for the Landau symbols as there has to be one constant that establishes the bound for all $n$, i.e. the constant factor can not change during the induction.

Consider, for example, the Mergesort runtime recurrence, simplified for the case of $n=2^k$¹:

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= 2T(n/2) + n-1 \qquad n \geq 1 \end{align}$

We guess that $T(n) \in O(n\log n)$ with constant $c=1$, that is $T(n) \leq n\log n$. We prove this by induction over $k$; the inductive step looks like this:

$\qquad \begin{align} T(n) &= 2T(n/2) + n-1 \\ &\leq 2\frac{n}{2}\log \frac{n}{2} + n - 1 \\ &= n\log n - n\log 2 + n - 1 \\ &\lt n \log n \end{align}$

---

1. For non-decreasing sequences of naturals, every infinite subsequence has the same asymptotic growth as the original sequence.

Answer 5

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$ T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for $x \ge x_0$} $$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h_i(x)$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $a_i$ and $b_i$ are all constants
• For all $i$, $a_i > 0$
• For all $i$, $0 < b_i < 1$
• $\lvert g(x) \rvert = O(x^c)$ for some constant $c$ as $x \rightarrow \infty$
• For all $i$, $\lvert h_i(x) \rvert = O(x / (\log x)^2)$
• $x_0$ is a constant

Note that $\lfloor b_i x \rfloor = b_i x - \{b_i x\}$, and as the sawtooth function $\{ u \} = u - \lfloor u \rfloor$ is always between 0 and 1, replacing $\lfloor b_i x \rfloor$ (or $\lceil b_i x \rceil$ as appropiate) satisfies the conditions on the $h_i$.

Find $p$ such that: $$ \sum_{1 \le i \le k} a_i b_i^p = 1 $$ Then the asymptotic behaviour of $T(x)$ as $x \rightarrow \infty$ is given by: $$ T(x) = \Theta \left( x^p \left( 1 + \int_{x_1}^x \frac{g(u)}{u^{p + 1}} du \right) \right) $$ with $x_1$ "large enough", i.e. there is $k_1>0$ so that $$g(x/2) \geq k_1g(x) \tag{2}$$ for all $x>x_1$.

Example A

As an example, take the recursion for $n \ge 5$, where $T(0) = T(1) = T(2) = T(3) = T(4) = 17$: $$ T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n $$ The conditions are satisfied, we need $p$: $$ 9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1 $$ As luck would have it, $p = 2$. Thus we have: $$ T(n) = \Theta \left( n^2 \left(1 + \int_3^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

since with $k_1 \leq \frac{1}{2}\left(1 - \frac{\log 2}{\log 3}\right)$ we fulfill $(2)$ for all $x\geq 3$. Note that because the integral converges even if we use other constants, such as $1$, as lower bound, it is legal to use those as well; the difference vanishes in $\Theta$.

Example B

Another example is the following for $n \ge 2$: $$ T(n) = 4 T(n / 2) + n^2 / \lg n $$ We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a_1 = 4$, $b_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h_i(n)$ also check out. So we need: $$ a_1 b_1^p = 4 \cdot (1 / 2)^p = 1 $$ Thus $p = 2$, and: $$ T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n) $$ We apply a similar trick as above to the lower bound of the integral, only that we use $2$ because the integral does not converge for $1$.

(The help of maxima with the algebra is gratefully acknowledged)

Answer 6

Summations

Often one encounters a recurrence of the form $$ T(n) = T(n-1) + f(n), $$ where $f(n)$ is monotone. In this case, we can expand $$ T(n) = T(c) + \sum_{m=c+1}^n f(m), $$ and so given a starting value $T(c)$, in order to estimate $T(n)$ we need to estimate the sum $f(c+1) + \cdots + f(m)$.

Non-decreasing $f(n)$

When $f(n)$ is monotone non-decreasing, we have the obvious bounds $$ f(n) \leq \sum_{m=c+1}^n f(m) \leq (n-c) f(n). $$ These bounds are best-possible in the sense that they are tight for some functions: the upper bound for constant functions, and the lower bound for step functions ($f(m) = 1$ for $m \geq n$ and $f(m) = 0$ for $m < n$). However, in many cases these estimates are not very helpful. For example, when $f(m) = m$, the lower bound is $n$ and the upper bound is $(n-c)n$, so they are quite far apart.

Integration

A better estimate is given by integration: $$ \int_c^n f(x) dx \leq \sum_{m=c+1}^n f(m) \leq \int_{c+1}^{n+1} f(x) dx. $$ For $f(m) = m$, this gives the correct value of the sum up to lower order terms: $$ \frac{1}{2} n^2 - \frac{1}{2} c^2 \leq \sum_{m=c+1}^n m \leq \frac{1}{2} (n+1)^2 - \frac{1}{2} (c+1)^2. $$ When $f(m) = m$ we can calculate the sum explicitly, but in many cases explicit computation is hard. For example, when $f(m) = m\log m$ the antiderivative of $f$ is $(1/2) x^2\log x - (1/4) x^2$, and so $$ \sum_{m=c+1}^n m\log m = \frac{1}{2} n^2 \log n \pm \Theta(n^2). $$

The Euler–Maclaurin formula gives better estimates. This formula can be used, for example, to prove strong forms of Stirling's formula, by estimating the sum $\log n! = \sum_{m=1}^n \log m$.

Non-increasing $f(n)$

In some cases, $f(n)$ is monotone non-increasing. The trivial estimates become $$ f(1) \leq \sum_{m=c+1}^n f(m) \leq (n-c) f(1), $$ and the integral estimates $$ \int_{c+1}^{n+1} f(x) dx \leq \sum_{m=c+1}^n f(m) \leq \int_c^n f(x) dx. $$ As an example, for $f(m) = 1/m$, using $\int f(m) = \log m$ we obtain $$ \sum_{m=c+1}^n \frac{1}{m} = \log n \pm \Theta(1). $$

Answer 7

Sedgewick and Flajolet have done extensive work in analytic combinatorics, which allows recurrences to be solved asymptotically using a combination of generating functions and complex analysis. Their work allows many recurrences to be solved automatically, and has been implemented in some computer algebra systems.

This textbook on the subject was written by Flajolet and Sedgewick and is an excellent reference. A somewhat simpler exposition, geared towards applications to algorithm analysis, is this text by Sedgewick and Flajolet.

Hope this helps!

Answer 8

There may be times when you come across a strange recurrence like this: $$T(n) = \begin{cases} c & n < 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$$ If you're like me, you'll realize you can't use the Master Theorem and then you may think, "hmmm... maybe a recurrence tree analysis could work." Then you'd realize that the tree starts to get gross really fast. After some searching on the internet you see the Akra-Bazzi method will work! Then you actually start to look into it and realize you don't really want to do all the math. If you've been like me up till this point, you'll be excited to know there's an easier way.

---

The Uneven Split Theorem Part 1

Let $c$ and $k$ be positive constants.

Then let $\{a_1, a_2, \ldots, a_k\}$ be positive constants such that $\sum_1^k a_i < 1$.

We also must have a recurrence of the form (like our example above):

$$\begin{align} T(n) & \leq c & 0 < n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ T(n) & \leq cn + T(a_1 n) + T(a_2 n) + \dots T(a_k n) & n \geq \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \end{align}$$

Claim

Then I claim $T(n) \leq bn$ where $b$ is a constant (e.g. asymptotically linear) and:

$$b = \frac{c}{1 - \left(\sum_1^k a_i\right)}$$

Proof by Induction

Basis: $n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \implies T(n) \leq c < b < bn$

Induction: Assume true for any $n' < n$, we then have

$$\begin{align} T(n) & \leq cn + T(\lfloor a_1 n \rfloor) + T(\lfloor a_2 n \rfloor) + \dots + T(\lfloor a_k n \rfloor)\\ & \leq cn + b \lfloor a_1 n \rfloor + b \lfloor a_2 n \rfloor + \dots + b \lfloor a_k n \rfloor\\ & \leq cn + b a_1 n + b a_2 n + \dots + b a_k n\\ & = cn + bn \sum_1^k a_i\\[0.5em] & = \frac{cn - cn \sum_1^k a_i }{1 - \left(\sum_1^k a_i\right)} + \frac{cn \sum_1^k a_i}{1 - \left(\sum_1^k a_i\right)}\\[0.5em] & = \frac{cn}{1 - \left(\sum_1^k a_i\right)}\\ & = bn & \square \end{align}$$

Then we have $T(n) \leq bn \implies T(n) = O(n)$.

Example

$$T(n) = \begin{cases} c & n < 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$$ We first verify the coefficients inside the recursive calls sum to less than one: $$\begin{align} 1 & > \sum_1^k a_i \\ & = \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7}\\[0.5em] & = \frac{2}{5} + \frac{4}{7}\\[0.5em] & = \frac{34}{35} \end{align}$$

We next verify that the base case is less than the max of the inverses of the coefficients: $$\begin{align} n & < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ & = \max\{5, 5, 7, 7, 7, 7\}\\ & = 7 \end{align}$$

With these conditions met, we know $T(n) \leq bn$ where $b$ is a constant equal to: $$\begin{align} b &= \frac{c}{1 - \left(\sum_1^k a_i\right)}\\[0.5em] &= \frac{c}{1 - \frac{34}{35}}\\[0.5em] &= 35c \end{align}$$ Therefore we have: $$\begin{align} T(n) & \leq 35cn\\ \land\; T(n) & \geq cn\\ \therefore T(n) & = \Theta(n) \end{align}$$

---

The Uneven Split Theorem Part 2

Similarly we can prove a bound for when $\sum_1^k = 1$. The proof will follow much of the same format:

Let $c$ and $k$ be positive constants such that $k > 1$.

Then let $\{a_1, a_2, \ldots, a_k\}$ be positive constants such that $\sum_1^k a_i = 1$.

We also must have a recurrence of the form (like our example above):

$$\begin{align} T(n) & \leq c & 0 < n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ T(n) & \leq cn + T(a_1 n) + T(a_2 n) + \dots T(a_k n) & n \geq \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \end{align}$$

Claim

Then I claim $T(n) \leq \alpha n \log_k n + \beta n$ (we choose $\log$ base $k$ because $k$ will be the branching factor of the recursion tree) where $\alpha$ and $\beta$ are constants (e.g. asymptotically linearithmic) such that:

$$\beta = c$$ and $$\alpha = \frac{c}{\sum_1^k a_i \log_k a_i^{-1}}$$

Proof by Induction

Basis: $n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \implies T(n) \leq c = \beta < \alpha n \log_k n + \beta n$

Induction: Assume true for any $n' < n$, we then have

$$\begin{align} T(n) & \leq cn + T(\lfloor a_1 n \rfloor) + T(\lfloor a_2 n \rfloor) + \dots + T(\lfloor a_k n \rfloor)\\ & \leq cn + \sum_1^k (\alpha a_i n \log_k a_i n + \beta a_i n)\\ & = cn + \alpha n\sum_1^k (a_i \log_k a_i n) + \beta n\sum_1^k a_i\\ & = cn + \alpha n\sum_1^k \left(a_i \log_k \frac{n}{a_i^{-1}}\right) + \beta n\\ & = cn + \alpha n\sum_1^k (a_i (\log_k n - \log_k a_i^{-1})) + \beta n\\ & = cn + \alpha n\sum_1^k a_i \log_k n - \alpha n\sum_1^k a_i \log_k a_i^{-1} + \beta n\\ & = \alpha n\sum_1^k a_i \log_k n + \beta n\\ & = \alpha n \log_k n + \beta n & \square \end{align}$$

Then we have $T(n) \leq \alpha n \log_k n + \beta n \implies T(n) = O(n \log n)$.

Example

Let's modify that previous example we used just a tiny bit: $$T(n) = \begin{cases} c & n < 35\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + T\left(\frac{n}{35}\right)+ cn & n \geq 35 \end{cases}$$

We first verify the coefficients inside the recursive calls sum to one: $$\begin{align} 1 & = \sum_1^k a_i \\ & = \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{35}\\[0.5em] & = \frac{2}{5} + \frac{4}{7} + \frac{1}{35}\\[0.5em] & = \frac{35}{35} \end{align}$$

We next verify that the base case is less than the max of the inverses of the coefficients: $$\begin{align} n & < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ & = \max\{5, 5, 7, 7, 7, 7, 35\}\\ & = 35 \end{align}$$

With these conditions met, we know $T(n)\leq \alpha n \log n + \beta n $ where $\beta = c$ and $\alpha$ is a constant equal to: $$\begin{align} b &= \frac{c}{\sum_1^k a_i \log_k a_i^{-1}}\\[0.5em] &= \frac{c}{\frac{2 \log_7 5}{5} + \frac{4 \log_7 7}{7} + \frac{\log_7 35}{35}}\\[0.5em] &\approx 1.048c \end{align}$$ Therefore we have: $$\begin{align} T(n) & \leq 1.048cn\log_7 n + cn\\ \therefore T(n) & = O(n \log n) \end{align}$$

Answer 9

After checking this post again, I'm surprised this isn't on here yet.

Domain Transformation / Change of Variables

When dealing with recurrences it's sometimes useful to be able to change your domain if it's unclear how deep the recursion stack will go.

For instance, take the following recurrence:

$$T(n) = T(2^{2^{\sqrt{\log \log n}}}) + \log \log \log n$$

How could we ever solve this? We could expand out the series, but I promise this will get gross really fast. Instead, let's consider how our input changes with each call.

We first have:

1. $n$, then
2. $2^{2^{\sqrt{\log \log n}}}$, then
3. $2^{2^{\sqrt{\log \log (2^{2^{\sqrt{\log \log n}}})}}}$, and so on.

The goal of a domain transformation will now be to change our recurrence into an equivalent $S(k)$ such that instead of the above transitions, we simply have $k, k-1, k-2, \ldots$.

For example, if we let $n = 2^{2^{2^{2^k}}}$, then this is what we get for our above recurrence: $$\begin{align*} T(2^{2^{2^{2^k}}}) & = T(2^{2^{\sqrt{\log \log 2^{2^{2^{2^{k}}}}}}}) + \log \log \log (2^{2^{2^{2^{k}}}})\\ & = T(2^{2^{2^{2^{k-1}}}}) + 2^k \end{align*}$$ Then we can simply rewrite it as: $$T(k) = T(k-1) + 2^k = \sum_{i = 1}^{k} 2^k = 2^{k+1} - 1$$ Then all you have to do is convert $k$ back to $n$ to get: $$T(n) = 2^{(\log \log \log \log n) + 1} - 1 = O(\log \log \log n)$$

---

With this example, we can now see our goal.

Assume $$T(n) = \begin{cases} h(1) & n = 1\\ a\cdot T(f(n)) + h(n) & \mathrm{otherwise} \end{cases}$$ For some constant $a$ and functions $f(n)$ and $h(n)$.

We are now trying to find some function $g(k) = n$ and $f(g(k)) = g(k-1)$ such that $$\begin{align*} T(g(k)) &= aT(f(g(k))) + h(g(k))\\ & = a\cdot T(g(k-1)) + h(g(k)) \end{align*}$$

More generally, we want $f^{(i)}(n) = g(k - i)$ where $f^{(i)}(n)$ is the repeated application of $f$ on $n$, $i$ times. (e.g. $f^{(2)}(n) = f(f(n))$). This will allow $g(k)$ to act as the "iterating" function. Where, at depth $i$ of recursion, the work done is simply $h(g(k-i))$.

Then we can easily convert this to $S(k) = T(g(k))$ so that $$S(k) = a\cdot S(k-1) + h(g(k))$$ Then we only have to worry about summing up $h(g(k))$ for all $k$ up to a given base case. That is, $$S(k) = \sum_{i = g^{-1}(1)}^{k} a^{k - i} h(g(i))$$

If we can determine $S(k) = \gamma(k)$ for some closed form $\gamma$ function, then we can determine $T(n)$ as $$T(n) = \gamma( g^{-1}(n))$$

Then we use this to get a bound on $T(n)$ via one of the other methods above. You could obviously modify this method a little bit to your specification, but in general you're trying to find an iterating function $g(k)$ to turn $T(n)$ into a simple recursion.

I don't know of an exact way to determine $g(k)$ at this point, but I will keep thinking about it and update if it becomes clearer (or if any commenter has some tips!). I have mostly found my $g(k)$ functions through trial and error in the past (see here, here, here, and here for examples).

Answer 10

Case 2 of the master theorem, as usually stated, handles only recurrences of the form $T(n) = aT(n/b) + f(n)$ in which $f(n) = \Theta(n^{\log_ab}\log^k n)$ for $k \geq 0$. The following theorem, taken from a handout of Jeffrey Leon, gives the answer for negative $k$:

Consider the recurrence $T(n) = a T(n/b) + f(n)$ with an appropriate base case.

1. If $f(n) = O(n^{\log_b a} \log^{c-1} n)$ for $c < 0$ then $T(n) = \Theta(n^{\log_b a})$.

2. If $f(n) = \Theta(n^{\log_b a} \log^{c-1} n)$ for $c = 0$ then $T(n) = \Theta(n^{\log_b a} \log\log n)$.

3. If $f(n) = \Theta(n^{\log_b a} \log^{c-1} n)$ for $c > 0$ then $T(n) = \Theta(n^{\log_b a} \log^c n$).

The proof uses the method of repeated substitution, as we now sketch. Suppose that $f(n) = n^{\log_b a} \log_b^{c-1} n$ and $T(1) = 0$. Then for $n$ a power of $b$, $$ T(n) = \sum_{i=0}^{\log_b n-1} a^i (nb^{-i})^{\log_b a} \log_b^{c-1} (nb^{-i}) = \\ \sum_{i=0}^{\log_b n-1} n^{\log_b a} (\log_b n - i)^{c-1} = n^{\log_b a} \sum_{j=1}^{\log_b n} j^{c-1}. $$ Now let us consider the cases one by one. When $c < 0$, the series $\sum_{j=0}^\infty j^{c-1}$ converges, and so $T(n) = \Theta(n^{\log_b a})$. When $c = 0$, the sum is the harmonic sum $H_{\log_b n} = \log(\log_b n) + O(1)$, and so $T(n) = \Theta(n^{\log_b a} \log \log n)$. When $c > 0$, we can approximate the sum using an integral: $$ \sum_{j=1}^{\log_b n} \approx \int_0^{\log_b n} x^{c-1} \, dx = \left. \frac{x^c}{c} \right|_0^{\log_b n} = \frac{\log_b^c n}{c}, $$ and so $T(n) = \Theta(n^{\log_b a} \log^c n)$.

Answer 11

There's one more approach that works for simple recurrence relations: ask Wolfram Alpha to solve the recurrence for you.

For instance, try typing f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) into Wolfram Alpha. You'll get a solution, with a link to the Fibonacci numbers. Or try f(1)=1, f(n)=f(n-1)+n or f(1)=1, f(n)=2*f(n-1)+3*n or f(n)=f(n-1) + 2 f(n-2), f(1)=1, f(2)=3 for other examples. However, be warned: Wolfram Alpha can solve some very simple recurrences, but it falls apart for more complex ones.

This approach avoids the need for any thinking, which can be viewed as either a bug or a feature.