Skip to main content

Section 16.2 Some 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.

Subsection 16.2.1 A 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.

Subsection 16.2.3 Analysis 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 )\label{eq-bubble-r}\tag{16.2.9} \end{gather}

with the initial condition

\begin{gather} T(1) = 0\label{eq-bubble-b}\tag{16.2.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 (16.2.9) and (16.2.10) for the purposes of comparing the merge sort with other algorithms. Table 16.2.7 compares \(B(n)\) with \(T_e(n)\) for selected values of \(n\text{.}\)

n \(B(n)\) \(T_e(n)\)
10 45 34
50 1225 283
100 4950 665
500 124750 4483
1000 499500 9966
Table 16.2.7. Comparison of Times for Bubble Sort and Merge Sort

Subsection 16.2.4 Derangements

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

Definition 16.2.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{16.2.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{.}\)

Exercises 16.2.5 Exercises for Section 10.2

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

Answer
  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.)

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

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

  3. \(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)^2=1\) for \(n \geq 2\text{,}\) with \(T(0) = 1\text{,}\) \(T(1) = 6\text{,}\) and \(T(n) \geq 0\text{.}\)

Answer

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

Answer
  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{.}\)

8.

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?