# Section8.4Some Common Recurrence Relations¶ permalink

In this section we intend to examine a variety of recurrence relations that are not finite-order linear with constant coefficients. For each part of this section, we will consider a concrete example, present a solution, and, if possible, examine a more general form of the original relation.

# Subsection8.4.1A First Basic Example¶ permalink

Consider the homogeneous first-order linear relation without constant coefficients, $S(n) - n S(n - 1) = 0$, $n \geq 1$, with initial condition $S(0) = 1$. Upon close examination of this relation, we see that the $n$th term is $n$ times the $(n - 1)^{st}$ term, which is a property of $n$ factorial. $S(n) = n!$ is a solution of this relation, for if $n \geq 1$, $S(n) = n! = n \cdot (n -1)! = n\cdot S(n - 1)$ In addition, since $0! = 1$, the initial condition is satisfied. It should be pointed out that from a computational point of view, our “solution” really isn't much of an improvement since the exact calculation of $n!$ takes $n-1$ multiplications.

If we examine a similar relation, $G(k) - 2 ^k G(k - 1),$ $k\geq 1$ with $G(0) = 1$, a table of values for $G$ suggests a possible solution: $\begin{array}{ccccccc} k & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline G(k) & 1 & 2 & 2^3 & 2^6 & 2^{10} & 2^{15} \\ \end{array}$ The exponent of 2 in $G(k)$ is growing according to the relation $E(k) = E(k - 1) + k,$ with $E(0) = 0$. Thus $E(k)=\frac{k(k+1)}{2}$ and $G(k) = 2^{k(k+1)/2}$. Note that $G(k)$ could also be written as $2^0 2^1 2^2 \cdots 2^k$, for $k \geq 0$, but this is not a closed form expression.

In general, the relation $P(n) = f(n)P(n - 1)$ for $n \geq 1$ with $P(0) =f(0)$, where $f$ is a function that is defined for all $n\geq 0$, has the “solution” $P(n)=\prod _{k=0}^n f(k)$ This product form of $P(n)$ is not a closed form expression because as $n$ grows, the number of multiplications grow. Thus, it is really not a true solution. Often, as for $G(k)$ above, a closed form expression can be derived from the product form.

# Subsection8.4.3Analysis of Bubble Sort and Merge Sort¶ permalink

The efficiency of any search algorithm such as the binary search relies on fact that the search list is sorted according to a key value and that the search is based on the key value. There are several methods for sorting a list. One example is the bubble sort. You might be familiar with this one since it is a popular “first sorting algorithm.” A time analysis of the algorithm shows that if $B(n)$ is the worst-case time needed to complete the bubble sort on $n$ items, then $B(n) =(n-1) + B(n-1)$ and $B(1) = 0$. The solution of this relation is a quadratic function $B(n) =\frac{1}{2}\left(n^2-n\right)$. The growth rate of a quadratic function such as this one is controlled by its squared term. Any other terms are dwarfed by it as $n$ gets large. For the bubble sort, this means that if we double the size of the list that we are to sort, $n$ changes to $2n$ and so $n^2$ becomes $4n^2$ . Therefore, the time needed to do a bubble sort is quadrupled. One alternative to bubble sort is the merge sort. Here is a simple version of this algorithm for sorting $F=\{r(1), r(2), \ldots , r(n)\}$, $n \geq 1$. If $n = 1$, the list is sorted trivially. If $n\geq 2$ then:

1. Divide $F$ into $F_1= \{r(1), \ldots , r(\lfloor n/2\rfloor )\}$ and $F_2= \{r(\lfloor n/2\rfloor +1), \ldots ,r(n)\}$.

2. Sort $F_1$ and $F_2$ using a merge sort.

3. Merge the sorted lists $F_1$ and $F_2$ into one sorted list. If the sort is to be done in descending order of key values, you continue to choose the higher key value from the fronts of $F_1$ and $F_2$ and place them in the back of $F$.

