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

def c(n):
    return (1 + 1 / n) * c(n - 1) + 2 if n > 1 else 2

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*}$$

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.HashMap;
import java.util.Map;

public class CalculateValues {
    private static final int MAXN = 5000;
    private static final int STEP = 1000;

    public static void main(String[] args) {
        System.out.printf("%8s | %8s | %8s| %8s%n", "n", "standard", "med-3", "radix");
        System.out.println("----------------------------------------");
        for (int n = STEP; n <= MAXN; n += STEP) {
            int m = n - STEP + 1;
            int standard = standardQuickSort(m, n);
            int med3 = medianOfThreeQuickSort(m, n);
            int radix = radixExchangeSort(m, n);
            System.out.printf("%8d | %8d | %8d| %8d%n", n, standard, med3, radix);
        }
    }

    private static final double[] c1 = new double[MAXN + 1];

    private static int standardQuickSort(int minN, int maxN) {
        for (int n = minN; n <= maxN; n++)
            c1[n] = (n + 1) * c1[n - 1] / n + 2;
        return (int) c1[maxN];
    }

    private static final double[] c2 = new double[MAXN + 1];

    private static int medianOfThreeQuickSort(int minN, int maxN) {
        for (int n = Integer.max(minN, 3); n <= maxN; n++) {
            long d = (long) n * (n - 1) * (n - 2) / 6;
            c2[n] = n + 1;
            for (int k = 1; k <= n; k++)
                c2[n] += ((k - 1D) * (n - k) / d) * (c2[k - 1] + c2[n - k]);
        }
        return (int) c2[maxN];
    }

    private static final MathContext MC = MathContext.DECIMAL128;
    private static final Map<Long, BigInteger> cache = new HashMap<>();

    private static BigInteger nChooseK(int n, int k) {
        if (k < 0 || k > n) return BigInteger.ZERO;
        if (k == 0 || k == n) return BigInteger.ONE;
        if (k > n - k) k = n - k;
        long key = (((long) n) << 32) | (k & 0xffffffffL);
        BigInteger cached = cache.get(key);
        if (cached != null) return cached;
        BigInteger value = nChooseK(n - 1, k - 1).add(nChooseK(n - 1, k));
        cache.put(key, value);
        return value;
    }

    private static final BigDecimal[] c3 = new BigDecimal[MAXN + 1];

    private static int radixExchangeSort(int minN, int maxN) {
        for (int i = minN; i <= maxN; i++) c3[i] = BigDecimal.ZERO;

        for (int n = Integer.max(minN, 2); n <= maxN; n++) {
            for (int k = 2; k < n; k++) {
                BigDecimal binom = new BigDecimal(nChooseK(n, k));
                c3[n] = c3[n].add(binom.multiply(c3[k], MC), MC);
            }
            BigDecimal f = new BigDecimal(BigInteger.ONE.shiftLeft(n - 1));
            BigDecimal d = f.subtract(BigDecimal.ONE);
            BigDecimal term1 = BigDecimal.valueOf(n).multiply(f).divide(d, MC);
            BigDecimal term2 = c3[n].divide(d, MC);
            c3[n] = term1.add(term2, MC);
        }
        return c3[maxN].toBigInteger().intValue();
    }
}

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

Table 2.5 - Estimated average number of comparisons of quicksort variants

       n | standard |    med-3|    radix
----------------------------------------
    1000 |    12985 |    10027|    11297
    2000 |    28729 |    22420|    24596
    3000 |    45519 |    35709|    38649
    4000 |    62988 |    49581|    53193
    5000 |    80963 |    63885|    68101

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:

var('c0 c1 c2 alpha beta gamma')

eq1 = 0 == c0 + c1 + c2
eq2 = 0 == c0 * alpha + c1 * beta + c2 * gamma
eq3 = 1 == c0 * alpha^2 + c1 * beta^2 + c2 * gamma^2

sol = solve([eq1, eq2, eq3], [c0, c1, c2], solution_dict=True)
c0 = sol[0][c0]
show(c0.factor())

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.

a = b = 0; c = 1
n = 20
for _ in range(n - 2):
    a, b, c = b, c, a + b + c

a = 1.839286755
c0 = 1 / (3 * a**2 - 2 * a - 1)
print(f"{c} ~ {c0 * a**20}")

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

