2.   Recurrence Relations


This chapter concentrates on fundamental mathematical properties of various types of recurrence relations which arise frequently when analyzing an algorithm through a direct mapping from a recursive representation of a program to a recursive representation of a function describing its properties.


2.1 Basic Properties.

Recurrences are classified by the way in which terms are combined, the nature of the coefficients involved, and the number and nature of previous terms used.

    recurrence typetypical example
    first-order
        linear$a_n=na_{n-1}-1$
        nonlinear$a_n=1/(1+a_{n-1})$
    second-order
        linear$a_n=a_{n-1}+2a_{n-2}$
        nonlinear$a_n=a_{n-1}a_{n-2}+\sqrt{a_{n-2}}$
        variable coefficients    $a_n=na_{n-1}+(n-1)a_{n-2}+1$
    $t$th order$a_n=f(a_{n-1},a_{n-2},\ldots,a_{n-t})$
    full-history$a_n=n+a_{n-1}+a_{n-2}\ldots + a_1$
    divide-and-conquer$a_n=a_{\lfloor{n/2}\rfloor}+a_{\lceil{n/2}\rceil}+n$

Calculating values. Normally, a recurrence provides an efficient way to calculate the quantity in question. In particular, the very first step in attacking any recurrence is to use it to compute small values in order to get a feeling for how they are growing. This can be done by hand for small values, or it is often easy to implement a program to compute larger values, as we already saw in Chapter 1. You can find the Java code referred to in the lecture slides here.

2.2 First-Order Recurrences.

We can often solve a recurrence relation in a manner analogous to solving a differential equations by multiplying by an integrating factor and then integrating. Instead, we use a summation factor to telescope the recurrence to a sum. Proper choice of a summation factor makes it possible to solve many of the recurrences that arise in practice. $$\eqalign{ NC_N &= (N+1)C_{N-1} + 2N {\quad\rm for\quad} N > 1 {\quad\rm with\quad} C_1 = 2\\ {C_N\over N+1} &= {C_{N-1}\over N} + {2\over N+1} \quad({\rm summation\ factor \ }{1\over N(N+1)})\\ &= {C_{N-2}\over N-1} + {2\over N} + {2\over N+1}\\ &= 2H_{N+1} - 2\\ }$$

Any first-order linear recurrence, with constant or nonconstant coefficients, can be transformed to a sum in this way. The problem of solving the recurrence is reduced to the problem of evaluating the sum.

2.3 Nonlinear First-Order Recurrences.

2.4 Higher-Order Recurrences

2.5 Methods for Solving Recurrences

2.6 Binary Divide-and-Conquer Recurrences and Binary Numbers.

Good algorithms for a broad variety of problems have been developed by applying the following fundamental algorithmic design paradigm: "Divide the problem into two subproblems of equal size, solve them recursively, then use the solutions to solve the original problem." Mergesort is a prototype of such algorithms. The number of comparisons used by Mergesort is given by the solution to the recurrence $$C_N=C_{\lfloor N/2\rfloor} +C_{\lceil N/2\rceil}+N \quad{\rm for}\ N>1{\rm \ with\ } C_1=0.$$ This recurrence, and others similar to it, arise in the analysis of a variety of algorithms with the same basic structure as Mergesort. It is normally possible to determine the asymptotic growth of functions satisfying such recurrences, but it is necessary to take special care in deriving exact results, primarily because of the simple reason that a problem of "size" $N$ cannot be divided into equal-sized subproblems if $N$ is odd: the best that can be done is to make the problem sizes differ by one. For large $N$, this is negligible, but for small $N$ it is noticeable, and, as usual, the recursive structure insures that many small subproblems will be involved. The end result is that exact solutions tend to have periodicities, sometimes even severe discontinuities, and often cannot be described in terms of smooth functions. For Mergesort, the number of compares is $$C_N = N\lfloor\lg N\rfloor+2N-2^{\lfloor\lg N\rfloor+1}$$ which can be written as $$ C_N = N\lg N + N\theta({1-\{\lg N\}}),$$ where $\theta(x)=1+x-2^x$ is a positive function satisfying $\theta(0)=\theta(1)=0$ and $0<\theta(x)<.086$ for $0 < x < 1$. The periodic function $\theta({1-\{\lg N\}})$ is plotted here.

The top curve is $1-\{\lg N\}$ and the middle curve is $1-2^{1-\{\lg N\}}$. Adding these together gives $$2-\{\lg N\}-2^{1-\{\lg N\}} = \theta({1-\{\lg N\}}),$$ a continuous but periodic function. Such situations arise frequently in the analysis of algorithms, and this result indicates the challenge of precisely characterizing the performance of some algorithms because periodic behavior of this sort is inherent.

