Chapter 2

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. Otherwise, both correctly return $F_{20}=6765$.

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=0$) 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: $\sim 2N\ln N \approx1.386N\lg N$

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

• Radix exchange sort: $\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$. The reason that $U_n=F_{n-1}$ is 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 Exercise 2.6. 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$. Chapter 3 of the book shows how to attain a closed-form solution for a sum of Fibonacci numbers.

Exercise 2.8 🌟

For $f$ linear, we can 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$} .$

This is a generalization of the previous two exercises.

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

Exercise 2.9

This immediately reduces to a product

$$\begin{align*} a_n &= \prod_{k=1}^n \frac{k}{k+2} && \text{(for $n>0$)}\\ &=\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 && \text{(for $n>0$)}\\ &= 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

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} && \text{(for $n>1$)}\\ &= \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

If we multiply both sides by $(n+1)$ and iterate, we get

$$\begin{align*} (n+1)a_n &= na_{n-1}+(n+1) && \text{(for $n>0$)}\\ &=(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 of writing down the solution to $a_n=x_na_{n-1}+y_n$ for $n>t$ in terms of the $x$’s, the $y$’s and the initial value $a_t$.

Following through the same steps as in the proof of Theorem 2.1, and stopping at $a_t$, we get

$$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, try shifting 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 have

$$\begin{align*} a_n&=\frac{n+1}{n}a_{n-1}+2 && \text{(for $n>0$)}\\ &=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).

We need to solve the recurrence

$$na_n=(n-4)a_{n-1}+12nH_n \qquad \text{for $n>4$ and $a_n=0$ for all $n \le 4$}.$$

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

We can now 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*}$$

After substituting back $s_{j+1}$ into the main recurrence, we have

$$\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 for all constituent factors.

The correct problem statement is published on the book’s website. After simplifying the expression for $A_N$, we 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} \text{ for $N>6$}.$$

Exercise 2.18

From the signed error term $b_n = a_n - \alpha$, we have $a_{n-1} = b_{n-1} + \alpha$. We can substitute it back into the main recurrence

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

Therefore, we have

$$\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 have

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

Notice that $\alpha = \frac{1}{1+\alpha} \implies \frac{\alpha}{1 + \alpha} = \alpha^2$, so we can derive an approximate formula

$$\begin{align*} b_n &\approx -\alpha^2 b_{n-1} \\ &= (-\alpha^2)^n b_0 && \text{(iterating)}\\ &=(-\alpha^2)^n(a_0-\alpha). \end{align*}$$

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. Therefore, we have reached 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$ 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)$. Observe, that $\{a_n\}_{n>0}$ is strictly decreasing, since the term $1-a_{n-1}<1$ in every iteration. Thus, $a_n<a_{n-1}$ because $a_{n-1}$ is multiplied by a factor less than one.

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

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

$$a_n \approx 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 \approx 1-2x$ for small $x$. Thus,

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

Following the hint from the book, let’s flip the above equation to get

