## Section8.4Some Common Recurrence Relations

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

Consider the homogeneous first-order linear relation without constant coefficients, $$S(n) - n S(n - 1) = 0\text{,}$$ $$n \geq 1\text{,}$$ with initial condition $$S(0) = 1\text{.}$$ 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\text{,}$$

\begin{equation*} S(n) = n! = n \cdot (n -1)! = n\cdot S(n - 1) \end{equation*}

In addition, since $$0! = 1\text{,}$$ 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\text{,}$$ a table of values for $$G$$ suggests a possible solution:

\begin{equation*} \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} \end{equation*}

The exponent of 2 in $$G(k)$$ is growing according to the relation $$E(k) = E(k - 1) + k,$$ with $$E(0) = 0\text{.}$$ Thus $$E(k)=\frac{k(k+1)}{2}$$ and $$G(k) = 2^{k(k+1)/2}\text{.}$$ Note that $$G(k)$$ could also be written as $$2^0 2^1 2^2 \cdots 2^k\text{,}$$ for $$k \geq 0\text{,}$$ 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)\text{,}$$ where $$f$$ is a function that is defined for all $$n\geq 0\text{,}$$ has the “solution”

\begin{equation*} P(n)=\prod _{k=0}^n f(k) \end{equation*}

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

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\text{.}$$ The solution of this relation is a quadratic function $$B(n) =\frac{1}{2}\left(n^2-n\right)\text{.}$$ 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)\}\text{,}$$ $$n \geq 1\text{.}$$ If $$n = 1\text{,}$$ 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)\}\text{.}$$

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\text{.}$$

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\text{.}$$ 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\text{;}$$ thus, its time is proportional to $$n\text{.}$$ 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 )\tag{8.4.9} \end{gather}

with the initial condition

\begin{gather} T(1) = 0\tag{8.4.10} \end{gather}

Instead of an exact solution of these equations, we will be content with an estimate for $$T(n)\text{.}$$ First, consider the case of $$n=2^r\text{,}$$ $$r \geq 1\text{:}$$

\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\text{.}$$ Now if, for some $$r \geq 2\text{,}$$ $$2^{r-1}\leq n\leq 2^r\text{,}$$ then $$(r-1)2^{r-1}\leq T(n) < r 2^r\text{.}$$ This can be proved by induction on $$r\text{.}$$ As $$n$$ increases from $$2^{r-1}$$ to $$2^r\text{,}$$ $$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\text{.}$$ 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\text{.}$$

### Subsection8.4.4Derangements

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

#### Definition8.4.8.Derangement.

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\text{.}$$

If $$A = \{1, 2, . . . , n\}\text{,}$$ an interesting question might be “How many derangements are there of $$A\text{?}$$” We know that our answer is bounded above by $$n!\text{.}$$ 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\text{.}$$

Let $$D(n)$$ be the number of derangements of $$\{1, 2, . . . , n\}\text{.}$$ Our answer will come from discovering a recurrence relation on $$D\text{.}$$ Suppose that $$n \geq 3\text{.}$$ If we are to construct a derangement of $$\{1, 2, \dots , n\}\text{,}$$ $$f\text{,}$$ then $$f(n) = k \neq n\text{.}$$ 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\text{,}$$ leaving $$D(n -2)$$ ways of completing the definition of $$f\text{,}$$ since $$f$$ will be a derangement of $$\{1, 2, \dots ,n\} - \{n, k\}\text{.}$$ Second, if we decide to select $$f(k)\neq n\text{,}$$ each of the $$D(n - 1)$$ derangements of $$\{1, 2,\dots ,n-1\}$$ can be used to define $$f\text{.}$$ If $$g$$ is a derangement of $$\{1, 2, \dots , n-1\}$$ such that $$g(p) = k\text{,}$$ then define f by

