Chapter 2: Recurrence Relations

Exercise 2.1

def fib_recursive(n):
    return fib_recursive(n - 1) + fib_recursive(n - 2) if n > 1 else n

def fib_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

The recursive version needlessly recomputes the same values and has an exponential running time. The iterative version eliminates this deficiency. The computation remains efficient for $F_{20}=6765$, even with the recursive implementation; however, as values exceed 30, performance differences become increasingly apparent.

Solve the Fibonacci Number problem on LeetCode.

Exercise 2.2

The total number of arithmetic operations (additions, subtractions and divisions), including loop increments and index calculations, is

$$C_{N_{max}}=\sum_{N=1}^{N_{max}}\left(1+1+\sum_{k=0}^{N-1}(1+5)\right)=N_{max}(3N_{max}+5).$$

Exercise 2.3

It uses only $5(N_{max}-1)$ arithmetic operations to compute the same value as Program 2.1.

Exercise 2.4

A non-recursive program would require $\Theta(N)$ time to compute values using recurrence (2) and $\Theta(N^2)$ for recurrence (3), as shown in Exercise 2.2.

A recursive program would also require $\Theta(N)$ time to compute values using recurrence (2). Despite an exponentially growing number of subproblems, their sizes are also exponentially dropping. On the other hand, recursively calculating values via recurrence (3), as mentioned in the book, has unacceptable performance. By instrumenting the code, we get that the number of function calls is $3^N$. This can be formally proven by induction on $N$, using the recurrence $r_N=1+2\sum_{k=0}^{N-1}r_k$ (with $r_0=1$) as the inductive hypothesis. Therefore, the number of arithmetic operations is $\Theta(3^N)$.

Classifying variants with tight asymptotic bounds is convenient here. For example, we don’t need more details to understand that $\Theta(3^N)$ is prohibitive.

Exercise 2.5

We can’t directly implement the recurrence for the radix exchange sort using the technique demonstrated in Program 2.1. To calculate $C_N$ we need to know $C_N$. Let’s transform it

$$\begin{align*} C_N &= N+\frac{1}{2^N} \sum_{k=0}^N {\binom{N}{k}(C_k+C_{N-k})} \\ &= N+\frac{2}{2^N} \sum_{k=0}^N {\binom{N}{k}C_k} && \text{$\left(\binom{N}{k}=\binom{N}{N-k}\right)$} \\ &= N+\frac{1}{2^{N-1}} \left(\left(\sum_{k=0}^{N-1} {\binom{N}{k}C_k}\right)+C_N\right) \\ &= N+\frac{1}{2^{N-1}} \left(\sum_{k=0}^{N-1} {\binom{N}{k}C_k}\right)+\frac{1}{2^{N-1}}C_N \\ &= \frac{2^{N-1}}{2^{N-1}-1} \left(N+\frac{1}{2^{N-1}} \sum_{k=0}^{N-1} {\binom{N}{k}C_k}\right). \end{align*}$$

For efficiently calculating the binomial coefficients, the program employs memoization. Here’s the output:

Analysis of Table 2.5

We’d expect that the average number of compares approach the following asymptotic approximations for sufficiently large $N$:

• Standard quicksort (full-key comparisons): $\sim 2N\ln N \approx1.386N\lg N$

• Median-of-three quicksort (full-key comparisons): $\sim (12/7)N\ln N \approx 1.188 N\lg N$

• Radix exchange sort (bit-inspections): $\sim N\lg N$

Nonetheless, for smaller values of $N$ we can’t ignore lower-order terms, as the data in Table 2.5 shows. This exercise serves as a perfect example of why relying only on the leading asymptotic term can lead to the wrong conclusion for practical input sizes. The book highlights this fact many times. Gradual asymptotic expansion allows fine-tuning the model to reflect the desired accuracy in relation to input size ranges.

Exercise 2.6

Denote by $U_n$ and $V_n$ solutions to homogeneous recurrences $u_n$ and $v_n$, respectively, where $f(x,y)=x+y$.

$u_n=f(u_{n-1},u_{n-2}) \text{ for $n > 1$ with $u_0=1$ and $u_1=0$} ,\\ v_n=f(v_{n-1},v_{n-2}) \text{ for $n > 1$ with $v_0=0$ and $v_1=1$} .$

$a_n=pU_n+qV_n$, where $U_n=F_{n-1}$ and $V_n=F_n$, thus $a_n=pF_{n-1}+qF_n$ for $n>1$. $U_n=F_{n-1}$ because it starts as 1,0,1,1,..., hence behaves like a right shifted Fibonacci sequence.

Exercise 2.7

The homogeneous part remains the same as in the previous exercise. The constant term $r$ "obeys" the same Fibonacci like growth pattern, with a difference, that in each iteration we also add one additional instance of $r$. Imagine always starting a new Fibonacci sequence and adding it to the existing count. We get $a_n=pF_{n-1}+qF_n+r\sum_{k=1}^{n-1}F_k$ for $n>1$. Exercise 3.35 shows how to attain a closed-form solution for the sum of Fibonacci numbers.

Exercise 2.8 🌟

This is a generalization of the previous two exercises.

For $f$ linear, let’s express the solution to the recurrence $a_n=f(a_{n-1},a_{n-2})$ for $n>1$ in terms of $a_0$, $a_1$, $f(0,0)$, $U_n$ and $V_n$, where $U_n$ and $V_n$ are solutions to homogeneous recurrences $u_n$ and $v_n$, respectively:

$u_n=f(u_{n-1},u_{n-2})-f(0,0) \text{ for $n > 1$ with $u_0=1$ and $u_1=0$} ,\\ v_n=f(v_{n-1},v_{n-2})-f(0,0) \text{ for $n > 1$ with $v_0=0$ and $v_1=1$} .$

$\boxed{a_n=a_0U_n+a_1V_n+f(0,0)\sum_{k=1}^{n-1}V_k \qquad \text{for $n>1$}.}$

Exercise 2.9

This immediately reduces to a product

$$\begin{align*} a_n &= \prod_{k=1}^n \frac{k}{k+2} \\ &=\frac{1}{3} \cdot \frac{2}{4} \cdot\cdot\cdot \frac{n-1}{n+1} \cdot \frac{n}{n+2} \\ &= \frac{n!}{(n+2)!/2} \\ &= \frac{2}{(n+1)(n+2)}. \end{align*}$$

Exercise 2.10

This immediately reduces to a sum

$$\begin{align*} a_n &= 1+\sum_{k=1}^n (-1)^kk \\ &= 1+(-1+2- 3+\dots + (-1)^nn) \\ &= 1+\begin{cases} \dfrac{n}{2} &\text{if $n$ is even}, \\ -\dfrac{n+1}{2} &\text{if $n$ is odd}. \end{cases} \\[0.6cm] &=1+ (-1)^n\bigg\lceil \frac{n}{2} \bigg\rceil. \end{align*}$$

Exercise 2.11 🌟

This exercise reminds us that sometimes there is a remarkably easy solution once we start thinking outside the box

The solution is posted on the book’s website.

Exercise 2.12

Following the hint from the book, we get

$$\begin{align*} \frac{a_n}{2^n} &= \frac{a_{n-1}}{2^{n-1}}+\frac{1}{2^n} \\ &= \frac{a_{n-2}}{2^{n-2}}+\frac{1}{2^{n-1}}+\frac{1}{2^n} \\ &= \dots \\ &= \frac{a_1}{2^1}+\frac{1}{2^2}+\dots+\frac{1}{2^n} \\ &\therefore \boxed{a_n=\sum_{k=0}^{n-1}2^k=2^n-1}. \end{align*}$$

Exercise 2.13

Multiply both sides by $(n+1)$ and iterate

$$\begin{align*} (n+1)a_n &= na_{n-1}+(n+1) \\ &=(n-1)a_{n-2}+n+(n+1) \\ &\dots \\ &= a_0+2+\dots+n+(n+1) \\ &= \sum_{k=1}^{n+1} k \\ &= \frac{(n+1)(n+2)}{2} \\ &\therefore \boxed{a_n=\frac{n+2}{2}}. \end{align*}$$

Exercise 2.14 🌟

This is a generalization of Theorem 2.1.

Follow virtually the same steps as in the proof of Theorem 2.1 and stop at $a_t$

$$a_n=y_n+a_t(x_nx_{n-1}\dots x_{t+1})+\sum_{t+1 \le j <n}y_jx_{j+1}x_{j+2}\dots x_n \text{ for $n>t$}.$$

As a sanity check, shift the recurrence in Exercise 2.13 and compute values as described here. For example, use $t=2$ and $a_t=2$ to get $a_7=9/2$ in both ways, via the original recurrence and this synthesized formula. When $x_n=n/(n+1)$ then $x_nx_{n-1}\dots x_{t+1}=(t+1)/(n+1)$.

Exercise 2.15

After dividing both sides by $n$ we’ve