2.7 General Divide-and-Conquer Recurrences.

More generally, efficient algorithms and upper bounds in complexity studies are very often derived by extending the divide-and-conquer algorithmic design paradigm along the following lines: "Divide the problem into smaller (perhaps overlapping) subproblems, solve them recursively, then use the solutions to solve the original problem." A variety of "divide-and-conquer" recurrences arise that depend on the number and relative size of subproblems, the extent to which they overlap, and the cost of recombining them for the solution. It is normally possible to determine the asymptotic growth of functions satisfying such recurrences, but, as above, the periodic and fractal nature of functions that are involved make it necessary to specify details carefully.


Selected Exercises

2.11

Solve the recurrence $$na_n = (n-2)a_{n-1} + 2\quad{\rm for}\ n>1{\rm \ with\ } a_1=1.$$ Solution. Use the summation factor $n-1$: $$\eqalign{ n(n-1)a_n &= (n-1)(n-2)a_{n-1} + 2(n-1)\\ &= (n-2)(n-3)a_{n-2} + 2(n-2) + 2(n-1)\\ &= 2(1 + 2 + \ldots + n-1)\\ &= n(n-1)\\ a_n &= 1\quad{\rm for}\ n\ge 1\\ }$$

Easier solution. Compute $a_2=1$, think for a moment, and then prove by induction that $a_n=1$ for all $n\ge 1$.


2.12

Solve the recurrence $$a_n = 2a_{n-1} + 1\quad{\rm for}\ n>1{\rm \ with\ } a_1=1.$$ Hint. Divide both sides by $2^n$.


2.13

Solve the recurrence $$a_n = {n\over n+1}a_{n-1} + 1\quad{\rm for}\ n>0{\rm \ with\ } a_0=1.$$


2.15

Solve the recurrence $$na_n = (n+1)a_{n-1} + 2n\quad{\rm for}\ n>0{\rm \ with\ } a_0=0.$$


2.17

[Yao] ("Fringe analysis of 2-3 trees") Solve the recurrence $$A_N = A_{N-1}-{2A_{N-1}\over N} + 2\Bigl(1-{2A_{N-1}\over N}\Bigr) \quad{\rm for}\ N>1{\rm \ with\ } A_1=1.$$ This recurrence describes the following random process: A set of $N$ elements collect into "2-nodes" and "3-nodes." At each step each 2-node is likely to turn into a 3-node with probability $2/N$ and each 3-node is likely to turn into two 2-nodes with probability $3/N$. What is the average number of 2-nodes after $N$ steps?


2.69

Plot the periodic part of the solution to the recurrence $$a_N = 3a_{\lfloor N/3\rfloor} + N \quad{\rm for}\ N>3{\rm \ with\ } a_1=a_2=a_3=1.$$ for $1\le N\le 972$.


2.71

Give an asymptotic solution to the recurrence $$a(x) = \alpha a_{x/\beta} + 2^x \quad{\rm for}\ x>1{\rm \ with\ } a(x)=0{\rm \ for\ } x\le 1.$$


2.73

Give an asymptotic solution to the recurrence $$a_N = a_{N/2} + a_{N/4} + N \quad{\rm for}\ N>2{\rm \ with\ } a_1=a_2=a_3=1.$$


Review Questions

Q2.1

Solve the recurrence $na_n = (n-3)a_{n-1} + n\quad{\rm for}\ n\ge 3{\rm \ with\ } a_0=a_1=a_2=0.$


Q2.2

Which of the following is true of the number of compares used by Mergesort to sort $N$ items? (a) Order of growth is $N lg N$ (b) Exactly $N lg N$ when $N$ is a power of 2 (c) Is equal to the number of 1s in the binary representation of the numbers < $N$ (d) Has periodic behavior (e) Is less than $N lg N + N/4$ for all $N$


Q2.3

Consider the following recurrences:


   A. $(n+1)a_{n+1} = (n-2)a_n + n $


   B. $a_{n+1} = 4a_{n-1} + (n+1)(n+2) $


   C. $na_n = 4a_{n-1} + (n+1)(n+2) $


   D. $na_{n+1} = (n+4)a_{n-1} + n+4 $


   E. $(n+1)a_{n+1} = (n+2)a_n + n $


Match each recurrence with an expression from this list that could be used to make it telescope: $(n+1)(n+2)(n+3) $, $n(n+2)(n+4) $, $2^{n+1} $, $(n+1)! $, $(n-1)!/4^n $, $n(n-1) $, $(n+1)(n+2) $.


Q2.4

(R. Brott) Consider the family of recurrences $a_n = ba_{n-1} - a_{n-2}$ for $n>1$ with $a_0=0$ and $a_1=1$. For which integer values of $b$ does this sequence oscillate?