def is_valid_monomial(s, t, n):
    """
    This function checks if a given monomial, represented by two
    lists s and t, appears in the expansion of a[n], for n > 1.
    The function returns True if the monomial is valid, otherwise False.
    """
    assert(n > 1)

    # Insert sentinel values to avoid index errors.
    s.append(0)
    t.append(0)

    i = len(s) - 1
    j = len(t) - 1

    s.sort()
    t.sort()

    while n > 1:
        # Simple reduction rules:
        # 1. If the largest element is in s,
        #    then the sub-monomial comes from the previous iteration.
        # 2. If the largest element is in t,
        #    then the sub-monomial comes from two iterations back.
        # The premise is that the current monomial is valid
        # iff built from a valid sub-monomial. Easily provable by induction.
        if s[i] > t[j]:
            if s[i] != n - 1:
                return False
            i -= 1
            n -= 1
        else:
            if t[j] != n - 2:
                return False
            j -= 1
            n -= 2

    return n > 0 and i == j == 0

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$.

from math import sqrt
import numpy as np
import matplotlib.pyplot as plt

def a(a0):
    x = a0
    for _ in range(6):
        x = 2 * x * sqrt(1 - x * x)
    return x

def plot_a(num_points=1000, save_path="a_plot.png",
           label_fontsize=18, tick_fontsize=14, title_fontsize=20):
    xs = np.linspace(0.0, 1.0, num_points)
    ys = [a(float(x)) for x in xs]

    plt.figure(figsize=(8, 5))
    plt.plot(xs, ys, marker='o', linestyle='-', markersize=4)
    plt.grid(True)
    plt.xlabel(r"$a_0$", fontsize=label_fontsize)
    plt.ylabel(r"$a_6$", fontsize=label_fontsize)
    plt.title(r"Values of $a_6$ for $a_0$ on the interval $[0,1]$",
              fontsize=title_fontsize)
    plt.xticks(fontsize=tick_fontsize)
    plt.yticks(fontsize=tick_fontsize)
    plt.tight_layout()
    plt.savefig(save_path, dpi=150)
    plt.show()

if __name__ == "__main__":
    plot_a()

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$.

a = 1
for n in range(1, 11):
    a = 2/(n+a)
    print(f"a({n})={a}, â({n})={2/n}")

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

a(1)=1.0, â(1)=2.0
a(2)=0.6666666666666666, â(2)=1.0
a(3)=0.5454545454545455, â(3)=0.6666666666666666
a(4)=0.43999999999999995, â(4)=0.5
a(5)=0.36764705882352944, â(5)=0.4
a(6)=0.3140877598152425, â(6)=0.3333333333333333
a(7)=0.2734449005367856, â(7)=0.2857142857142857
a(8)=0.2417372719639722, â(8)=0.25
a(9)=0.2164095278998315, â(9)=0.2222222222222222
a(10)=0.19576349152197078, â(10)=0.2

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.

a = 1
for n in range(1, 11):
    a = 2/(n+a)
    print(f"a({n})={a}, â({n})={2*(n-1)/(n*n-n+2)}")

The results are better aligned as $n$ increases.

a(1)=1.0, â(1)=0.0
a(2)=0.6666666666666666, â(2)=0.5
a(3)=0.5454545454545455, â(3)=0.5
a(4)=0.43999999999999995, â(4)=0.42857142857142855
a(5)=0.36764705882352944, â(5)=0.36363636363636365
a(6)=0.3140877598152425, â(6)=0.3125
a(7)=0.2734449005367856, â(7)=0.2727272727272727
a(8)=0.2417372719639722, â(8)=0.2413793103448276
a(9)=0.2164095278998315, â(9)=0.21621621621621623
a(10)=0.19576349152197078, â(10)=0.1956521739130435

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.

a(2)=0.6666666666666666, â(2)=1.0
a(3)=0.5454545454545455, â(3)=0.5714285714285714
a(4)=0.43999999999999995, â(4)=0.4444444444444444
a(5)=0.36764705882352944, â(5)=0.3684210526315789
a(6)=0.3140877598152425, â(6)=0.3142857142857143
a(7)=0.2734449005367856, â(7)=0.27350427350427353
a(8)=0.2417372719639722, â(8)=0.24175824175824176
a(9)=0.2164095278998315, â(9)=0.21641791044776118
a(10)=0.19576349152197078, â(10)=0.19576719576719576

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*}$$

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

$$\begin{align*} \phi^2 - \phi &= \alpha(\phi + 2) \\ 1 &= \alpha(\phi + 2) \\ &\therefore \boxed{\alpha = \frac{1}{\phi + 2}}. \end{align*}$$

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