$$\begin{align*} a_n&=\frac{n+1}{n}a_{n-1}+2 \\ &=2+2(n+1)(H_n-1) && \text{(by Theorem 2.1)} \\ &=2(n+1)(H_{n+1}-1) && \text{($2=2(n+1) \cdot \frac{1}{n+1}$)}. \end{align*}$$

Notice, that the recurrence in section 2.2 for $C_N$ isn’t the same as in section 1.5 (the initial conditions are different). Consequently, the solution based on Theorem 2.1 is exactly as given in the book. The reported errata to change -1 to -3/2 is incorrect, since it assumes the recurrence from section 1.5.

Exercise 2.16 🌟

This exercise perfectly illustrates the generalized Theorem 2.1 (see Exercise 2.14).

After dividing both sides by $n$, we get a first-order linear recurrence

$$a_n=\frac{n-4}{n}a_{n-1}+12H_n \qquad \text{for $n>4$ and $a_n=0$ for all $n \le 4$}.$$

Use the generalized Theorem 2.1 with $t=4$. The reduced summation factor $s_{j+1}=x_{j+1}x_{j+2}\dots x_n$ equals to

$$\begin{align*} s_{j+1}&=\frac{j-3}{j+1} \cdot \frac{j-2}{j+2} \cdot \cdot \cdot \frac{n-4}{n} \\ &= \frac{j(j-1)(j-2)(j-3)}{n(n-1)(n-2)(n-3)} \\ &= \frac{\dbinom{j}{4}}{\dbinom{n}{4}}. \end{align*}$$

Substitute back $s_{j+1}$ into the main recurrence

$$\begin{align*} a_n&=12H_n+\frac{12}{\dbinom{n}{4}}\sum_{j=5}^{n-1} {\binom{j}{4}H_j} \\ &=\frac{12}{\dbinom{n}{4}}\sum_{j=5}^n {\binom{j}{4}H_j} \\ &= \frac{12}{\dbinom{n}{4}}\left(\sum_{j=4}^n \left({\binom{j}{4}H_j}\right)-\binom{4}{4}H_4\right) \\[0.8cm] &= \frac{12}{\dbinom{n}{4}}\left(\binom{n+1}{5}\left(H_{n+1}-\frac{1}{5}\right)-H_4\right) && \text{(by formula (6.70))}. \end{align*}$$

The identity (6.70) comes from the book Concrete Mathematics: A Foundation for Computer Science (2nd ed.).

Exercise 2.17 🌟

This exercise highlights an important detail not explicitly mentioned in the text; the summation factor must be nonzero.

Simplify the expression for $A_N$ to get

$$A_N=\frac{N-6}{N}A_{N-1}+2 \qquad \text{for $N>1$ and $A_1=1$}.$$

Before proceeding, we must resolve the base cases for $N \le 6$, ensuring that the summation factor is nonzero. Using the original recurrence for $A_N$ we get $A_2=0, A_3=2,A_4=1,A_5=9/5,A_6=2$. Following the same steps from the previous exercise (see also Table 2.2 from the book), we get

$$A_N=\frac{2(N+1)}{7} \qquad \text{ for $N>6$}.$$

Exercise 2.18

From the signed error term $b_n = a_n - \alpha$, we’ve $a_{n-1} = b_{n-1} + \alpha$. Substitute it back into the main recurrence

$$a_n = \frac{1}{1 + a_{n-1}} = \frac{1}{1 + \alpha + b_{n-1}}.$$

Therefore,

$$\begin{align*} b_n &= a_n - \alpha \\ &= \frac{1}{1 + \alpha + b_{n-1}} - \alpha \\ &= \frac{1 - \alpha(1 + \alpha + b_{n-1})}{1 + \alpha + b_{n-1}} \\ &= \frac{1 - \alpha - \alpha^2 - \alpha b_{n-1}}{1 + \alpha + b_{n-1}} \\ &= -\frac{\alpha}{1 + \alpha + b_{n-1}} \cdot b_{n-1} && \text{($1 - \alpha - \alpha^2 = 0$)}. \end{align*}$$

As $n \to \infty$, $a_n \to \alpha$, thus, $b_n \to 0$; see the next exercise why this holds when $a_0$ is between 0 and 1. For small $b_{n-1}$ we’ve

$$\frac{1}{1 + \alpha + b_{n-1}} \approx \frac{1}{1 + \alpha} \implies b_n \approx -\frac{\alpha}{1 + \alpha} b_{n-1}= -\alpha^2 b_{n-1}.$$

Notice that $\alpha = \frac{1}{1+\alpha} \implies \frac{\alpha}{1 + \alpha} = \alpha^2$. At any rate, $|b_n| \approx 0.4|b_{n-1}|$, which explains why each iteration increases the number of significant digits available by a constant number of digits (about half a digit).

Exercise 2.19 🌟

The solution is known as the Dottie number and revolves around the concept of a fixed point. We must show that all conditions are satisfied for applying the Banach fixed point theorem; it then guarantees that the function $\cos(x)$ converges to a unique fixed point for any $a_0 \in [0,1]$.

Let $f(x)=\cos(x)$ and $x \in [0,1]$. We know that $f:[0,1] \mapsto [0,1]$ and is differentiable on this whole interval. Thus, by the mean value theorem, for any distinct $x,y \in [0,1]$, there’s a point $c \in (x,y)$ such that $f(x)-f(y)=f'(c)(x-y)$. Consequently, we can always express the distance between $f(x)$ and $f(y)$ in terms of the distance between $x$ and $y$. If $|f'(c)| <1$ for all $c \in(0,1)$, then $f$ has a Lipschitz constant less than 1, therefore $f$ is a contraction mapping on $[0,1]$. This is indeed the case, since $|f'(x)|=\sin(x)$ on this interval and $\sin(1)<1$ (sine is strictly increasing in the interval $[0,1]$, see Exercise 2.22).

We can also represent the continued fraction as $f(x)=1/(1+x)$ for $x \in [0,1]$. I’s easy to show that all conditions hold for applying the Banach theorem.

Exercise 2.20

Suppose, for the sake of contradiction, that $a_n=0.5(a_{n-1}-1/a_{n-1})$ has a real fixed point for $n>0$ with $a_0\neq 0$. Since, $a_0$ is a real number, then $a_1=0.5(a_0-1/a_0)$ is also a real number. By induction on $n$, we can conclude that all $a_n$ are real numbers for $n>0$. On the other hand, the fixed point $\sqrt{-1}=i$ isn’t a real number. This is a contradiction, so $\{a_n\}_{n>0}$ diverges.

---

The sequence exhibits chaotic behavior. Let’s use a substitution $a_n=\cot(\theta_n)$. Recall the double-angle identity for cotangent:

$$\cot(2\theta) = \frac{\cot^2\theta - 1}{2\cot\theta} = \frac{1}{2}\left(\cot\theta - \frac{1}{\cot\theta}\right).$$

This exactly matches our recurrence relation. If $a_0=\cot(\theta_0)$, then $a_1=\cot(2\theta_0)$. Therefore, $a_n = \cot(2^n \theta_0)$ and the sequence will fluctuate chaotically, governed by the doubling of the angle in the cotangent function. It’ll either terminate or not. If $a_n$ becomes zero, then the next iteration fails due to division by zero. For example, $a_0=\cot(\pi/4)=1$ will terminate the sequence in the second iteration, since $a_1=0$. It turns out that the sequence terminates if and only if $\theta_0$ is a dyadic rational multiple of $\pi$. That is

$$\theta_0 = \frac{k}{2^m}\pi,$$

where $k$ and $m>0$ are integers. Both directions are trivial to prove.

Exercise 2.21 🌟

This exercise introduces the Stolz–Cesàro theorem, which is a discrete version of L'Hôpital’s rule.

We prove the lower bound in a similar fashion, as the book does for the upper bound

$$\begin{align*} \frac{1}{a_n} &= \frac{1}{a_{n-1}} \left(\frac{1}{1-a_{n-1}}\right) && \text{(for $n>0$)}\\ &=\frac{1}{a_{n-1}}+\frac{1}{1-a_{n-1}} \\ &< \frac{1}{a_{n-1}}+2 && \text{($1-a_{n-1} > 1/2$ for sufficiently large $n$)} \\ &\dots \\ &< 2(n+1) && \text{(telescoping sum)} \\ &\le 3n && \text{(for all $n>1$)} \\ &\therefore \boxed{a_n \ge \frac{1}{3} \cdot \frac{1}{n} = \Omega(1/n)}. \end{align*}$$

Both asymptotic bounds match, hence $a_n=\Theta(1/n) \implies \lim_{n \to \infty}a_n=0$.

---

After computing initial terms, it seems that $a_n \sim c/n$, where $c=1$. Let’s prove that $\lim_{n \to \infty} na_n=\lim_{n \to \infty}\frac{n}{1/a_n}=1$, which matches the $\infty/\infty$ case of the Stolz–Cesàro theorem. It states that if the limit of the differences $\frac{n - (n-1)}{1/a_n - 1/a_{n-1}}$ exists, then $\lim_{n \to \infty} \frac{n}{1/a_n}$ is equal to that same limit. The numerator is 1, and the denominator is $1/(1-a_{n-1})$ (see the derivation of the lower bound). Thus,