Note that $F_1$ will always have $\lfloor n/2\rfloor$ items and $F_2$ will have $\lceil n/2\rceil$ items; thus, if $n$ is odd, $F_2$ gets one more item than $F_1$. We will assume that the time required to perform Step 1 of the algorithm is insignificant compared to the other steps; therefore, we will assign a time value of zero to this step. Step 3 requires roughly $n$ comparisons and $n$ movements of items from $F_1$ and $F_2$ to $F$; thus, its time is proportional to $n$. For this reason, we will assume that Step 3 takes $n$ time units. Since Step 2 requires $T(\lfloor n/2\rfloor ) + T(\lceil n/2\rceil )$ time units, \begin{gather} T(n) = n + T(\lfloor n/2\rfloor ) + T(\lceil n/2\rceil )\label{eq-bubble-r}\tag{8.4.9} \end{gather} with the initial condition \begin{gather} T(1) = 0\label{eq-bubble-b}\tag{8.4.10} \end{gather}

Instead of an exact solution of these equations, we will be content with an estimate for $T(n)$. First, consider the case of $n=2^r$, $r \geq 1$: \begin{equation*} \begin{array}{c} T\left(2^1\right)= T(2) = 2 +T(1)+T(1)= 2 = 1\cdot 2\\ T\left(2^2\right) = T(4)=4+\text{ }T(2)+T(2)=8 = 2\cdot 4\\ T\left(2^3\right) =T(8)=8 + T(4)+T(4) =24=3\cdot 8\\ \vdots \\ T\left(2^r\right)=r 2^r= 2^r \log_2 2^r \end{array} \end{equation*}

Thus, if $n$ is a power of 2, $T(n) = n \log_2 n$. Now if, for some $r \geq 2$, $2^{r-1}\leq n\leq 2^r$, then $(r-1)2^{r-1}\leq T(n) < r 2^r$. This can be proved by induction on $r$. As $n$ increases from $2^{r-1}$ to $2^r$, $T(n)$ increases from $(r-1)2^{r-1}$to $r 2^r$ and is slightly larger than $\left\lfloor n \log_2n\right\rfloor$. The discrepancy is small enough so that $T_e(n)=\left\lfloor n \log _2n\right\rfloor$ can be considered a solution of (8.4.9) and (8.4.10) for the purposes of comparing the merge sort with other algorithms. Table 8.4.7 compares $B(n)$ with $T_e(n)$ for selected values of $n$.

A derangement is a permutation on a set that has no “fixed points”. Here is a formal definition:

##### Definition8.4.8Derangement

A derangement of a nonempty set $A$ is a permutation of $A$ (i.e., a bijection from $A$ into $A$) such that $f(a)\neq a$ for all $a \in A$.

If $A = \{1, 2, . . . , n\}$, an interesting question might be “How many derangements are there of $A$?” We know that our answer is bounded above by $n!$. We can also expect our answer to be quite a bit smaller than $n!$ since $n$ is the image of itself for $(n-1)!$ of the permutations of $A$.