Exercise 2.52

The paper Some Doubly Exponential Sequences by Aho and Sloane elaborates the solution for a more general recurrence. It’s also instructive to read about how variants of the generic form appear in practical problems.

The recurrence from the book, where $g_n=1$, generates a sequence A003095 shifted by one (the first element should be skipped, since in our case $a_0=1$). Using the relationship to the constant $c=1.225902443528748\dots$, our $\alpha$ corresponds to $c^2$ (due to the previously mentioned index shift). The digits of $\alpha$ are listed in A077496.

Exercise 2.53

This is a small variation of Exercise 2.50 with $\alpha = -\frac{\phi^2}{\phi^2 + 1}=-\frac{\phi+1}{\phi + 2}$.

The perturbation factor is $(1 - 1/n)<1$, hence, the sequence is asymptotically slightly less than the standard Fibonacci sequence. The polynomial correction must be decay, which explains why $\alpha$ is negative. Of course, we could have forgotten about the polynomial factor, since the upper bound is valid even without it. But it’s assumed that the O-notation expresses a tight upper bound.

Exercise 2.54

In the best case, we always choose the smaller subinterval of size $\lfloor(N-1)/2\rfloor$ (see the proof of Theorem 2.3 in the book). Therefore, the recurrence is

$$B_N=B_{\lfloor(N-1)/2\rfloor}+1 \space \space \space \space \text{ for $N >1$ with $B_1=1$}.$$

After one iteration, we get $B_N=B_{\lfloor(N-3)/4\rfloor}+2$ leveraging a useful property of floor and ceiling functions that $\lfloor\lfloor x\rfloor/2 \rfloor=\lfloor x/2 \rfloor$. At the end, we must have

$$\frac{N-(2^n-1)}{2^n} \ge 1 \implies n=\lfloor\lg(N+1)\rfloor-1.$$

The number of comparisons is $B_N=n+1=\lfloor\lg(N+1)\rfloor$ for $N \ge1$.

Exercise 2.55

We always choose the largest subinterval of size $\lceil N/3\rceil$. Therefore, the recurrence is

$$B_N=B_{\lceil N/3\rceil}+2 \space \space \space \space \text{ for $N >1$ with $B_1=1$ and $B_0=0$}.$$

The number of comparisons is $B_N\sim2\log_3 N$ for $N>1$. If we convert the formula of ternary search to use logarithm of base two, then we can see that the leading term is $2/\lg 3\approx 1.26 > 1$. Ternary search is less efficient than binary search in terms of comparisons. Even though it reduces the problem size faster (dividing by 3 instead of 2), the "cost" of doing so (2 comparisons instead of 1) is too high to be worth it.

Exercise 2.56

The solution is part of the course material about recurrences (slides 36-37) by RS.

Exercise 2.57

The recurrence (4) from the book may be regarded as a function $f:\N \to \N$, thus cannot have two closed-form solutions that map the same input to different outputs.

Exercise 1.5 contains an inductive proof for the RHS of an identity mentioned in this exercise. The LHS is the Theorem 2.4 from the book. Both are closed-form solutions to the same recurrence, so they must resolve to the same value for all $N>0$.

Exercise 2.58

Figure 2.5 in the book is wrong. $P_N<0.5N\lg N$ (just by looking entries of Table 2.3), hence $f_N=O(N)$ must be negative; the plot of $P_N-0.5N\lg N$ cannot be at the top. As a matter of fact, the top and bottom plots must be swapped. Furthermore, $P_{84}=252$ instead of 215. Finally, the cumulated number of zero bits must include zero itself, otherwise we cannot recreate the plots.