$$\lim_{n \to \infty} \frac{1}{1/(1-a_{n-1})} = \lim_{n \to \infty} (1-a_{n-1}) = 1.$$

Since the limit of the differences is 1, the limit of the original sequence is also 1.

Exercise 2.22

First, we prove that $\lim_{n \to \infty}a_n=0$. For $x \in (0,1]$ we have that $0<sin(x)<x$; the geometric proof relies on the definition of radian. Consequently, $a_n$ is a strictly decreasing sequence bounded from below by zero. According to the monotone convergence theorem, it converges to the infimum, which is zero.

---

Since $a_n \to 0$, we can use the Taylor series for $\sin(x)$ around $x=0$:

$$\sin(x) = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \dots = x - \frac{x^3}{6} + O(x^5).$$

Substitute this expansion into the recurrence $a_n = \sin(a_{n-1})$ to get

$$a_n \sim a_{n-1} - \frac{a_{n-1}^3}{6}=a_{n-1}\left(1 - \frac{a_{n-1}^2}{6}\right).$$

If we square both sides of the equation, then we can use the approximation $(1-x)^2 \sim 1-2x$ for small $x$. Thus,

$$\begin{align*} a_n^2 &\sim a_{n-1}^2\left(1 - \frac{a_{n-1}^2}{6}\right)^2 \\ &\sim a_{n-1}^2\left(1 - \frac{a_{n-1}^2}{3}\right). \end{align*}$$

Following the hint from the book to consider change of variable $b_n=1/a_n$ , let’s flip the above equation to get

$$\begin{align*} b_n^2 &\sim \frac{b_{n-1}^2}{ \left(1 - \frac{a_{n-1}^2}{3}\right)} \\ &\sim b_{n-1}^2 \left(1 + \frac{a_{n-1}^2}{3}\right) && \text{($\frac{1}{1-x} \sim 1+x$ for small $x$)} \\ &= b_{n-1}^2 + \frac{1}{3} \\ &= 1+\frac{n}{3} && \text{(telescoping sum)}. \end{align*}$$

Therefore, $b_n=O(\sqrt n) \implies a_n=O(1/\sqrt n)$.

Exercise 2.23

If $f'(\alpha) > 1$ then $\alpha$ is a repelling fixed point. The sequence $a_n = f(a_{n-1})$, starting at any point $a_0$ near $\alpha$ (but not exactly $\alpha$), will diverge from the fixed point $\alpha$. To develop an intuition why, let’s use the familiar error term from the book $b_n=a_n-\alpha$ and monitor how it changes in each iteration.

