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

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 2

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 3

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 4

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(n) \in O\left( n^{\log_b (a) - \varepsilon} \right)$,

   for some $\varepsilon > 0$.

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

3. $\quad \displaystyle f(n) = \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(n) \in \Theta\left( n^{\log_b a} \right)$,
2. $T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n \right)$ and
3. $T\left(n \right) = \Theta \left(f \left(n \right) \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(n) \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(n) \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(n) \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 5

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 6

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)