$$\begin{align*} b_n^2 &\approx \frac{b_{n-1}^2}{ \left(1 - \frac{a_{n-1}^2}{3}\right)} \\ &\approx b_{n-1}^2 \left(1 + \frac{a_{n-1}^2}{3}\right) && \text{($\frac{1}{1-x} \approx 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 🌟

This exercise states sufficient criteria corresponding to the three cases above for local convergence (when $a_0$ is sufficiently close to α) and quantifies the speed of convergence in terms of f′(α) and f″(α).

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 \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 for particular solutions of inhomogeneous linear recurrences. The text covers many recurrence types that occur in practical applications.

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 initial conditions, we can fundamentally change 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.

We need to solve the recurrence $a_n=a_{n-1}-a_{n-2}$ for $n>1$ with $a_0=0$ and $a_1=1$. 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

We have to solve the recurrence $2a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$ for $n>2$ with $a_0=0$, $a_1=1$ and $a_2=2$. 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 $c_0$

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

In the derivation, we’ve used the expression for the sum of Fibonacci numbers. 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$}.$$

Therefore,

$$a_n=2^{\frac{2}{3}\left(1-\left(-\frac{1}{2}\right)^n\right)}\space\space\space\space\text{ 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

We need to solve the register allocation recurrence $a_n=a_{n-1}^2-2$ for $n>0$ and various initial values.

Case 1: $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.

Case 2: $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.

Case 3: $a_0=\frac{3}{2}$

This case is fundamentally different compared to the previous two. 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$ will therefore fluctuate 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. We need to find all values of the parameters α, β and γ such that $a_n=\alpha a_{n-1}^2+\beta a_{n-1}+\gamma$ reduces to $b_n=b_{n-1}^2-2$ by a linear transformation $b_n = f(α, β, γ)a_n + g(α, β, γ)$.

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

Analysis of $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 $a_n = a_{n-1}^2 + 1$ does not 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.

Our starting recurrence is a generalized "continued fraction" representation

$$a_n=\frac{\alpha a_{n-1}+\beta}{\gamma a_{n-1}+\delta} \space\space\space\space \text{ for $n>0$}.$$

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

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

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.

We need to express the recurrence

$$a_n = \frac{1}{s_n + t_n a_{n-1}} \space \space \space \space \text{ for $n>0$ with $a_0=1$},$$

where $s_n$ and $t_n$ are arbitrary sequences, as the ratio of two successive terms in a sequence defined by a linear recurrence.

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}} && \text{(for $n>0$)} \\ \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$}.$$

We need to 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 basic form of the bootstrapping method.

We need to solve the recurrence $a_n=\cfrac{2}{n+a_{n-1}}$ for $n>0$ with $a_0=1$.

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=\frac{2(n-1)}{n^2-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=\frac{2 (n^2 - 3 n + 4)}{(n-1)(n^2 - 2 n + 4)} \space\space\space\space \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. 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}} \\ &\approx \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 \approx k$ and $N+1 \approx N$. If we substitute these changes into our original expression and replace the summation with an integral, we have

$$C_N \approx 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} \\ &= 12 \alpha N \ln N \left( \frac{1}{3} - \frac{1}{4} \right) \\ &= 12 \alpha N \ln N \left( \frac{1}{12} \right) \\ &= \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 recurrence is

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

We separated the $k=0$ term, which is $\frac{a_0}{n(n-0)} = \frac{1}{n^2}$.

Iteration 1: From $O(1/n)$ to $O(\frac{\log n}{n^2})$

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] &\approx \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: From $O(\frac{\log n}{n^2})$ to $O(1/n^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. 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}$ is strictly decreasing. The maximum value is 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)}=O\left(\frac{\log n}{n^2}\right).$$

Iteration 3: From $O(1/n^2)$ to $O(1/n^2)$

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.

The recurrence is

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