{# 1 bits in numbers less than $N$} – $(N \lg N)/2$

The function is specified as $T_N=P_N – (N \lg N)/2$, where

$$P_N=P_{\lceil N/2 \rceil}+P_{\lfloor N/2 \rfloor}+\lfloor N/2 \rfloor \space \space \space \space \text{ for $N>1$ with $P_1=0$ (see the book).}$$

---

{# 0 bits in numbers less than $N$} – $(N \lg N)/2$

The function is specified as $T_N=Z_N – (N \lg N)/2$, where

$$Z_N = Z_{\lceil N/2 \rceil} + Z_{\lfloor N/2 \rfloor} + \lceil N/2 \rceil-1 \space \space \space \space \text{ for $N>1$ with $Z_1=1$ (we also count zero).}$$

---

{# bits in numbers less than $N$} – $N \lg N$

The function is specified as $T_N=S_N – N \lg N$, where $S_N$ is given in Exercise 2.56.

Exercise 2.59

The recurrences for $R_N$ are (for $N>1$ with $R_1=R_0=0$)

$$\begin{align*} R_N &= R_{N-2^{\lfloor \lg N \rfloor}}+R_{2^{\lfloor \lg N \rfloor}-1}+\lfloor \lg N \rfloor && \text{(considering the leftmost bit)} \\ &= R_{\lfloor N/2 \rfloor}+\lfloor N/2 \rfloor && \text{(considering the rightmost bit).} \end{align*}$$

Exercise 2.60 🌟

This and the next couple of exercises illustrate how seemingly smooth asymptotic bounds don’t reflect what actually happens under the hood, due to usage of floor and ceiling functions (see Table 2.4 in the book).

The Python 3 script below generates the required plot.

from functools import lru_cache
from math import floor, log2
import matplotlib.pyplot as plt

@lru_cache(maxsize=None)
def f(n):
    return f(n//2) + f((n + 1)//2) + floor(log2(n)) if n > 1 else 0

def plot(save_path="exercise_2_60.png", label_fontsize=18, tick_fontsize=14, title_fontsize=20):
    xs = list(range(1, 513))
    ys = [f(n) for n in xs]

    # Theoretical comparison curve (scaled to match roughly) 𝛩(N).
    zs = [2 * n for n in xs]

    plt.figure(figsize=(12, 9))
    plt.plot(xs, ys, label="$A_N$", linestyle='-', color='blue', linewidth=1)
    plt.plot(xs, zs, label="$\\Theta(N)$", color='red', linestyle='--', alpha=0.3)

    plt.grid(True)
    plt.legend(fontsize=16)
    plt.xlabel(r"$N$", fontsize=label_fontsize)
    plt.ylabel(r"$A_N$", fontsize=label_fontsize)
    plt.title(r"$A_N = A_{\lfloor N/2 \rfloor} + A_{\lceil N/2 \rceil} + \lfloor \lg N \rfloor$",
              fontsize=title_fontsize)
    plt.xticks(fontsize=tick_fontsize)
    plt.yticks(fontsize=tick_fontsize)
    plt.tight_layout()
    plt.savefig(save_path, dpi=150)
    plt.show()

if __name__ == "__main__":
    plot()

Apparently, the function is continuous and periodic. It runs slightly below the line $y=2N$.

Exercise 2.61

The script from the previous exercise needs to be tweaked to produce the desired plot.

This time the function is extremely "spiky." Large jumps occur just after powers of 2.

Exercise 2.62

The following Python 3 script creates the required plot and could be used to test out the variants, as mentioned in the book.

from functools import lru_cache
import matplotlib.pyplot as plt

@lru_cache(maxsize=None)
def c(n):
    return c((n + 1)//2) + c((n + 1)//2) + n if n > 1 else 0

@lru_cache(maxsize=None)
def d(n):
    return d((n + 1)//2) + d((n + 1)//2) + c(n) if n > 1 else 0

def plot(save_path="exercise_2_62.png", label_fontsize=18, tick_fontsize=14, title_fontsize=20):
    xs = list(range(1, 513))
    ys = [d(n) for n in xs]

    plt.figure(figsize=(12, 9))
    plt.plot(xs, ys, label="$D_N$", linestyle='-', color='blue', linewidth=1)

    plt.grid(True)
    plt.xlabel(r"$N$", fontsize=label_fontsize)
    plt.ylabel(r"$D_N$", fontsize=label_fontsize)
    plt.title(r"$D_N = D_{\lceil N/2 \rceil} + D_{\lceil N/2 \rceil} + C_N$, "
              r"where $C_N = C_{\lceil N/2 \rceil} + C_{\lceil N/2 \rceil} + N$",
              fontsize=title_fontsize)
    plt.xticks(fontsize=tick_fontsize)
    plt.yticks(fontsize=tick_fontsize)
    plt.tight_layout()
    plt.savefig(save_path, dpi=150)
    plt.show()

if __name__ == "__main__":
    plot()

We see a similar figure as in Exercise 2.61. If $N$ isn’t a power of 2, then many recursive calls happen on larger indices due to the usage of the ceil function. These effects accumulate and produce large jumps right after these border values. When only floors are used, jumps happen on transitioning to powers of 2. Balancing floors and ceilings in both recurrences completely smooths out the curve.

Exercise 2.63

The function wildly oscillates and is fractal. Let $m=\lg N$. Values of $g(N)$ for $N \in [2^m,2^{m+1})$ can be generated from previously computed values in the interval $[2^{m-1},2^m)$ by adding $2^m$ depending on parity of $N$. Therefore, every subsequent period is a scaled version of its predecessor.

Exercise 2.64

We’ll develop two equivalent recurrence relations, although they appear to be completely different. As the book hinted in Chapter 1, it’s often easier to derive the total amount $T_N$ and calculate the average as $T_N/N$; we do include zero in the range of numbers less than $N$.

Considering the Leftmost Bit

The constituent parts of the recursive formula for the cumulated number of leading 1s in numbers less than $N$.

Let’s focus on the leftmost column and define $m=\lfloor \lg N \rfloor$. There are $2^m$ zeros, so we should add $N-2^m$ 1s to our count. This is represented as (1) in the image. There are two major sections demarcated by a horizontal line between the last 0 and first 1 in the leftmost column. The upper region has $m+T_{2^m-1}$ 1s, where (2) denotes those $m$ 1s. The total number of 1s in the bottom section depends whether it contains the row (3). If it doesn’t include (3), then the count is simply zero. Otherwise, it is $T_{N-2^m}-T_{2^{m-1}}$. After combining all these ingredients into a single formula, we get

$$T_N=N-2^{\lfloor \lg N \rfloor}+\lfloor \lg N \rfloor+T_{2^{{\lfloor \lg N \rfloor}}-1}+\begin{cases} 0 &\text{if } N-2^{\lfloor \lg N \rfloor} < 2^{\lfloor \lg N \rfloor-1}, \\ T_{N-2^{\lfloor \lg N \rfloor}}-T_{2^{{\lfloor \lg N \rfloor}-1}} &\text{otherwise}. \end{cases}$$

The base cases are $T_1=T_0=0$.

Considering the Rightmost Bit

If we focus on the rightmost bit, we see that the range can be split onto numbers ending with 1 and those ending with 0. Suppose we count how many leading 1s are there in those two subintervals. What we’re only missing is the $\lfloor \lg N \rfloor$ 1s associated with the number $2^{\lfloor \lg N \rfloor}-1 \in [1,N)$. Thus, we need to add it to the total. Therefore, the recurrence becomes $T_N=T_{\lfloor N/2 \rfloor} + T_{\lceil N/2 \rceil} + \lfloor \lg N \rfloor$ for $N>1$ with $T_1=0$. Notice, that it’s exactly the one from Exercise 2.60.

For example, when $N = 2^n$, the average simplifies to $2 - \frac{n+2}{N}$, which tends to 2 as $N \to \infty$.

Exercise 2.65

A bitstring of length $N$ has the form $b_1b_2\dots b_N$, where each $b_i \in {0,1}$. The initial run of 1s ends at the first 0 (or continues to the end if all bits are 1). Let $X$ be a random variable denoting the length of the initial string of 1s in a random bitstring of length $N$. Its probability mass function is defined as

$$\Pr\{X=k\}=\begin{cases} \left(\cfrac{1}{2}\right)^k \cdot \cfrac{1}{2}=\left(\cfrac{1}{2}\right)^{k+1} &\text{if } 0 \le k<N, \\[0.5cm] \left(\cfrac{1}{2}\right)^N &\text{if } k=N. \end{cases}$$

The event $X=k$ for $0 \le k<N$ occurs if the first $k$ bits are 1 and the $(k+1)$-th bit is 0. The expected value is

$$\begin{align*} \mathbb{E}[X] &= \sum_{k=0}^N k \cdot \Pr\{X=k\}\\ &=\sum_{k=1}^N \Pr\{X\ge k\} && \text{($\Pr\{X=k\}=\Pr\{X\ge k\}-\Pr\{X\ge k+1\}$, so the sum telescopes)}\\ &=\sum_{k=1}^N 2^{-k} \\ &= 1 - \frac{1}{2^N}. \end{align*}$$

Exercise 2.66

Based on Exercise 2.65, we have that $\lim_{n \to \infty}\mu=\mathbb{E}[X]=1$.

The variance is given by

$$\text{Var}(X) = \mathbb{E}[X^2] - \mathbb{E}[X]^2.$$

We need to compute

$$\begin{align*} \mathbb{E}[X^2] &= \sum_{k=0}^{\infty} k^2 \cdot \Pr\{X = k\} \\ &= \sum_{k=0}^{\infty} \frac{k^2}{2^{k+1}} \\ &= \frac{1}{2} \cdot \frac{\frac{1}{2} \cdot \frac{3}{2}}{(1 - 1/2)^3} && \text{$\left(\sum_{k=0}^{\infty} k^2 x^k = \cfrac{x(1 + x)}{(1 - x)^3} \quad \text{for } |x|=1/2 < 1\right)$} \\ &= 3. \end{align*}$$

Thus, the variance is $3-1=2$.

This problem actually maps perfectly to the geometric distribution. If we let $Y$ be the total number of bits we examine until we see the first 0, $Y$ follows a geometric distribution with probability $p = 1/2$. Our random variable would be defined as $X=Y-1$. At any rate, both the mean and variance are given.

Exercise 2.67

The total number of carries made when a binary counter increments $N$ times, from $0$ to $N$, matches $R_N$, as defined in the book (see also Exercise 2.59).

Exercise 2.68

In both subproblems, we follow the steps from the proof of Theorem 2.5 outlined in the book.

For $\delta=0$ the exact representation of the solution is

$$a(x)=x^\gamma\left(1+\left(\frac{\alpha}{\beta^\gamma}\right)+\left(\frac{\alpha}{\beta^\gamma}\right)^2+\dots \left(\frac{\alpha}{\beta^\gamma}\right)^t\right) \text{, where }t=\lfloor \log_\beta x\rfloor.$$

If $\alpha<\beta^\gamma \implies \gamma > \log_\beta \alpha$ then the sum converges and

$$a(x) \sim x^\gamma \sum_{j \ge 0} \left(\frac{\alpha}{\beta^\gamma}\right)^j=\underbrace{\frac{\beta^\gamma}{\beta^\gamma-\alpha}}_{c_1}x^\gamma.$$

If $\alpha=\beta^\gamma \implies \gamma =\log_\beta \alpha$ then each of the terms in the sum is 1 and the solution is simply

$$a(x) \sim \underbrace{\frac{1}{\log \beta}}_{c_2}\cdot x^\gamma \log x.$$

---

For $\delta \neq0$ the exact representation of the solution is

$$a(x)=x^\gamma\left((\log x)^\delta+\left(\frac{\alpha}{\beta^\gamma}\right)\left(\log \frac{x}{\beta}\right)^\delta+\left(\frac{\alpha}{\beta^\gamma}\right)^2\left(\log \frac{x}{\beta^2}\right)^\delta+\dots \left(\frac{\alpha}{\beta^\gamma}\right)^t\left(\log \frac{x}{\beta^t}\right)^\delta\right) \text{, where }t=\lfloor \log_\beta x\rfloor.$$

Note that

$$\begin{align*} \left(\log \frac{x}{\beta^k}\right)^\delta &= (\log x - k\log \beta)^\delta \\ &= (\log x)^\delta\left(1-\frac{k\log \beta}{\log x}\right)^\delta. \end{align*}$$

As $x \to \infty \implies \log x \to \infty$, so for fixed k

$$\left(1-\frac{k\log \beta}{\log x}\right)^\delta \to 1.$$

If $\alpha<\beta^\gamma \implies \gamma > \log_\beta \alpha$ then the contribution of terms where $k$ is close to $t$ is negligible and the sum converges. We have

$$a(x) \sim x^\gamma (\log x)^\delta\sum_{j \ge 0} \left(\frac{\alpha}{\beta^\gamma}\right)^j=\underbrace{\frac{\beta^\gamma}{\beta^\gamma-\alpha}}_{c_1}x^\gamma(\log x)^\delta.$$

If $\alpha=\beta^\gamma \implies \gamma =\log_\beta \alpha$ then

$$a(x) \sim x^\gamma \sum_{k=0}^{\log_\beta x} (\log x - k \log \beta)^\delta.$$

This sum can be approximated by an integral. Let $t$ be a continuous variable for $k$ and $u = \log x - t \log \beta$, so $du = -\log \beta \, dt$. This gives

$$a(x) \sim x^\gamma \frac{1}{\log \beta} \int_{0}^{\log x} u^\delta \, du \sim\underbrace{\frac{1}{\log \beta (\delta +1)}}_{c_2}x^\gamma(\log x)^{\delta+1}.$$

While the book states $c_1, c_2$ depend on $\alpha, \beta, \gamma$, the derivation shows $c_2$ also depends on $\delta$ due to the integration of the logarithmic term.

Exercise 2.69 🌟

This exercise reminds us that the asymptotic approximations given by the Master theorem differ in nature from exact solutions.

The recurrence falls under case 2 of the Master theorem. The exact solution takes the form

$$a_N = N \log_3 N + N \cdot P(N).$$

The function $P$ represents the fluctuations caused by the floor function $\lfloor N/3 \rfloor$. We have

$$P(N)=\frac{a_N}{N}-\log_3 N \space \space \space \space \text{ for $N>3$}.$$

The plot of the periodic part shows a fractal image, where jumps occur at values of $N=4 \cdot 3^k$ for $k>0$.

Exercise 2.70

Here is the Python script for trying out different configurations. Currently, it is setup to draw a variant where floors are replaced by ceils.

from functools import lru_cache
from math import log
import matplotlib.pyplot as plt

@lru_cache(maxsize=None)
def a(n):
    return 3 * a((n+1)//3) + n if n > 3 else 1

def plot(save_path="exercise_2_70.png", label_fontsize=18, tick_fontsize=14, title_fontsize=20):
    xs = list(range(1, 973))
    ys = [a(n) / n - log(n, 3) for n in xs]

    plt.figure(figsize=(12, 9))
    plt.plot(xs, ys, linestyle='-', color='blue', linewidth=1)

    plt.grid(True, which='both', linestyle='--', alpha=0.4)
    plt.xlabel(r"$N$", fontsize=label_fontsize)
    plt.ylabel(r"$\frac{a_N}{N} - \log_3 N$", fontsize=label_fontsize)
    plt.title(r"Periodic Part of $a_N = 3a_{\lceil N/3 \rceil} + N$",
              fontsize=title_fontsize)
    plt.xticks(fontsize=tick_fontsize)
    plt.yticks(fontsize=tick_fontsize)
    plt.tight_layout()
    plt.savefig(save_path, dpi=150)

    plt.show()

if __name__ == "__main__":
    plot()

This is the plot where 2 floors are replaced by ceils. Apparently, the jumps aren’t so steep as in Exercise 2.69.

Exercise 2.71 🌟

This exercise shows what happens when the function $f(x)$ grows exponentially fast.

The exact solution takes the form

$$\begin{align*} a(x) &= 2^x + \alpha 2^{x/\beta} + \alpha^2 2^{x/\beta^2} + \cdots + \alpha^t 2^{x/\beta^t} \\ &= \sum_{k=0}^t \alpha^k 2^{x/\beta^k} \\ &= 2^x\left(1 + \sum_{k=1}^t \alpha^k 2^{x \cdot \frac{1-\beta^k}{\beta^k}}\right) \text{, where }t=\lfloor \log_\beta x\rfloor. \end{align*}$$

Since $\beta>1$, we have $\frac{1-\beta^k}{\beta^k}<0$ for $k \ge 1$. The $2^{c \cdot x}$ term grows faster than any polynomial $\alpha^x$, hence $a^x/2^{c \cdot x} \to 0$ as $x \to \infty$, for any positive constant $c$.

Therefore, we can conclude that $a(x) = \Theta(2^x)$.

Exercise 2.72

There are many ways to give an asymptotic solution to the recurrence. One approach is to use the more general Akra-Bazzi method. Another one is to draw a recursion tree and discover patterns. There’s a tool called VisuAlgo to see recursive trees in action. It has lots of prebuilt recurrences, but it’s also possible to define a custom recurrence by selecting the Custom Code option from the drop-down list. The following snippet contains the definition for this exercise.

if (n <= 3) /* base case */
  return 1;
else /* recursive case */
  return f(3*n/4) + f(n/4) + n;

After entering a value for $N$ and pressing the Run button, the tool visualizes the whole tree. In general, the cost per level is $N$. The largest subproblem size decreases by a factor of 3/4 at each step, so the depth is $\sim \log_{4/3} N$. Therefore, the recurrence satisfies $a_N = \Theta(N \lg N)$.

If we want to be rigorous, then we must prove the hypothesis just formulated, for example, using induction on $N$.

---

We can even determine the leading coefficient by substituting $a_N \sim cN\log N$ into the recurrence (bootstrapping). This gives $a_N \sim \frac{N \log N}{\log 4 - \frac{3}{4} \log 3}$.

Exercise 2.73 🌟

This exercise shows how the interplay between the Master theorem (or Theorem 2.6 with a more specific function) and bootstrapping may reveal the leading coefficient.

The same remark applies here as in the previous exercise. By drawing a recursion tree, we can see that the depth is $\sim \lg N$ and the amount of work at each step drops by a factor of 3/4. In other words, the cost at level $k$ is $(3/4)^kN$. After summing up costs, we can conclude that the recurrence satisfies $a_N=\Theta(N)$.

---

We can make one step further and discover the leading coefficient. Assuming that $a_N \sim cN$, we can substitute $a_N$ into the recurrence and find that $a_N \sim 4N$.

Exercise 2.74

We must prove that the solution to the recurrence

$$a_n = a_{f(n)}+a_{g(n)}+a_{h(n)}+1 \space\space\space\space \text{ for $n>t$ with $a_n=1$ for $n \le t$},$$

with the constraint that $f(n) + g(n) + h(n) = n$, is $a_n=\Theta(n)$. We assume that all index functions are positive. We’ll prove the lower and upper bounds separately.

Suppose $a_n=O(n) \implies a_n \le c_2n-d_2$ for some positive constants $c_2$ and $d_2$ as well as sufficiently large $n$. Substituting this hypothesis into our recurrence, we get

$$\begin{align*} a_n &= a_{f(n)}+a_{g(n)}+a_{h(n)}+1 \\ &\le c_2(f(n)+g(n)+h(n))-3d_2+1 && \text{(by the inductive hypothesis)} \\ &= c_2n-d_2-(2d_2-1) \\ &\le c_2n-d_2 && \text{(if we make $2d_2-1 \ge 0 \implies d_2 \ge 1/2$)} \\ &\therefore a_n=O(n) \space\space\space\space \checkmark \end{align*}$$

The lower bound is even easier. Suppose $a_n=\Omega(n) \implies a_n \ge c_1n$ for some positive constant $c_1$ and sufficiently large $n$. Substituting this hypothesis into our recurrence, we get

$$\begin{align*} a_n &= a_{f(n)}+a_{g(n)}+a_{h(n)}+1 \\ &\ge c_1(f(n)+g(n)+h(n))+1 && \text{(by the inductive hypothesis)} \\ &= c_1n+1 \\ &\ge c_1n \\ &\therefore a_n=\Omega(n) \space\space\space\space \checkmark \end{align*}$$

Since both bounds are the same, we can conclude that $a_n=\Theta(n)$. Observe that we can choose suitable values for our constants to satisfy the base cases, too. For example, $c_1=1/t, c_2=3/2$ and $d_2=1/2$ configuration works.

Exercise 2.75

The recurrence $a_n= a_{f(n)}+a_{g(n)}+1$ for $n>t$ with $a_n=1$ for $n \le t$, where $f(n)+g(n)=n-h(n)$, describes the number of nodes in a recursion tree of a divide-and-conquer algorithm with a "coarsening effect" (subproblems of size $\le t$ are handled as base cases). We assume that all index functions are positive:

• The $+1$ represents the current node.

• The problem is split into two subproblems of size $f(n)$ and $g(n)$.

We are also given the condition $f(n) + g(n) = n - h(n)$. This equation tells us how the "size" of the problem decreases at each step. At any internal node with size $n$, the combined size of its children is $n-h(n)$. This means that at every step of the recursion, a size drops by $h(n)$. Since the recursion starts with $n$, and ends when reaching the "leaves" (blocks of size $\le t$), the sum of reductions at every internal node must be equal to the initial size $n$ minus the residuals at the leaves. This can be expressed as

$$n \approx \sum_{\text{all internal nodes } i} h(\text{size}_i) \approx \sum_{i=1}^{a_n/2} h(\text{size}_i).$$

Let’s assume that $h(n)=O(1) \implies h(n) <=c$ for some positive constant $c$ and sufficiently large $n$. Substituting this into the above equation, we get

$$n \approx \sum_{i=1}^{a_n/2} c \approx ca_n \implies a_n/n >0 \text{ as $n \to \infty$}.$$

Roughly speaking $n \approx a_n \cdot h_{\text{average}}$, which implies

$$\frac{a_n}{n} \approx \frac{1}{h_{\text{average}}} \to 0.$$

So, we just need to ensure that $h(n)=\omega(1)$ somehow grows unboundedly as $n \to \infty$.