\begin{equation*} f(j)=\left\{ \begin{array}{cc} n & \textrm{ if } j = p \\ k & \textrm{ if } j = n \\ g(j) & \textrm{ otherwise } \\ \end{array} \right. \end{equation*}

Note that with our second construction of $$f\text{,}$$ $$f(f(n)) = f(k) \neq n\text{,}$$ while in the first construction, $$f(f(n)) = f(k) = n\text{.}$$ 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))\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\text{,}$$ completely defines $$D\text{.}$$ Instead of deriving a solution of this relation by analytical methods, we will give an empirical derivation of an approximation of $$D(n)\text{.}$$ 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!\text{,}$$ $$D(n)\text{,}$$ and $$\frac{D(n)}{n!}\text{.}$$ 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\text{,}$$ $$D(n)/n! = 0.36787944\text{.}$$ The reciprocal of this number, which $$D(n)/n!$$ seems to be tending toward, is, to eight places, 2.7182818. This number appears in so many places in mathematics that it has its own name, $$e\text{.}$$ An approximate solution of our recurrence relation on $$D$$ is then $$D(n)\approx \frac{n!}{e}\text{.}$$

def D(n):
if n<=2:
return n-1
else:
return (n-1)*(D(n-2)+D(n-1))

list(map(lambda k:[k,D(k),(D(k)/factorial(k)).n(digits=8)],range(1,16)))


### Exercises8.4.5Exercises

#### 1.

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

1. $$n S(n) - S(n - 1) = 0\text{,}$$ $$S(0) = 1\text{.}$$

2. $$T(k) + 3k T(k - 1) = 0\text{,}$$ $$T(0) = 1\text{.}$$

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

1. $$S(n)=1/n\text{!}$$

2. $$U(k)=1/k\text{,}$$ an improvement.

3. $$T(k)=(-3)^kk\text{!,}$$ no improvement.

#### 2.

Prove that if $$n \geq 0\text{,}$$ $$\lfloor n/2\rfloor +\lceil n/2\rceil = n\text{.}$$ (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 )\text{,}$$ $$T(0) = 0\text{.}$$

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

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

1. $$\displaystyle T(n)=3\left(\left\lfloor \log_2n\right\rfloor +1\right)$$

2. $$\displaystyle T(n)=2$$

3. $$\displaystyle V(n)=\left\lfloor \log_8n\right\rfloor +1$$

#### 4.

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

Hint.

Prove by induction on $$r\text{.}$$

#### 5.

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

The indicated substitution yields $$S(n)=S(n+1)\text{.}$$ Since $$S(0)=T(1)/T(0)=6\text{,}$$ $$S(n)=6$$ for all $$n\text{.}$$ Therefore $$T(n+1)=6T(n)\Rightarrow T(n)=6^n\text{.}$$

#### 6.

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

#### 7.

Solve as completely as possible:

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

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

1. A good approximation to the solution of this recurrence relation is based on the following observation: $$n$$ is a power of a power of two; that is, $$n$$ is $$2^m\text{,}$$ where $$m=2^k$$ , then $$Q(n)=1+Q\left(2^{m/2}\right)\text{.}$$ By applying this recurrence relation $$k$$ times we obtain $$Q(n)=k\text{.}$$ Going back to the original form of $$n\text{,}$$ $$\log _2n=2^k$$ or $$\log _2\left(\log _2n\right)=k\text{.}$$ We would expect that in general, $$Q(n)$$ is $$\left\lfloor \log _2\left(\log _2n\right)\right\rfloor\text{.}$$ We do not see any elementary method for arriving at an exact solution.
2. Suppose that $$n$$ is a positive integer with $$2^{k-1} \leq n < 2^k\text{.}$$ Then $$n$$ can be written in binary form, $$\left(a_{k-1}a_{k-2}\cdots a_2a_1a_0\right)_{\textrm{two}}$$ with $$a_{k-1}=1$$ and $$R(n)$$ is equal to the sum $$\underset{i=0}{\overset{k-1}{\Sigma }}$$ $$\left(a_{k-1}a_{k-2}\cdots a_i\right)_{\textrm{two}}\text{.}$$ If $$2^{k-1}\leq n < 2^k\text{,}$$ then we can estimate this sum to be between $$2n-1$$ and $$2n+1\text{.}$$ Therefore, $$R(n)\approx 2n\text{.}$$
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\text{.}$$
1. Write out a new recurrence relation for $$T(n)$$ that takes this factor into account.
2. Solve for $$T\left(2^r\right)\text{,}$$ $$r \geq 0\text{.}$$
3. Assuming the solution for powers of 2 is a good estimate for all $$n\text{,}$$ compare your result to the solution in the text. As gets large, is there really much difference?