Thus, the asymptotic growth of the solution is $a_n=O(n^\frac{\phi - 1}{\phi^2 + 1} \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 from OEIS 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 from OEIS.

Exercise 2.53

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

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. Furthermore, $P_{84}=252$ instead of 215. As a matter of fact, the top and bottom plots must be swapped. Finally, the cumulative 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$

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

Let’s substitute $P_N=T_N + (N \lg N)/2$ into the above recurrence relation

$$\begin{align*} T_N + \frac{N \lg N}{2} &= \left(T_{\lceil N/2 \rceil} + \frac{\lceil N/2 \rceil \lg \lceil N/2 \rceil}{2} \right) + \left( T_{\lfloor N/2 \rfloor} + \frac{\lfloor N/2 \rfloor \lg \lfloor N/2 \rfloor}{2} \right) + \lfloor N/2 \rfloor \\[0.4cm] &\therefore \boxed{T_N= T_{\lceil N/2 \rceil} + T_{\lfloor N/2 \rfloor} + \Delta_N}, \end{align*}$$

where the "disturbance" term $\Delta_N$ is

$$\begin{align*} \Delta_N &= \lfloor N/2 \rfloor + \frac{1}{2} \left( \lceil N/2 \rceil \lg \lceil N/2 \rceil + \lfloor N/2 \rfloor \lg \lfloor N/2 \rfloor - N \lg N \right) \\[0.4cm] &= \lfloor N/2 \rfloor + \frac{1}{2} \left( \lceil N/2 \rceil (\lg \lceil N/2 \rceil - \lg N) + \lfloor N/2 \rfloor (\lg \lfloor N/2 \rfloor - \lg N) \right) && \text{($-N \lg N = -\lceil N/2 \rceil \lg N - \lfloor N/2 \rfloor \lg N$)} \\[0.4cm] &= \lfloor N/2 \rfloor + \frac{1}{2} \left( \lceil N/2 \rceil \lg \left(\frac{\lceil N/2 \rceil}{N}\right) + \lfloor N/2 \rfloor \lg \left(\frac{\lfloor N/2 \rfloor}{N}\right) \right) \\[0.6cm] &= \begin{cases} 0 &\text{if $N$ is even} \\[0.2cm] \frac{1}{2} \left( \bigg\lceil \frac{N}{2} \bigg\rceil \lg \left( \frac{2\lceil N/2 \rceil}{N} \right) + \bigg\lfloor \frac{N}{2} \bigg\rfloor \lg \left( \frac{2\lfloor N/2 \rfloor}{N} \right) - 1 \right) &\text{if $N$ is odd.} \end{cases} \end{align*}$$

The final simplification reuses ideas from Exercise 1.5 together with an identity $\lg(M/N) = \lg(2 \cdot M/N) - 1$.

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

Without repeating the previous derivation, we’ll just dump the final results for this and the next subproblem. The starting point is $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).}$$

$T_N= T_{\lceil N/2 \rceil} + T_{\lfloor N/2 \rfloor} + \Delta_N$, where $\Delta_N$ is

$$\Delta_N=\begin{cases} -1 &\text{if $N$ is even} \\[0.2cm] \frac{1}{2} \left( \bigg\lceil \frac{N}{2} \bigg\rceil \lg \left( \frac{2\lceil N/2 \rceil}{N} \right) + \bigg\lfloor \frac{N}{2} \bigg\rfloor \lg \left( \frac{2\lfloor N/2 \rfloor}{N} \right) -1 \right) &\text{if $N$ is odd.} \end{cases}$$

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

$T_N= T_{\lceil N/2 \rceil} + T_{\lfloor N/2 \rfloor} + \Delta_N$, where $T_1=1$ and $\Delta_N$ is (sum of the previous formulae)

$$\Delta_N= \begin{cases} -1 &\text{if $N$ is even} \\[0.2cm] \bigg\lceil \frac{N}{2} \bigg\rceil \lg \left( \frac{2\lceil N/2 \rceil}{N}\right) + \bigg\lfloor \frac{N}{2} \bigg\rfloor \lg \left( \frac{2\lfloor N/2 \rfloor}{N} \right)-1 &\text{if $N$ is odd.} \end{cases}$$

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 floors and ceilings (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 a little 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 periodic. 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 cumulative 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 $N$ is a power of two, then $T_N=R_N$ due to symmetry. Otherwise, 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$.

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.

$\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 x^\gamma \log_\beta x\sim\underbrace{\frac{1}{\log \beta}}_{c_2}\cdot x^\gamma \log x.$$

$\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}{(\delta +1)\log \beta}}_{c_2}x^\gamma(\log x)^{\sigma+1}.$$

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

Exercise 2.69

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 ceilings. Apparently, the jumps aren’t so steep as in Exercise 2.69.

Exercise 2.71

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 constant by substituting $a_N \sim CN\log N$ into the recurrence. This gives $a_N \sim \frac{N \log N}{\log 4 - \frac{3}{4} \log 3}$.

Exercise 2.73

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 approximately equal to the initial size $n$ (minus the small residuals at the leaves). This can be expressed as

$$n \sim \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 \sim \sum_{i=1}^{a_n/2} c \approx ca_n \implies a_n/n >0 \text{ as $n \to \infty$}.$$

We must have $h(n)=\omega(1)$. 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)$ somehow grows unboundedly as $n \to \infty$.