$$\begin{align*} a_n &= f(a_{n-1}) \\ \alpha + b_n &= f(\alpha + b_{n-1}) \\ &\approx f(\alpha) + f'(\alpha) \cdot b_{n-1} && \text{(by Taylor expansion near $\alpha$, $f(\alpha + b_{n-1}) \approx f(\alpha) + f'(\alpha) \cdot b_{n-1}$)} \\ &\therefore \boxed{|b_n| \approx f'(\alpha) \cdot |b_{n-1}|} && \text{($\alpha=f(\alpha$))}. \end{align*}$$

Since $f'(\alpha) > 1$ the magnitude of the error term grows instead of shrinks. In general, what happens in later iterations highly depends on the global properties of the function. The point is, once the error term becomes small, the above approximation for $b_n$ becomes relevant and it’ll grow again.

Exercise 2.24

The analysis relies on the approximation of the error term $b_n$ from the previous exercise and the precondition stated in the book that $a_0$ is sufficiently close to $\alpha$. The three cases are:

1. If the fixed point $\alpha$ is attracting then local convergence is guaranteed. The error drops by a constant factor $|f'(\alpha)|$ at each step, hence the number of significant digits increases by a fixed amount in each iteration.

2. If the fixed point $\alpha$ is super-attracting, we have guaranteed and fast local convergence. Here, the error term must be more precisely described using a higher-order derivative, assuming $f$ is at least twice continuously differentiable, for example, $b_n \approx \frac12 \left| f''(\alpha) \right| \cdot b_{n-1}^2$. Each iteration approximately doubles the number of significant digits available.

3. If the fixed point $\alpha$ is neutral then convergence isn’t guaranteed. The criteria is more complicated, as described in the excerpt about nonhyperbolic fixed points.

4. If the fixed point $\alpha$ is repelling then convergence isn’t possible.

The lecture notes by Burbulla nicely recaps the basic theory around fixed points with lots of examples. It contains a case study of a unilaterally attracting/repelling neutral fixed point.

Exercise 2.25

The book mentions that restructuring the terms of a recurrence corresponds to factoring the polynomial whose degree equals the order of the recurrence. There are two worked-out examples:

• For $a_n=2^n-1=2^n-1^n$ the "characteristic polynomial" is $(1-2x)(1-x)$ in factored form.

• For $a_n=3^n-2^n$ the "characteristic polynomial" is $(1-3x)(1-2x)$ in factored form.

In our case, we need to work with a cubic polynomial

$$(1-4x)(1-3x)(1-2x) = 1x^0-9x^1+26x^2-24x^3.$$

The term $x^d$ is associated with $a_{n-d}$. Therefore, we can immediately construct our recurrence

$$a_n=9a_{n-1}-26a_{n-2}+24a_{n-3} \space\space\space\space\space\space\text{ for $n>2$}.$$

The initial values are

$$\begin{align*} a_0 &=4^0-3^0+2^0=1 \\ a_1 &=4^1-3^1+2^1=3 \\ a_2 &=4^2-3^2+2^2=11. \end{align*}$$

Exercise 2.26 🌟

This exercise explains how to solve an inhomogeneous recurrence of the form

a_n = x₁a_{n – 1} + x₂a_{n – 2} + ... + x_ta_{n – t} + r for n ≥ t.

The main idea is the same as in Exercise 2.8. The notes for recitation 12, from the course 6.042/18.062J Mathematics for Computer Science (2005), summarize the methodology of solving inhomogeneous linear recurrences. It contains additional examples for each recurrence type.

The paper Some Techniques for Solving Recurrences by GL is a superb tutorial on solving recurrences with advanced material on systematic search (annihilator method) for particular solutions of inhomogeneous linear recurrences. The text covers many recurrence types that occur in practical applications.

At any rate, generating functions handle linear recurrences of this form in a unified manner without worrying about guessing a particular solution or doing any additional searches. Chapter 3 of the book is devoted to this topic.

Exercise 2.27

We know that $a_n=c_03^n+c_12^n$, as stated in the book. Furthermore, we have

$$\begin{align*} a_0&=c_0+c_1 \\ a_1&=3c_0+2c_1. \end{align*}$$

We need to work backwards to find initial conditions resulting in $c_0=0$ and $c_1=1$. We immediately get $a_0=1$ and $a_1=2$.

---

There are no initial conditions for which the solution is $a_n=2^n-1$. Irrespectively of boundary conditions, $a_n$ must satisfy the recurrence, which isn’t the case here.

Exercise 2.28

The exercise from the book mentions $a_n=2a_{n-1}-a_{n-2}+2a_{n-3}$ for $n>2$. The characteristic equation has two complex roots, so the general solution is $a_n = c_02^n + c_1i^n + c_2(-i)^n$. However, there is no way to set initial conditions for $a_n$ to be constant, except trivially being zero, which is only a special case. So, we assume that this exercise is about the recurrence given in the main text.

By tweaking the initial conditions, we can fundamentally alter the growth rate of the solution to

$$a_n=2a_{n-1}+a_{n-2}-2a_{n-3} \space\space\space\space \text{ for $n>2$}.$$

We use the same approach as in the previous exercise. Here are the initial conditions leading to each desired growth rate of $a_n$:

• Constant is achieved when $a_0=a_1=a_2=c_0$. For example, $a_0=a_1=a_2=2$ makes $a_n=2$.

• Exponential is achieved when $a_0=c_2$, $a_1=2c_2$ and $a_2=4c_2$. For example, $a_0=1$, $a_1=2$ and $a_2=4$ makes $a_n=2^n$.

• Fluctuating in sign is achieved when $a_0=c_1$, $a_1=-c_1$ and $a_2=c_1$. For example, $a_0=1$, $a_1=-1$ and $a_2=1$ makes $a_n=(-1)^n$.

Exercise 2.29

The characteristic equation is $z^2-2z-4=0$ whose roots are $z_1=1+\sqrt5$ and $z_2=1-\sqrt5$. Therefore, the general solution is $a_n=c_0(1+\sqrt 5)^n+c_1(1-\sqrt5)^n$ for $n>1$. We also have the following system of linear equations:

$$\begin{align*} a_0&=1=c_0+c_1 \\ a_1&=2=c_0(1+\sqrt 5)+c_1(1-\sqrt 5). \end{align*}$$

The constants are $c_0=\frac{\sqrt5+1}{2\sqrt5}$ and $c_1=\frac{\sqrt5-1}{2\sqrt5}$.

Exercise 2.30

The characteristic equation is $z^2-2z+1=0$ whose double root is $z_1=1$. Therefore, the general solution is $a_n=c_0+c_1n$ for $n>1$.

---

We also have the following system of linear equations:

$$\begin{align*} a_0&=0=c_0\\ a_1&=1=c_0+c_1. \end{align*}$$

The constants are $c_0=0$ and $c_1=1$.

---

If we change the initial conditions, then we get another system of linear equations:

$$\begin{align*} a_0&=1=c_0\\ a_1&=1=c_0+c_1. \end{align*}$$

The constants are $c_0=1$ and $c_1=0$.

Exercise 2.31 🌟

This exercise illustrates how to handle complex roots and transform them into trigonometric form.

The characteristic equation is $z^2-z+1=0$ whose complex roots are $z_1=(1+\sqrt3i)/2$ and $z_2=(1-\sqrt3i)/2$. We could continue as usual, but the expression for $a_n$ would be awkward. Let’s use Euler’s formula to convert complex numbers into trigonometric form. The roots can be represented as $e^{±i\frac{\pi}{3}}=\cos(\frac{\pi}{3})±i\sin(\frac{\pi}{3})$. Thankfully to Euler’s formula, exponentiation becomes trivial. The general solution is

$$\begin{align*} a_n&=c_0e^{in\frac{\pi}{3}}+c_1e^{-in\frac{\pi}{3}}\\ &=(c_0+c_1)\cos\left(n\frac{\pi}{3}\right)+i(c_0-c_1)\sin\left(n\frac{\pi}{3}\right) \\ &=c'_0\cos\left(n\frac{\pi}{3}\right)+c'_1\sin\left(n\frac{\pi}{3}\right). \end{align*}$$

Since the sequence $a_n$ is real (it starts with real numbers $a_0, a_1$ and has real coefficients), the constants $c_0'$ and $c_1'$ must be reals, too. Consequently, the constants $c_0$ and $c_1$ must be complex conjugates. We also have the following system of linear equations:

$$\begin{align*} a_0 &=0= c'_0 \cos(0) + c'_1 \sin(0) \\ a_1&=1=c'_0\cos\left(\frac{\pi}{3}\right) + c'_1 \sin\left(\frac{\pi}{3}\right). \end{align*}$$

The constants are $c'_0=0$ and $c'_1=2/\sqrt3$. Thus,

$$a_n=\frac{2}{\sqrt3}sin\left(n\frac{\pi}{3}\right) \space\space\space\space\text{ for $n>1$}.$$

This was an amazing journey from a seemingly straightforward second-order linear recurrence to the trigonometric solution via complex algebra.

Exercise 2.32

The characteristic equation is $2z^3 - 3z^2 + 3z - 1 = 0$. Let’s first search for a rational root. If we can find one, then by dividing the original polynomial with the corresponding factor, we get a quadratic equation. The latter is then directly solvable. The rational root theorem enumerates all rational candidates. It turns out that ½ is a root, thus $(2z-1)$ is a factor.

Using a classical polynomial division algorithm, we get that the characteristic equation in factored form is

$$(z^2 - z + 1)(2z-1)=0.$$

The other two complex roots are $z_{2,3} = \frac{1}{2} ± i\frac{\sqrt{3}}{2}$. Using the same transformation as in the previous exercise, we can write down the general solution as

$$a_n = c_0 \left(\frac{1}{2}\right)^n + c_1 \cos\left(\frac{n\pi}{3}\right) + c_2 \sin\left(\frac{n\pi}{3}\right).$$

We also have the following system of linear equations:

$$\begin{align*} a_0 &= 0=c_0 + c_1 \\ a_1&=1 = \frac{1}{2} c_0 + \frac{1}{2} c_1 + \frac{\sqrt{3}}{2} c_2 \\ a_2&=2 = \frac{1}{4} c_0 - \frac{1}{2} c_1 + \frac{\sqrt{3}}{2} c_2. \end{align*}$$

The constants are $c_0=4/3$, $c_1=-4/3$ and $c_2= 2/\sqrt{3}$.

Exercise 2.33

Let’s split the problem into two subproblems based on parity of $n>1$

$$a_n=\begin{cases} 2a_{n-2} &\text{if $n$ is even,} \\ \cfrac{1}{2}a_{n-2} &\text{if $n$ is odd}. \end{cases}$$

We can combine both cases into a single recurrence $a_n=2^{(-1)^n}a_{n-2}$ for $n>1$. The initial conditions are $a_0=a_1=1$.

Exercise 2.34

The sequence is known as Tribonacci numbers. The characteristic equation is $z^3-z^2-z-1=0$, whose single real root is the Tribonacci constant $\alpha \approx 1.839286755.$ The other two complex roots $\beta$ and $\gamma$ have magnitudes less than one, hence they tend to zero for large $N$. Therefore, the approximate general solution is

$$\boxed{F_N^{(3)} \approx c_0 \alpha^N}.$$

Tools are useful in finding roots of the characteristic polynomial. For example, issuing x^3-x^2-x-1=0 in WolframAlpha gives three solutions (one real and two complex). Switching to trigonometric form reveals the magnitudes of complex roots.

Finding the Unknown Constant

To find $c_0$ we need to use the exact general solution

$$F_N^{(3)} = c_0 \alpha^N + c_1 \beta^N + c_2 \gamma^N.$$

We have the following system of linear equations:

$$\begin{align*} 0& = c_0 + c_1 + c_2 \\ 0 &= c_0 \alpha + c_1 \beta + c_2 \gamma \\ 1 &= c_0 \alpha^2 + c_1 \beta^2 + c_2 \gamma^2. \end{align*}$$

Let’s solve for $c_0$ by running the next Sage script:

It outputs

$$c_0 = \frac{1}{(\alpha - \beta)(\alpha - \gamma)}.$$

The characteristic polynomial is $P(z)=z^3-z^2-z-1=(z-\alpha)(z-\beta)(z-\gamma)$. Let’s take the derivative of $P(z)$ on both sides and make them equal for $\alpha$. On the left we have

$$\begin{align*} P'(z) &= \frac{d}{dz} [z^3-z^2-z-1] \\ &= 3z^2-2z-1 \\ &\therefore P'(\alpha)= 3{\alpha}^2 - 2{\alpha} - 1 \end{align*}$$

On the right we get

$$\begin{align*} P'(z) &= \frac{d}{dz} [(z-\alpha)(z-\beta)(z-\gamma)] \\ &= (z-\beta)(z-\gamma) + (z-\alpha)(z-\gamma) + (z-\alpha)(z-\beta) \\ &\therefore P'(\alpha) = (\alpha-\beta)(\alpha-\gamma). \end{align*}$$

Consequently, $(\alpha-\beta)(\alpha-\gamma)=3{\alpha}^2 - 2{\alpha} - 1$, which gives us the value of $c_0$ in terms of $\alpha$

$$c_0 = \frac{1}{3\alpha^2 - 2\alpha - 1}.$$

Estimating the Accuracy

We can calculate the exact and approximate value of $F_{20}^{(3)}$ using the following Python script.

It outputs 35890 ~ 35889.999620092305. They are indeed very close.

Exercise 2.35

Let’s define a new sequence $b_n = n! \cdot a_n \implies a_n = \frac{b_n}{n!}$. If we substitute this back into the main recurrence, we get

$$\begin{align*}n(n - 1) \cdot \frac{b_n}{n!} &= (n - 1) \cdot \frac{b_{n - 1}}{(n - 1)!} + \frac{b_{n - 2}}{(n - 2)!} \\ \frac{b_n}{(n-2)!} &= \frac{b_{n-1}}{(n-2)!} + \frac{b_{n - 2}}{(n - 2)!} \\ &\therefore \boxed{b_n = b_{n - 1} + b_{n - 2}} && \text{(for $n>1$)}.\end{align*}$$

The initial conditions are $b_1=b_0=1$, thus $b_n=F_{n+1}$. Therefore,

$$a_n=\frac{F_{n+1}}{n!}.$$

Exercise 2.36

The following Python script implements the algorithm for checking the validity of a monomial; covers both types of monomials (pure and mixed). The running time is $\Theta(p\lg p + q\lg q)$.

In the expansion of $a_n$, for $n>1$, we have $F_n-1-\frac{1-(-1)^n}{2}$ mixed monomials (consisted of both symbols $s_i$ and $t_j$). The total number of such monomials, across all iterations, is

$$\begin{align*} \sum_{k=2}^n\left(F_k-1-\frac{1-(-1)^k}{2}\right) &= F_{n+2}-F_3-(n-1)-\bigg\lfloor\frac{n-1}{2}\bigg\rfloor \\ &= F_{n+2}-n-1-\bigg\lfloor\frac{n-1}{2}\bigg\rfloor. \end{align*}$$

For example, when $n=6$ this formula evaluates to 12, which matches the number of mixed monomials listed in the book.

If we count all monomials, including initial values, then the formula for their total number is $F_{n+2}-1$.

Exercise 2.37

Solving $b_n$ proceeds along the same steps as in Exercise 2.29 and won’t be repeated here. The exact solution is

$$b_n=\frac{2}{3}\left(1-\left(-\frac{1}{2}\right)^n\right) \space\space\space\space\text{ for $n>1$},$$

and $a_n=2^{b_n}$ for $n>1$.

Exercise 2.38

Let’s square both sides of the initial recurrence to get $a_n^2=1+a_{n-1}^2$ for $n>0$. If we introduce a substitution $b_n=a_n^2$ then the recurrence transforms into $b_n=1+b_{n-1}$, thus $b_n=n$. Therefore, $a_n=\sqrt n$ for $n>0$.

Exercise 2.39

For $a_0=3$ the solution is

$$a_n = \left(\frac{3 + \sqrt{5}}{2}\right)^{2^n} + \left(\frac{3 - \sqrt{5}}{2}\right)^{2^n}.$$

As the book notes, only the larger of the two roots predominates in this expression—the one with the plus sign.

---

For $a_0=4$ the solution is

$$a_n = (2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n}.$$

Again, only the larger of the two roots predominates in this expression—the one with the plus sign.

---

For $a_0=3/2$ the solution is fundamentally different. The roots $b_0$ are complex numbers

$$b_0=\frac{1}{2}\left(\frac{3}{2} ± \sqrt{-7/4}\right) = \frac{3}{4} ± i\frac{\sqrt{7}}{4}.$$

We can use the same approach as in Exercise 2.31 to transform these into trigonometric form. Let $b_0=e^{±i\theta}$, where $\theta=\arccos(3/4)$, thus the recurrence becomes

$$\begin{align*} a_n &= (e^{i\theta})^{2^n} + (e^{-i\theta})^{2^n} \\ &= e^{i(2^n\theta)} + e^{-i(2^n\theta)} \\ &= 2\cos(2^n\theta) && \text{($e^{ix} + e^{-ix} = 2\cos(x)$ because $\sin(-x)=-\sin(x)$)} . \end{align*}$$

The sequence $a_n$ fluctuates between -2 and 2, never settling on a single value.

Exercise 2.40 🌟

This exercise introduces the bifurcation theory; as demonstrated in the previous exercise, a fundamentally different behavior occurs around the bifurcation point $a_0=2$.

The accurate approximate answer for large $\epsilon$ and sufficiently large $n$ is $a_n \approx a_0^{2^n}$. Usually, in expressions like $a_0=2+\epsilon$, $\epsilon$ is a small positive constant, so the subsequent analysis assumes this situation. The critical term is

$$\begin{align*} \sqrt{a_0^2 - 4} &= \sqrt{(a_0-2)(a_0+2)} \\ &= \sqrt{\epsilon(4 + \epsilon)} \\ &\approx 2\sqrt{\epsilon} && \text{($\epsilon \ll 1 \implies \epsilon \gg \epsilon^2$)}. \end{align*}$$

For the larger root we have

$$\begin{align*} b_0^+ &= \frac{1}{2}(a_0 + \sqrt{a_0^2 - 4}) \\ &\approx \frac{1}{2}( (2 + \epsilon) + 2\sqrt{\epsilon}) \\ &= 1 + \frac{\epsilon}{2} + \sqrt{\epsilon} \\ &\approx 1 + \sqrt{\epsilon} && \text{($\epsilon \ll 1 \implies \sqrt{\epsilon} \gg \epsilon$)}. \end{align*}$$

For the smaller root we have

$$\begin{align*} b_0^- &= \frac{1}{2}(a_0 - \sqrt{a_0^2 - 4}) \\ &\approx \frac{1}{2}( (2 + \epsilon) - 2\sqrt{\epsilon}) \\ &= 1 + \frac{\epsilon}{2} - \sqrt{\epsilon} \\ &\approx 1 - \sqrt{\epsilon}. \end{align*}$$

As $n$ increases, ${(b_0^-)}^{2^n}$ will rapidly vanish to 0. Consequently, we get $a_n \approx (1 + \sqrt{\epsilon})^{2^n}$. This shows that even for an infinitesimally small $\epsilon$, the sequence $a_n$ diverges to infinity at a double-exponential rate.

Exercise 2.41 🌟

This exercise shows a mechanism of transforming generic quadratic recurrences into the register allocation type recurrence, whose solution space is known.

Assume that $f \neq 0$. Otherwise, we can define $g=2$ and all sequences $a_n$ would "turn" into $b_n=b_{n-1}^2-2$ by using the transformation $b_n=0\cdot a_n+g$.

We expand $b_n$ to match parameters

$$\begin{align*} b_n &= b_{n-1}^2 - 2 \\ &= (f a_{n-1} + g)^2 - 2 && \text{($b_{n-1}=f a_{n-1} + g$)} \\ &= f^2 a_{n-1}^2 + 2fg a_{n-1} + g^2 - 2. \end{align*}$$

Let’s express $a_n$ in terms of $f$ and $g$ starting with $b_n=f a_n + g$

$$\begin{align*} f a_n + g &= f^2 a_{n-1}^2 + 2fg a_{n-1} + g^2 - 2 \\ f a_n &= f^2 a_{n-1}^2 + 2fg a_{n-1} + (g^2 - g - 2) \\ a_n &= \left(\frac{f^2}{f}\right) a_{n-1}^2 + \left(\frac{2fg}{f}\right) a_{n-1} + \left(\frac{g^2 - g - 2}{f}\right) \\ &= \boxed{f a_{n-1}^2 + 2g a_{n-1} + \frac{g^2 - g - 2}{f}}. \end{align*}$$

We now match the coefficients of this result with the given recurrence $a_n = \alpha a_{n-1}^2 + \beta a_{n-1} + \gamma$ and derive the necessary and sufficient condition for transforming $a_n$ into $b_n=b_{n-1}^2-2$:

• $\alpha = f$

• $\beta = 2g \implies g=\beta/2$

• $\gamma = \frac{g^2 - g - 2}{f}=\frac{\beta^2/4 - \beta/2 - 2}{\alpha} \implies \boxed{4\alpha\gamma = \beta^2 - 2\beta - 8}$.

---

For $a_n = a_{n-1}^2 + 1$ the parameters are $\alpha=1$, $\beta=0$ and $\gamma=1$. Clearly

$$4\alpha\gamma =4 \bold{\neq} \beta^2 - 2\beta - 8=-8.$$

This shows that it doesn’t reduce to the target form.

Exercise 2.42

We need to solve the recurrence $a_n=2a_{n-1} \sqrt{1-a_{n-1}^2}$ for $n>0$ and different initial values. Let’s square both sides and use the substitution $b_n=a_n^2$. We get

$$\begin{align*} a_n^2&=4a_{n-1}^2(1-a_{n-1}^2) \\ &\implies b_n=4b_{n-1}(1-b_{n-1})=\boxed{-4b_{n-1}^2+4b_{n-1}}. \end{align*}$$

The idea is to leverage the result from the previous exercise and transform $b_n$ into $c_n=c_{n-1}^2-2$. The parameters are $\alpha=-4=f$, $\beta=4=2g$ and $\gamma=0$. Since $4 \cdot (-4) \cdot 0=4^2-2 \cdot 4-8$, we can apply the transformation, thus $c_n=-4b_n+2$.

---

If $a_0=1/2$, then $b_0=1/4$, hence $c_0=1$. We already know the solution from the book for this special case, namely $c_n=-1$. Therefore, $b_n=3/4$ which implies that $a_n=\sqrt 3/2$ for $n>0$.

---

If $a_0=1/3$, then $b_0=1/9$, thus $c_0=14/9$. We hit the third case in Exercise 2.39, so the solution is $c_n=2\cos(2^n\theta)$, where $\theta=\arccos(7/9)$. Therefore, $b_n=(1-\cos(2^n\theta))/2$, which implies that $a_n=\sqrt {(1-\cos(2^n\theta))/2}$.

---

Here’s the Python script to plot $a_6$ as a function of $a_0$.

A change in the initial condition $a_0$ has an unpredictable effect on $a_6$. This is especially evident as $a_0$ approaches 1. At large scale, we see some regularities. These traits are typical for dynamic systems investigated by the chaos theory.

Exercise 2.43 🌟

This exercise shows a way to express general classes of “continued fraction” representations as solutions to recurrences.

Let’s represent the recurrence as a function $f(x) = (\alpha x+\beta)/(\gamma x+\delta)$, where $\gamma \neq 0$ (otherwise, we won’t have a continued fraction). This function defines a Möbius transformation. We first need to determine the fixed points denoted by $r$ and $s$. Afterward we can leverage a change of variable to linearize the original recurrence.

Distinct Roots

$$\begin{align*} b_n &= \frac{a_n - r}{a_n - s} \\[0.3cm] &= \frac{f(a_{n-1}) - r}{f(a_{n-1}) - s} \\[0.3cm] &= \frac{\cfrac{\alpha a_{n-1}+\beta}{\gamma a_{n-1}+\delta}-r}{\cfrac{\alpha a_{n-1}+\beta}{\gamma a_{n-1}+\delta}-s} \\[0.9cm] &= \frac{\cfrac{\alpha a_{n-1}+\beta-r\gamma a_{n-1}-r\delta}{\gamma a_{n-1}+\delta}}{\cfrac{\alpha a_{n-1}+\beta-s\gamma a_{n-1}-s\delta}{\gamma a_{n-1}+\delta}} \\[0.9cm] &= \frac{\alpha a_{n-1}+\beta-r\gamma a_{n-1}-r\delta}{\alpha a_{n-1}+\beta-s\gamma a_{n-1}-s\delta} && \text{(assuming $\gamma a_{n-1}+\delta \neq 0$)}\\[0.3cm] &= \frac{\alpha \cfrac{r-sb_{n-1}}{1-b_{n-1}}+\beta-r\gamma \cfrac{r-sb_{n-1}}{1-b_{n-1}}-r\delta}{\alpha \cfrac{r-sb_{n-1}}{1-b_{n-1}}+\beta-s\gamma \cfrac{r-sb_{n-1}}{1-b_{n-1}}-s\delta} && \text{$\left(a_{n-1}=\cfrac{r-sb_{n-1}}{1-b_{n-1}}\right)$}\\[0.9cm] &= \frac{\cfrac{\alpha r - \alpha sb_{n-1} +\beta - \beta b_{n-1} -r^2\gamma + r\gamma sb_{n-1} -r\delta +r\delta b_{n-1}}{1-b_{n-1}}} {\cfrac{\alpha r - \alpha sb_{n-1} +\beta - \beta b_{n-1} -sr\gamma + s^2\gamma b_{n-1} -s\delta +s\delta b_{n-1}}{1-b_{n-1}}} \\[0.9cm] &= \frac{\alpha r - \alpha sb_{n-1} +\beta - \beta b_{n-1} -r^2\gamma + r\gamma sb_{n-1} -r\delta +r\delta b_{n-1}} {\alpha r - \alpha sb_{n-1} +\beta - \beta b_{n-1} -sr\gamma + s^2\gamma b_{n-1} -s\delta + s\delta b_{n-1}} && \text{(assuming $b_{n-1} \neq 1$)} \\[0.3cm] &= \frac{(-s\alpha - \beta + rs\gamma +r\delta) b_{n-1} -(r^2\gamma + r\delta -r\alpha-\beta)} {r\alpha +\beta -sr\gamma -s\delta + (s^2\gamma + s\delta -s\alpha - \beta)b_{n-1}} \\[0.3cm] &= \frac{-s\alpha - \beta + rs\gamma +r\delta} {r\alpha +\beta -sr\gamma -s\delta} \cdot b_{n-1} && \text{($r$ and $s$ are roots of the quadratics)} \\[0.3cm] &= \frac{\gamma s + \delta}{\gamma r + \delta} \cdot b_{n-1} && \text{($-s\alpha - \beta=-s^2\gamma - s\delta$ and $r\alpha +\beta=r^2\gamma + r\delta$)}\\[0.3cm] &= \left(\frac{\gamma s + \delta}{\gamma r + \delta}\right)^n b_0 && \text{(iterating)}. \end{align*}$$

The initial value is $b_0=(a_0-r)/(a_0-s)=(1-r)/(1-s)$. If we substitute $b_0$ into the expression for $a_n$, assuming $s \neq 1$, we get

$$\boxed{a_n=\frac{r(1-s) - s(1-r)\left(\cfrac{\gamma s+\delta}{\gamma r+\delta}\right)^n}{(1-s) - (1-r)\left(\cfrac{\gamma s+\delta}{\gamma r+\delta}\right)^n}} \space\space\space\space \text{ for $n>0$}.$$

As a quick check, we should get the closed-form solution for the continued fraction example from the book by using $\alpha=0,\beta=1,\gamma=1$ and $\delta=1$. The roots of the equation $x^2+x-1=0$ are $r=-\phi$ and $s=-\hat \phi$. If we substitute these values into the formula for $a_n$, and use the properties of the golden ratio, then we get $a_n=F_{n+1}/F_{n+2}$ for $n \ge 0$.

The book erroneously states that $b_n=F_{n+1}$ instead of $b_n=F_{n+2}$. The correct initial conditions are $b_0=1$ and $b_1=2$.

Repeated Roots

When a Möbius transformation has a single, repeated fixed point $r=s$, it is classified in dynamical systems as a parabolic transformation. We need to use a different change of variable

$$b_n = \frac{1}{a_n - r}.$$

Without repeating a similar grueling algebra, the outcome is

$$b_n = b_{n-1} + \frac{2\gamma}{\alpha + \delta} \implies b_n= b_0 + n\frac{2\gamma}{\alpha + \delta}.$$

Flip the substitution back to get the closed form for $a_n$.

Exercise 2.44 🌟

This exercise demonstrates the use of substitution to simplify sequences. Calculating values directly is often difficult and can result in accuracy loss over time. By using an integer sequence, exactness is maintained, allowing any value to be expressed as a rational number at each step.

Let $a_n=b_n/b_{n+1}$ for $n\ge0$. We need to specify a linear recurrence relation on $b_n$ such that $a_n$ also satisfies the original non-linear recurrence. We have

$$\begin{align*} a_n &= \frac{1}{s_n + t_n a_{n-1}} \\ \cfrac{b_n}{b_{n+1}} &= \frac{1}{s_n + t_n \cfrac{b_{n-1}}{b_n}} \\ \cfrac{b_n}{b_{b+1}} &= \cfrac{1}{\cfrac{s_n b_n + t_n b_{n-1}}{b_n}} \\ \cfrac{b_n}{b_{n+1}} &= \cfrac{b_n}{s_n b_n + t_n b_{n-1}} \\ &\therefore \boxed{b_{n+1} = s_n b_n + t_n b_{n-1}}. \end{align*}$$

The initial conditions must satisfy

$$\begin{align*} a_0 &= \frac{b_0}{b_1} \\ 1 &= \frac{b_0}{b_1} \\ &\implies b_1=b_0 \end{align*}$$

We can choose any starting value for $b_0$.

As a quick check, we should get the closed-form solution for the continued fraction example from the book by using $b_0=1,s_n=1$ and $t_n=1$. Indeed, $b_n=F_{n+1}$ implying $a_n=F_{n+1}/F_{n+2}$ for $n \ge 0$.

Exercise 2.45 🌟

This exercise replaces the bad example in the book and demonstrates how a repertoire table streamlines analysis by allowing reuse of many entries.

We are given a relaxed quicksort recurrence

$$a_n=f(n)+\frac{2}{n} \sum_{1 \le j \le n} a_{j-1} \space\space\space\space \text{ for $n>0$ with $a_0=0$}.$$

Let’s solve it when $f(n)=n^3$.

---

The repertoire table from the book has many reusable entries except for the $n^3$ term. If we set $a_n=n^3$ then $a_n-(2/n)\sum_{j=1}^n a_{j-1}=n^3/2+n^2-n/2$. We need to combine entries from the expanded table to get $f(n)=n^3$, thus we have

$$n^3=2 \left(\frac{n^3}{2} +n^2 - \frac{n}{2}\right) - 6 \left(\frac{n^2 - 1}{3}+ n - 1\right) + 14\left(\frac{n - 1}{2}+H_n\right) + 14(-H_n+2) - 29 \cdot 1.$$

Therefore, the solution is

$$a_n=2n^3-6n(n-1)+14(n+1)H_n-29n \space\space\space\space\text{ for $n\ge0$}.$$

Exercise 2.46

The post on StackExchange for Mathematics explains the basics of the repertoire method and illustrates its application by solving this exercise.

Exercise 2.47 🌟

The solution of this problem illustrates the basic form of the bootstrapping method.

Let’s use the next Python script to calculate numerical values of $a_n$, alongside our guess that $a_n\sim2/n$. This hypothesis is based on the observation that $a_{n-1} \to 0$ as $n \to \infty$.

The output shows that we’re on the right track.

If we employ bootstrapping and substitute our guess back into the recurrence, we get

$$a_n \sim \frac{2(n-1)}{n^2-n+2}=\frac{2n}{n^2-n+2}+O(1/n^2).$$

The new version of the script reflects this change.

The results are better aligned as $n$ increases.

After an additional iteration we have

$$a_n \sim \frac{2 (n^2 - 3 n + 4)}{(n-1)(n^2 - 2 n + 4)}=\frac{2n^2}{(n-1)(n^2 - 2 n + 4)}-\frac{6n}{(n-1)(n^2 - 2 n + 4)}+O(1/n^3) \quad \text{ for $n>1$}.$$

We see that the approximation of $a_n$ is improved again.

This process may continue depending on a desired accuracy level.

There’s no simple closed-form solution. The standard method to "solve" it is based on the technique from Exercise 2.44. In this case, the substitution should be $a_n=2b_{n-1}/b_n$ for $n\ge1$, that yields $b_n=s_nb_{n-1}+2t_nb_{n-2}$, where $s_n=n$ and $t_n=1$. The initial values are $b_0=1$ and $b_1=2$.

Exercise 2.48

The book assumes (without stating it explicitly) that we need to find the approximation of the average number of compares used by median-of-three quicksort. For the sake of completeness, it’s repeated here

$$C_N = N+1 + \frac{2}{\binom{N}{3}} \sum_{k=1}^{N} (k-1)(N-k) C_{k-1} \space\space\space\space \text{ for $N>2$}.$$

The key is to convert this discrete recurrence into its continuous form, by approximating the sum with a definite integral. Converting a discrete sum into a definite integral is a good choice for expected (average) values. The integral elegantly smooths out local discrete fluctuations, providing a highly accurate asymptotic approximation without the need for cumbersome error tracking. At any rate, the process can be broken down into three major stages.

1

Converting the Discrete Recurrence

Let’s simplify the constant multiplier of the sum for large enough $N$

$$\begin{align*} \frac{2}{\binom{N}{3}} &= \frac{2}{\cfrac{N(N-1)(N-2)}{6}} \\ &\sim \frac{2}{N^3/6} \\ &= \frac{12}{N^3}. \end{align*}$$

Let’s set the pivot’s rank $k$ relative to the size $N$; for this we use the continuous variable $x = k/N \implies k = xN \implies dk = N dx$. Finally, we treat $k-1 \sim k$ and $N+1 \sim N$. If we substitute these changes into our original expression and replace the summation with an integral, we have

$$C_N \sim N+ 12 \int_{0}^{1} (x-x^2) C_{xN} \,dx.$$

2

Bootstrapping the Solution

Our initial hypothesis is $C_N \sim \alpha N \ln N$. After all, we expect to have a familiar asymptotic form $\Theta(N \ln N)$ as other quicksort variants. Let’s substitute this hypothesis into our recurrence relation

$$\begin{align*} C_N &\approx N + 12 \int_{0}^{1} C_{xN} (x-x^2) \,dx \\ &\approx N + 12 \int_{0}^{1} \alpha (xN) \ln(xN) (x-x^2) \,dx \\ &= N + 12 \alpha N \int_{0}^{1} x (\ln N + \ln x)(x-x^2) \,dx && \text{($\ln(xN) = \ln N + \ln x$)} \\ &= N + 12 \alpha N \int_{0}^{1} (x^2 \ln N - x^3 \ln N + x^2 \ln x - x^3 \ln x) \,dx. \end{align*}$$

Let’s split this integral into the $\ln N$ part and the $\ln x$ part.

$$\begin{align*} 12 \alpha N \ln N \int_{0}^{1} (x^2 - x^3) \,dx &= 12 \alpha N \ln N \left[ \frac{x^3}{3} - \frac{x^4}{4} \right]_{0}^{1} \\ &= \mathbf{\alpha N \ln N}. \end{align*}$$

$$\begin{align*} N+12 \alpha N \int_{0}^{1} (x^2 \ln x - x^3 \ln x) \,dx &= N+12 \alpha N \left( \left[ \int_{0}^{1} x^2 \ln x \,dx \right]-\left[ \int_{0}^{1} x^3 \ln x \,dx \right] \right) \\ &= N+12 \alpha N \left( \left[ -\frac{1}{(2+1)^2} \right] - \left[ -\frac{1}{(3+1)^2} \right] \right) \\ &= N- \frac{7\alpha}{12} N \\ &= \mathbf{\left(1 - \frac{7\alpha}{12}\right) N}. \end{align*}$$

In the second line, we used the identity $\int_0^1 x^k \ln x \,dx = -\frac{1}{(k+1)^2}$.

3

Determining the Value of $\alpha$

Bootstrapping confirms the statement from the book that

$$\begin{align*} C_N &\approx \underbrace{(\alpha N \ln N)}_{\text{Initial}} + \underbrace{\left(1 - \frac{7\alpha}{12}\right) N}_{\text{Expanded}} \\ &= \alpha N \ln N + O(N). \end{align*}$$

If we want to retain only the leading factor, then we should choose $\alpha=12/7$ to "eradicate" the $O(N)$ summand.

To be rigorous, we should check that this form is "stable"; if we assume $\alpha N \ln N + O(N)$, we must get $\alpha N \ln N + O(N)$ back. This is indeed true, since the definite integral

$N + 12 \int_{0}^{1} [\alpha (xN) \ln(xN)+\beta N] (x-x^2) \,dx$

resolves again to the same form. $\beta$ denotes the hidden constant inside the $O(N)$ term.

Exercise 2.49 🌟

This exercise showcases an advanced usage of the bootstrapping method.

With bootstrapping we start with a rough bound and then improve it step by step. The altered recurrence is

$$a_n = \frac{1}{n^2} + \frac{1}{n} \sum_{1 \le k < n} \frac{a_k}{n-k} \qquad \text{ for $n>0$ with $a_0=1$},$$

where the $k=0$ term is separated out. When the goal is to establish strict upper bounds, converting a sum to an integral introduces unnecessary complications. We would need to carefully cover the error gaps. It’s far more easier to apply a splitting technique, as explained below.

Iteration 1

Let’s start with the rough guess that $a_n = O(1/n)$ for $n>0$. Thus, there exists some constant $c>0$ such that $a_n \le c/n$ for sufficiently large $n$. Note that $a_n>0$ for all $n\ge0$. If we substitute this into the recurrence, we have

$$\begin{align*} a_n &\le \frac{1}{n^2} + \frac{1}{n} \sum_{1 \le k < n} \frac{c}{k(n-k)} \\ &= \frac{1}{n^2} + \frac{c}{n^2} \sum_{1 \le k < n} \left( \frac{1}{k} + \frac{1}{n-k} \right) && \text{$\left(\cfrac{1}{k(n-k)} = \cfrac{1}{n} \left( \cfrac{1}{k} + \cfrac{1}{n-k} \right)\right)$} \\ &= \frac{1}{n^2} + \frac{c}{n^2} (2 H_{n-1}) \\[0.4cm] &\sim \frac{1}{n^2} + \frac{2c \ln n}{n^2} \\ &\therefore \boxed{a_n=O\left(\frac{\log n}{n^2}\right)}=O(1/n). \end{align*}$$

Iteration 2

We assume that $a_n \le c \frac{\ln n}{n^2}$ for some constant $c>0$ and $n>0$. If we substitute this into the recurrence, we have

$$a_n \le \frac{1}{n^2} + \frac{c}{n} \sum_{1 \le k < n} \frac{\ln k}{k^2 (n-k)}.$$

To upper bound the sum $S = \sum_{1 \le k < n} \frac{\ln k}{k^2 (n-k)}$, we split it into two parts. The split typically occurs at the midpoint (e.g., $n/2$). The approach involves independently constraining each region—either by limiting the growth of an expanding component or by anchoring a diminishing component at its maximal value. This method generally yields two independent asymptotic approximations, which are subsequently combined to bound the entire sum. For convenience assume that $n$ is even.

When $1 \le k \le n/2$ then $n-k \ge n/2 \implies 1/(n-k) \le 2/n$. We have

$$S_1 \le \frac{2}{n} \sum_{1 \le k \le n/2} \frac{\ln k}{k^2} < \frac{2}{n} \sum_{k=1}^\infty \frac{\ln k}{k^2}=O(1/n).$$

The infinite series $\sum_{k=1}^{\infty} \frac{\ln k}{k^2}$ converges to a constant.

When $n/2 < k < n$ then $\frac{\ln k}{k^2}$ attains its maximum value at the start of the range, bounded by $\approx \frac{\ln(n/2)}{(n/2)^2} = O(\frac{\log n}{n^2})$. Therefore,

$$S_2\le O\left(\frac{\log n}{n^2}\right) \sum_{n/2 < k < n} \frac{1}{n-k}= O\left(\frac{\log n}{n^2}\right) \cdot O(\log n) = O\left( \frac{(\log n)^2}{n^2} \right).$$

Thus,

$$a_n \le \frac{1}{n^2} + \frac{c}{n} \left(O(1/n)+O\left( \frac{(\log n)^2}{n^2} \right)\right)=\boxed{O(1/n^2)}\subset O\left(\frac{\log n}{n^2}\right).$$

Iteration 3

To be rigorous, we should check that this form is "stable"; if we assume $O(1/n^2)$, we must get $O(1/n^2)$ back. So, we take that $a_n \le c/n^2$ for some constant $c>0$ and $n>0$. If we substitute this into the recurrence, we have

$$a_n \le \frac{1}{n^2} + \frac{c}{n} \sum_{1 \le k < n} \frac{1}{k^2(n-k)}.$$

We split the summation again into two parts. When $1 \le k \le n/2$ then $\frac{1}{n-k} \le \frac{2}{n}$, hence

$$S_1\le \frac{2}{n} \sum_{k=1}^\infty \frac{1}{k^2} = O(1/n).$$

The sum $\sum_{k=1}^\infty \frac{1}{k^2}=\zeta(2)$, where $\zeta$ is the Riemann zeta function.

When $n/2 < k < n$ then $\frac{1}{k^2} \le \frac{4}{n^2}$. Thus, $S_2\le\frac{4}{n^2} \sum \frac{1}{n-k} = O(\frac{\log n}{n^2})$. Therefore,

$$a_n \le \frac{1}{n^2} + \frac{c}{n} \cdot \left(O(1/n) +O\left(\frac{\log n}{n^2}\right)\right)= O(1/n^2).$$

Final Result

From $a_n=O(1/n^2)$ it follows that $n^2a_n=O(1)$.

Exercise 2.50 🌟

We can expect many hardships with the perturbation method. This and the next few exercises demonstrate different obstacles that we may encounter. Here, we must tune the initial growth rate after failing to bound the error rate with the initial guess.

Find the asymptotic growth of the solution to the “perturbed” Fibonacci recurrence

$$a_{n+1} = \left(1 + \frac{1}{n}\right)a_n + \left(1 - \frac{1}{n}\right)a_{n-1} \space\space\space\space\text{ for $n>0$}.$$

Notice that $n>0$, otherwise $a_2$ would be missing, since initial values are $a_0=0$ and $a_1=1$.

---

We can view the recurrence as

$$a_{n+1}=\underbrace{a_n + a_{n-1}}_{\text{Standard Fibonacci}} + \underbrace{\frac{1}{n}(a_n - a_{n-1})}_{\text{Perturbation Term}}.$$

The solution to a simpler recurrence $b_{n+1}=b_n+b_{n-1}$ for $n>0$ with $b_0=0$ and $b_1=1$ is $b_n=F_n =\Theta( \phi^n)$, where $\phi$ is the golden ratio.

Following the steps from the book, we need to compare the two recurrences by forming the ratio

$$\rho_n=\frac{a_n}{b_n}=\frac{a_n}{\Theta(\phi^n)}.$$

If we plug $\Theta(\phi^n)\rho_n$ into the original recurrence, we won’t be able to bound $\rho_n$. Consequently, the solution must grow faster. The book contains a hint as part of Exercise 2.53; let’s add an extra $n^\alpha$ multiplier and find the value of $\alpha$ such that $\rho_n=O(1)$. This gives

$$\rho_n\sim\frac{a_n}{n^\alpha\phi^n} \space\space\space\space \text{ for $n>1$},$$

with $\rho_1=1/\phi$. We have

$$\begin{align*} (n+1)^\alpha \phi^{n+1} \rho_{n+1} &= \left(1 + \frac{1}{n}\right) n^\alpha \phi^n \rho_n + \left(1 - \frac{1}{n}\right) (n-1)^\alpha \phi^{n-1} \rho_{n-1} \\[0.4cm] \phi^2 \frac{(n+1)^\alpha}{n^\alpha} \rho_{n+1} &= \phi \left(1 + \frac{1}{n}\right) \rho_n + \left(1 - \frac{1}{n}\right) \frac{(n-1)^\alpha}{n^\alpha} \rho_{n-1} \\[0.4cm] \phi^2 \left(1 + \frac{1}{n}\right)^\alpha \rho_{n+1} &= \phi \left(1 + \frac{1}{n}\right) \rho_n + \left(1 - \frac{1}{n}\right) \left(1 - \frac{1}{n}\right)^\alpha \rho_{n-1} \\[0.4cm] \phi^2 \left(1 + \frac{1}{n}\right)^\alpha \rho_{n+1} &\le \left[\phi \left(1 + \frac{1}{n}\right) + \left(1 - \frac{1}{n}\right) \left(1 - \frac{1}{n}\right)^\alpha \right] \rho_n && \text{(assume $\rho_n$ is non-decreasing)} \\[0.4cm] \phi^2 \left(1 + \frac{\alpha}{n}\right) \rho_{n+1} &\le \left[\phi \left(1 + \frac{1}{n}\right) + \left(1 - \frac{1}{n}\right) \left(1 - \frac{\alpha}{n}\right)\right] \rho_n && \text{(Taylor expansion $(1 + x)^\alpha \approx 1 + \alpha x$)} \\[0.4cm] \left(\phi^2 + \frac{\alpha \phi^2}{n}\right) \rho_{n+1} &\le \left[\phi + \frac{\phi}{n} + \left(1 - \frac{\alpha}{n} - \frac{1}{n} + O\left(\frac{1}{n^2}\right)\right)\right] \rho_n \\[0.4cm] \left(\phi^2 + \frac{\alpha \phi^2}{n}\right) \rho_{n+1} &\le \left[(\phi + 1) + \frac{\phi - 1 - \alpha}{n}\right] \rho_n && \text{(ignore $O(1/n^2$)}\\[0.4cm] \left(\phi^2 + \frac{\alpha \phi^2}{n}\right) \rho_{n+1} &\le \left[\phi^2 + \frac{\phi - 1 - \alpha}{n}\right] \rho_n. \end{align*}$$

To solve for $\alpha$ we can set $\alpha \phi^2 = \phi - 1 - \alpha$, which implies that

$$\alpha = \frac{\phi - 1}{\phi^2 + 1} = \frac{\phi - 1}{\phi + 2}.$$

Thus, the asymptotic growth of the solution is $a_n=O(n^\frac{\phi - 1}{\phi + 2} \phi^n)$.

Exercise 2.51 🌟

Often, we have to employ the perturbation method iteratively. This exercise illustrates the process.

The coefficient $n$ on $a_{n-1}$ suggests $a_n=\omega(n!)$. Let’s employ a change of variable $b_n=a_n/n!$ to find a solution to a simpler recurrence

$$\begin{align*} n! \cdot b_n &= n(n-1)!\cdot b_{n-1} + n^2 (n-2)! \cdot b_{n-2} \\ b_n &= b_{n-1} + \frac{n^2}{n(n-1)} b_{n-2} \\ &= b_{n-1} + \frac{n}{n-1} b_{n-2} \\ &= b_{n-1} + \left(1+\frac{1}{n-1}\right) b_{n-2} \end{align*}$$

As $n \to \infty$, $\frac{1}{n-1} \to 0$. Therefore, applying the perturbation method again, we end up with another simpler recurrence $c_n = c_{n-1} + c_{n-2}$ for $n>1$ with $c_0=0$ and $c_1=1$. Clearly, $c_n=F_n \sim \phi^n$, where $\phi$ is the golden ratio.

To account for the perturbation factor, we reuse the approach from the previous exercise. This gives

$$\rho_n\sim\frac{b_n}{n^\alpha\phi^n} \space\space\space\space \text{ for $n>1$},$$

with $\rho_1=1/\phi$. We have

$$\begin{align*} n^\alpha \phi^n \rho_n &= (n-1)^\alpha \phi^{n-1} \rho_{n-1} + \frac{n}{n-1} (n-2)^\alpha \phi^{n-2} \rho_{n-2} \\[0.4cm] \phi^2 \rho_n &= \left(1 - \frac{1}{n}\right)^\alpha \phi \rho_{n-1} + \frac{n}{n-1} \left(1 - \frac{2}{n}\right)^\alpha \rho_{n-2} \\[0.4cm] \phi^2 \rho_n &= \left(1 - \frac{\alpha}{n}\right) \phi \rho_{n-1} + \frac{n}{n-1} \left(1 - \frac{2\alpha}{n}\right) \rho_{n-2} && \text{(Taylor expansion $(1 + x)^\alpha \approx 1 + \alpha x$)} \\[0.4cm] \phi^2 \rho_n &\le \rho_{n-1} \left[\left(1 - \frac{\alpha}{n}\right) \phi + \frac{n}{n-1} \left(1 - \frac{2\alpha}{n}\right)\right] && \text{(assume $\rho_n$ is non-decreasing)} \\[0.4cm] \left(1 - \frac{1}{n}\right)\phi^2 \rho_n &\le \rho_{n-1} \left[\left(1 - \frac{1}{n}\right) \left(1 - \frac{\alpha}{n}\right) \phi + \left(1 - \frac{2\alpha}{n}\right)\right] \\[0.4cm] \left(\phi^2 - \frac{\phi^2}{n}\right) \rho_n &\le \rho_{n-1} \left[\phi \left(1 - \frac{1}{n} - \frac{\alpha}{n} + O\left(\frac{1}{n^2}\right)\right) + \left(1 - \frac{2\alpha}{n}\right)\right] \\[0.4cm] \left(\phi^2 - \frac{\phi^2}{n}\right) \rho_n &\le \rho_{n-1} \left[\phi \left(1 - \frac{1}{n} - \frac{\alpha}{n}\right) + \left(1 - \frac{2\alpha}{n}\right)\right] && \text{(ignore $O(1/n^2$)} \\[0.4cm] \left(\phi^2 - \frac{\phi^2}{n}\right) \rho_n &\le \rho_{n-1} \left[\phi + 1 - \frac{1}{n}(\phi + \phi \alpha + 2\alpha)\right] \\[0.4cm] \left(\phi^2 - \frac{\phi^2}{n}\right) \rho_n &\le \rho_{n-1} \left[\phi^2 - \frac{1}{n}(\phi + \phi \alpha + 2\alpha)\right]. \end{align*}$$