Let $D(n)$ be the number of derangements of $\{1, 2, . . . , n\}$. Our answer will come from discovering a recurrence relation on $D$. Suppose that $n \geq 3$. If we are to construct a derangement of $\{1, 2, \dots , n\}$, $f$, then $f(n) = k \neq n$. Thus, the image of $n$ can be selected in $n-1$ different ways. No matter which of the $n -1$ choices we make, we can complete the definition of $f$ in one of two ways. First, we can decide to make $f(k) = n$, leaving $D(n -2)$ ways of completing the definition of $f$, since $f$ will be a derangement of $\{1, 2, \dots ,n\} - \{n, k\}$. Second, if we decide to select $f(k)\neq n$, each of the $D(n - 1)$ derangements of $\{1, 2,\dots ,n-1\}$ can be used to define $f$. If $g$ is a derangement of $\{1, 2, \dots , n-1\}$ such that $g(p) = k$, then define f by $f(j)=\left\{ \begin{array}{cc} n & \textrm{ if } j = p \\ k & \textrm{ if } j = n \\ g(j) & \textrm{ otherwise } \\ \end{array} \right.$

Note that with our second construction of $f$, $f(f(n)) = f(k) \neq n$, while in the first construction, $f(f(n)) = f(k) = n$. Therefore, no derangement of $\{1, 2, . . . , n\}$ with $f(n) = k$ can be constructed by both methods.

To recap our result, we see that $f$ is determined by first choosing one of $n - 1$ images of $n$ and then constructing the remainder of $f$ in one of $D(n - 2) + D(n -1)$ ways. Therefore, \begin{gather} D(n) = (n - 1) (D(n - 2) + D(n - 1))\label{mrow-12}\tag{8.4.11} \end{gather}

This homogeneous second-order linear relation with variable coefficients, together with the initial conditions $D(1) = 0$ and $D(2) = 1$, completely defines $D$. Instead of deriving a solution of this relation by analytical methods, we will give an empirical derivation of an approximation of $D(n)$. Since the derangements of $\{1,2 . . . , n\}$ are drawn from a pool of $n!$ permutations, we will see what percentage of these permutations are derangements by listing the values of $n!$, $D(n)$, and $\frac{D(n)}{n!}$. The results we observe will indicate that as $n$ grows, $\frac{D(n)}{n!}$ hardly changes at all. If this quotient is computed to eight decimal places, for $n \geq 12$, $D(n)/n! = 0.36787944$. The reciprocal of this number, which $D(n)/n!$ seems to be tending toward, is, to eight places, 2.71828182. This number appears in so many places in mathematics that it has its own name, $e$. An approximate solution of our recurrence relation on $D$ is then $D(n)\approx \frac{n!}{e}$.

\begin{equation*}\begin{array}{lll} n & D(n) & D(n)/n! \\ 1 & 0 & 0 \\ 2 & 1 & 0.50000000 \\ 3 & 2 & 0.33333333 \\ 4 & 9 & 0.37500000 \\ 5 & 44 & 0.36666667 \\ 6 & 265 & 0.36805556 \\ 7 & 1854 & 0.36785714 \\ 8 & 14833 & 0.36788194 \\ 9 & 133496 & 0.36787919 \\ 10 & 1334961 & 0.36787946 \\ 11 & 14684570 & 0.36787944 \\ 12 & 176214841 & 0.36787944 \\ 13 & 2290792932 & 0.36787944 \\ 14 & 32071101049 & 0.36787944 \\ 15 & 481066515734 & 0.36787944 \\ \end{array} \end{equation*}

# Subsection8.4.5Exercises for Section 8.4¶ permalink

##### 1

Solve the following recurrence relations. Indicate whether your solution is an improvement over iteration.

1. $n S(n) - S(n - 1) = 0$, $S(0) = 1$.

2. $T(k) + 3k T(k - 1) = 0$, $T(0) = 1$.

3. $U(k) -\frac{k-1}{k}U(k - 1) = 0$, $k \geq 2$, $U(1) = 1$.

##### 2

Prove that if $n \geq 0$, $\lfloor n/2\rfloor +\lceil n/2\rceil = n$. (Hint: Consider the cases of $n$ odd and $n$ even separately.)

##### 3

Solve as completely as possible:

1. $T(n) = 3 + T(\lfloor n/2\rfloor )$, $T(0) = 0$.

2. $T(n) = 1 + \frac{1}{2}T(\lfloor n/2\rfloor )$, $T(0) = 2$.

3. $V(n) = 1 + V\lfloor n/8\rfloor )$, $V(0) = 0$. (Hint: Write $n$ in octal form.)

##### 4

Prove by induction that if $T(n)= 1 + T (\lfloor n/2 \rfloor )$, $T(0) = 0$, and $2^{r-1}\leq n < 2^r$ , $r \geq 1$, then $T(n) = r$.

Hint
##### 5

Use the substitution $S(n) = T(n + 1)/T(n)$ to solve $T(n)T(n-2)-T(n)^2=1$ for $n \geq 2$, with $T(0) = 1$, $T(1) = 6$, and $T(n) \geq 0$.

##### 6

Use the substitution $G(n) =T(n)^2$ to solve $T(n)^2-T(n-1)^2=1$ for $n \geq 1$, with $T(0) = 10$.

##### 7

Solve as completely as possible:

1. $Q(n)=1+Q\left(\left\lfloor \sqrt{n}\right\rfloor \right)$, $n \geq 2$, $Q(1) = 0$.

2. $R(n)=n +R(\lfloor n/2\rfloor )$, $n \geq 1$, $R(0) = 0$.

Suppose Step 1 of the merge sort algorithm did take a significant amount of time. Assume it takes 0.1 time unit, independent of the value of $n$.
1. Write out a new recurrence relation for $T(n)$ that takes this factor into account.
2. Solve for $T\left(2^r\right)$, $r \geq 0$.
3. Assuming the solution for powers of 2 is a good estimate for all $n$, compare your result to the solution in the text. As gets large, is there really much difference?