Chapter 3

Exercise 3.1

In all subproblems, $\{a_k\}_{k \ge m}$ denotes a sequence $a_m,a_{m+1},\dots$; for example, $\{k^3\}_{k \ge 2}$ starts with 8 (without leading zeros).

Sequence $\{2^{k+1}\}_{k \ge 0}$

We can represent $\{2^{k+1}\}_{k \ge 0}$ as $2\{2^k\}_{k \ge 0}$, which is 2x an elementary OGF from Table 3.1 with $c=2.$ Thus, $\boxed{2/(1-2z)=\sum_{k \ge 0}2^{k+1}z^k}$. Observe, that we can attain the same result by left shifting the elementary OGF $1/(1-2z)$ instead of first pulling out a constant factor 2.

Sequence $\{k2^{k+1}\}_{k \ge 0}$

We can represent $\{k2^{k+1}\}_{k \ge 0}$ as $2\{k2^k\}_{k \ge 0}$, which is a scaled version of an elementary OGF from Table 3.1. Thus, $\boxed{4z/(1-2z)^2=\sum_{k \ge 0}k2^{k+1}z^k}$.

Sequence $\{kH_k\}_{k \ge 1}$

Let $A(z)=\sum_{k \ge 0} k(H_k-1)z^k$ and $B(z)=\sum_{k \ge 0} kz^k$, so that our sequence is their left shifted sum (both summands are elementary OGFs from Table 3.1). We have

$$\begin{align*} C(z) &= \frac{A(z)+B(z)}{z} \\ &= \boxed{\frac{1}{(1-z)^2}\left(\ln \frac{1}{1-z}+1\right) =\sum_{k \ge 0}(k+1)H_{k+1}z^k}. \end{align*}$$

Sequence $\{k^3\}_{k \ge 2}$

Notice that $k^3=6\binom{k}{3}+6\binom{k}{2}+k$, so that our sequence is doubly left shifted sum of the corresponding elementary OGFs from Table 3.1. We have

$$\begin{align*} A(z)&=\frac{\cfrac{\cfrac{6z^3}{(1-z)^4}+\cfrac{6z^2}{(1-z)^3}+\cfrac{z}{(1-z)^2}}{z}-1}{z} \\[0.2cm] &= \frac{\cfrac{6z^2}{(1-z)^4}+\cfrac{6z}{(1-z)^3}+\cfrac{1}{(1-z)^2}-1}{z} \\[0.3cm] &= \frac{6z}{(1-z)^4}+\frac{6}{(1-z)^3}+\frac{1}{z(1-z)^2}-\frac{1}{z} \\[0.4cm] &=\boxed{ \frac{8 - 5z + 4z^2 - z^3}{(1-z)^4}=\sum_{k \ge 0}(k+2)^3z^k}. \end{align*}$$

Exercise 3.2

The idea behind each subproblem is to find the root OGF from Table 3.1 and then see what operations have been performed on it from Table 3.2.

$[z^N]$ for $\frac{1}{(1-3z)^4}$

This is a scaled elementary OGF from Table 3.1 with $M=3$, so

$$\boxed{[z^N]\frac{1}{(1-3z)^4}=\frac{3^N}{6}(N+1)(N+2)(N+3)}.$$

$[z^N]$ for $(1-z)^2\ln\frac{1}{(1-z)}$

The difference operation is applied twice in succession on the elementary OGF. We have to be careful to avoid a division by zero error. For this reason, the first three terms are enumerated separately. We have

$$\boxed{[z^N](1-z)^2\ln\frac{1}{(1-z)} = \begin{cases} 0 & \text{if } N=0, \\ 1 & \text{if } N=1, \\ -3/2 & \text{if } N=2, \\ \cfrac{2}{N(N-1)(N-2)} & \text{if } N \ge 3. \end{cases}}$$

$[z^N]$ for $\frac{1}{(1-2z^2)^2}$

The starting point is the elementary OGF $\frac{1}{1-z^2}=\sum_{N \ge 0}z^{2N}$. It is scaled by $\lambda=\sqrt 2$ to get $\frac{1}{1-2z^2}$. Finally, it is an elementary OGF from Table 3.1 with $M=1$, so

$$\boxed{[z^N]\frac{1}{(1-2z^2)^2} = \begin{cases} \left(\frac{N}{2} + 1\right) 2^{N/2} & \text{if } N \text{ is even,} \\ 0 & \text{if } N \text{ is odd}. \end{cases}}$$

Exercise 3.3

$$\begin{align*} \frac{1}{(1-z)}\ln\frac{1}{(1-z)}&=\sum_{N \ge 1}H_Nz^N \\ \frac{\ln\cfrac{1}{(1-z)}+1}{(1-z)^2}&=\sum_{N \ge 1}NH_Nz^{N-1} && \text{(differentiating)} \\ \frac{z\left(\ln\cfrac{1}{(1-z)}+1\right)}{(1-z)^2}&=\sum_{N \ge 1}NH_Nz^N && \text{(right shifting)} \\ \frac{z}{(1-z)^2}\ln\cfrac{1}{(1-z)}&=\sum_{N \ge 1}N(H_N-1)z^N && \text{(subtracting $z/(1-z)^2=\sum_{N \ge 1}Nz^N$)} \\ \frac{z}{(1-z)^2}\ln\cfrac{1}{(1-z)}&=\sum_{N \ge 0}N(H_N-1)z^N && \text{(altering index for $N$)}. \end{align*}$$

The last step wasn’t really needed, since any "missing" term has a coefficient of zero.

Exercise 3.4

The solution is available as part of the course material on the book’s website (see slide 13).

Exercise 3.5 🌟

This exercise demonstrates the advantages of representing an entire sequence using a single mathematical construct, such as a generating function. By manipulating generating functions, we can transform sequences and derive new identities through factoring. Each factorization corresponds to the same sequence, providing multiple perspectives for describing its terms. The preceding exercise has already illustrated this methodology in practice.

We need to prove a general identity satisfied by the harmonic numbers and binomial coefficients by factoring the initial OGF in different ways. Let’s start with

$$\underbrace{\frac{z^M}{(1-z)^{M+1}}}_{A(z)} \cdot \underbrace{\ln \frac{1}{1-z}}_{B(z)}.$$

Both components are elementary OGFs from Table 3.1. We have by definition

$$[z^N](A(z)B(z)) = \sum_{k=M}^{N-1} \binom{k}{M} \frac{1}{N-k}.$$

Looking at the initial OGF, we see that it is

$$\underbrace{\frac{1}{(1-z)^{M+1}}}_{C(z)} \cdot \underbrace{\ln \frac{1}{1-z}}_{D(z)}$$

right shifted $M$ times, or from an opposite direction, the latter is a result of left shifting the original one the same number of times. Therefore, $[z^N](A(z)B(z)) =[z^{N-M}](C(z)D(z))$. The book Concrete Mathematics: A Foundation for Computer Science (2nd ed.) contains an identity (7.43)

$$C(z)D(z)=\sum_{N \ge 0} (H_{M+N}-H_M)\binom{M+N}{N}z^N.$$

Therefore,

$$\boxed{\sum_{M \le k < N} \binom{k}{M} \frac{1}{N-k}=\binom{N}{M}(H_N-H_M)}.$$

The form of the generating function in this exercise is associated with hyperharmonic numbers.

Exercise 3.6

We are given the sequence

$$\left\{\sum_{0<k<n} \frac{1}{k(n-k)}\right\}_{n>1},$$

and we need to find its OGF. We presume the same interpretation of the above definition as in Exercise 3.1. It’s a doubly left shifted self-convolution of an elementary OGF $\ln \frac{1}{1-z}$.

$$A(z)=\frac{\left(\ln \cfrac{1}{1-z}\right)^2}{z^2}.$$

Exercise 3.7

We need to find the OGF for $\{H_k/k\}_{k \ge 1}$. Assume the same interpretation of this definition as in Exercise 3.1. A recipe for crafting the required OGF is as follows:

1. Start with the elementary OGF for the harmonic numbers.

2. Left shift it.

3. Apply the index divide (integration) operation.

4. Left shift again.

Despite being simple at first blush, the third step requires some advanced knowledge from calculus. The first two steps are

$$\begin{align*} \frac{1}{(1-z)}\ln\frac{1}{(1-z)}&=\sum_{N \ge 1}H_Nz^N \\ \frac{1}{z} \cdot \frac{1}{(1-z)}\ln\frac{1}{(1-z)}&=\sum_{N \ge 0}H_{N+1}z^N && \text{(left shifting)}. \end{align*}$$

We can’t directly integrate the LHS, since we have an improper integral (isn’t defined at zero). Let’s break it up and compute the components individually. We get

$$\begin{align*} \int_0^z \frac{-\ln(1-z)}{z(1-z)} \, dz &= \int_0^z -\ln(1-z) \left( \frac{1}{z} + \frac{1}{1-z} \right) \, dz \\[0.4cm] &= \underbrace{\int_0^z \frac{-\ln(1-z)}{z} \, dz}_{Dilogarithm function} - \int_0^z \frac{\ln(1-z)}{1-z} \, dz \\[0.8cm] &= Li_2(z) + \frac{1}{2} \ln^2(1-z). \end{align*}$$

Wikipedia has more information on the dilogarithm function. For the second integral, we can use WolframAlpha.

$$\begin{align*} &Li_2(z) + \frac{1}{2} \ln^2(1-z) = \sum_{N \ge 0} \frac{H_{N+1}}{N+1}z^{N+1} \\ &\boxed{\frac{Li_2(z) + \frac{1}{2} \ln^2(1-z)}{z} = \sum_{N \ge 0} \frac{H_{N+1}}{N+1}z^N} && \text{(left shifting)}. \end{align*}$$

Exercise 3.8

Let’s tackle first the common OGF $A(z)=\ln^2 \frac{1}{1-z}$ that appears in both subtasks. As usual, there are many equivalent expressions for $[z^N]$. Let’s reuse the results from Exercise 3.6 and Exercise 3.7.

$$[z^N]A(z)=\sum_{0<k<N} \frac{1}{k(N-k)}=\frac{2H_{N-1}}{N} \space\space\space\space \text{ for $N>1$}.$$

For $N \le 1$ the coefficients are zero. Observe that our $A(z)$ differs from the one from Exercise 3.6, in a sense, that it represents a sequence with two leading zeros.

$[z^N]$ for $\frac{1}{1-z}\ln^2 \frac{1}{1-z}$

We apply the partial sum operation on $A(z)$ to get $B(z)=A(z)/(1-z)$. For pedagogical reasons, we show here another derivation of the identity stated above for $A(z)$ (see step 3). We have

$$\begin{align*} [z^N]B(z)&=\sum_{1<i\le N}\sum_{0<j<i} \frac{1}{j(i-j)} \\[0.5cm] &= \sum_{1<i\le N} \frac{1}{i}\sum_{0<j<i} \left(\frac{1}{j}+\frac{1}{i-j}\right) \qquad \text{$\left(\frac{1}{j(i-j)}=\frac{1}{i}\left(\frac{1}{j}+\frac{1}{i-j}\right)\right)$} \\[0.6cm] &= \sum_{1<i\le N} \frac{2H_{i-1}}{i} \\ &= 2 \sum_{1<i\le N} \frac{H_i - \cfrac{1}{i}}{i} \\[0.5cm] &= 2 \sum_{i=1}^{N} \frac{H_i}{i} - 2 \sum_{i=1}^{N} \frac{1}{i^2} \qquad \text{(set $i$ to start at 1 without influencing the sum)} \\[0.5cm] &=2 \left( \frac{1}{2} (H_N^2 + H_N^{(2)}) \right) - 2 H_N^{(2)} \qquad \text{(by identity (6.71))} \\[0.5cm] &\therefore \boxed{[z^N]\frac{1}{1-z}\ln^2 \frac{1}{1-z}=[z^N]\left(\ln \frac{1}{1-z}\right)\left(\frac{1}{1-z}\ln \frac{1}{1-z}\right) \implies \sum_{k=1}^{N-1} \frac{H_{N-k}}{k} = H_N^2 - H_N^{(2)}}. \end{align*}$$

The previous derivation uses the identity (6.71) from the book Concrete Mathematics: A Foundation for Computer Science (2nd ed.).

$[z^N]$ for $\ln^3 \frac{1}{1-z}$

We convolve $A(z)$ with $\ln \frac{1}{1-z}$ to get $B(z)=\ln \frac{1}{1-z}A(z)$. We have

$$\begin{align*} [z^N]B(z)&=2 \sum_{k=1}^{N-1} \frac{H_{N-k-1}}{k(N-k)} \\ &= \frac{2}{N} \left( \underbrace{\sum_{k=1}^{N-1} \frac{H_{N-k-1}}{k}}_{S_1} + \underbrace{\sum_{k=1}^{N-1} \frac{H_{N-k-1}}{N-k}}_{S_2} \right). \end{align*}$$

Evaluation of $S_1$

$$\begin{align*} S_1 &= \sum_{k=1}^{N-1} \frac{H_{N-k-1}}{k} \\ &= \sum_{k=1}^{N-1} \frac{H_{N-k}}{k} - \sum_{k=1}^{N-1} \frac{1}{k(N-k)} \\ &= (H_N^2 - H_N^{(2)}) - \frac{2}{N} H_{N-1} && \text{$\left(\sum_{k=1}^{N-1} \frac{H_{N-k}}{k} = H_N^2 - H_N^{(2)}\right)$} \\ &= \left(H_N^2-H_{N-1}^{(2)}- \frac{1}{N^2}\right) - \frac{2}{N} H_{N-1} \\ &= \left(H_N-\frac{1}{N}\right)\left(H_N+\frac{1}{N}\right) -H_{N-1}^{(2)} - \frac{2}{N} H_{N-1} \\ &= H_{N-1}\left(H_{N-1}+\frac{2}{N}\right) -H_{N-1}^{(2)} - \frac{2}{N} H_{N-1} \\ &= H_{N-1}^2 - H_{N-1}^{(2)}. \end{align*}$$

Evaluation of $S_2$

$$\begin{align*} S_2 &= \sum_{k=1}^{N-1} \frac{H_{k-1}}{k} && \text{(reindexing)} \\ &= \sum_{k=1}^{N-1} \frac{H_k - \frac{1}{k}}{k} \\ &= \sum_{k=1}^{N-1} \frac{H_k}{k} - \sum_{k=1}^{N-1} \frac{1}{k^2} \\ &= \frac{1}{2} \left( H_{N-1}^2 - H_{N-1}^{(2)} \right). \end{align*}$$

Final Result

Substituting our partial sums into the expression for $[z^N]$ we have

$$\begin{align*} [z^N]B(z) &= \frac{2}{N} (S_1 + S_2) \\ &= \frac{2}{N} \left( \left[ H_{N-1}^2 - H_{N-1}^{(2)} \right] + \frac{1}{2} \left[ H_{N-1}^2 - H_{N-1}^{(2)} \right] \right) \\ &\therefore \boxed{[z^N]\ln^3 \frac{1}{1-z} = \frac{3}{N} \left( H_{N-1}^2 - H_{N-1}^{(2)} \right)} && \text{for $N>1$}. \end{align*}$$

For $N \le 1$ the coefficients are zeros.

Exercise 3.9

In all subproblems, $\{a_k\}_{k \ge m}$ denotes a sequence $a_m,a_{m+1},\dots$; for example, $\{k^3\}_{k \ge 2}$ starts with 8 (without leading zeros).

Sequence $\{2^{k+1}\}_{k \ge 0}$

We can represent $\{2^{k+1}\}_{k \ge 0}$ as $2\{2^k\}_{k \ge 0}$, which is 2x an elementary EGF from Table 3.3 with $c=2.$ Thus, $\boxed{2e^{2z}=\sum_{k \ge 0}2^{k+1}\frac{z^k}{k!}}$. Observe, that we can attain the same result by left shifting the elementary EGF $e^{2z}$ instead of first pulling out a constant factor 2.

Sequence $\{k2^{k+1}\}_{k \ge 0}$

We can represent $\{k2^{k+1}\}_{k \ge 0}$ as $2\{k2^k\}_{k \ge 0}$. For the scaled sequence, the starting point is $e^{2z}$. Next, we need to perform an index multiply operation. To get $ka_k$ instead of $ka_{k-1}$, we must again multiply by 2, since $a_k=2a_{k-1}$ for $k>1$.. Thus, $\boxed{4ze^{2z}=\sum_{k \ge 0}k2^{k+1}\frac{z^k}{k!}}$.

Sequence $\{k^3\}_{k \ge 2}$

Notice that $k^3=6\binom{k}{3}+6\binom{k}{2}+k$, so that our sequence is a doubly left shifted sum of the corresponding elementary EGFs from Table 3.3. We have

$$\begin{align*} A(z)&=((6/6)z^3e^z+(6/2)z^2e^z+ze^z)'' \\ &=((z^3+3z^2+z)e^z)'' \\ &=((z^3+6z^2+7z+1)e^z)' \\ &\therefore \boxed{(z^3+9z^2+19z+8)e^z=\sum_{k \ge 0}(k+2)^3\frac{z^k}{k!}}. \end{align*}$$

Exercise 3.10

The sequence $1,3,5,7,\dots$ can be described as $\{2k+1\}_{k \ge 0}$. This is basically a sum of elementary EGFs from Table 3.3, so $(1+2z)e^z$ is the matching EGF.

The sequence $0,2,4,6,\dots$ can be described as $\{2k\}_{k \ge 0}$. This is 2x an elementary EGF from Table 3.3, so $2ze^z$ is the matching EGF.

Exercise 3.11

The coefficients for the first two EGFs can be directly read out by looking at the corresponding OGFs and multiply their coefficients by $N!$. Nonetheless, we derive them here independently.

$N![z^N]$ for $A(z)=\frac{1}{1-z}\ln \frac{1}{1-z}$

If we treat $A(z)$ as an OGF, then the same EGF is its labelled counterpart. This immediatelly gives $N![z^N]A(z)=N!H_N$.

$N![z^N]$ for $A(z)=\ln^2 \frac{1}{1-z}$

This is a self-convolution of a right-shifted elementary EGF from Table 3.3.

$$\begin{align*} N![z^N]A(z)&=\sum_{1\le k<N}\binom{N}{k}(k-1)!(N-k-1)! \\ &=\sum_{1\le k<N}\frac{N!}{k(N-k)} \\ &=(N-1)!\sum_{1\le k<N}\left(\frac{1}{k}+\frac{1}{N-k}\right) \\ &=\boxed{2(N-1)!H_{N-1}} && \text{for $N>1$}. \end{align*}$$

For $N \le1$ the coefficients are zeros.

$N![z^N]$ for $A(z)=e^{z+z^2}$

Since $e^{z+z^2} = e^z \cdot e^{z^2}$, $A(z)$ is a binomial sum operation applied on

$$B(z)=e^{z^2}=\sum_{N\ge0}\cfrac{(2N)!}{N!}\cfrac{z^{2N}}{(2N)!}.$$

As in the case of the similar OGF from Table 3.1, odd entries are zero. Using the definition of a binomial sum operation from Table 3.4, we have

$$\begin{align*} N![z^N]A(z)&=\sum_{0\le 2k\le N}\binom{N}{2k}b_{2k} && \text{(sum over nonzero entries)} \\ &=\sum_{0\le k\le \lfloor N/2 \rfloor}\frac{N!}{(N-2k)!(2k)!} \cdot \frac{(2k)!}{k!} \\ &= \boxed{\sum_{0\le k\le \lfloor N/2 \rfloor}\frac{N!}{(N-2k)!k!}}. \end{align*}$$

Exercise 3.12

We need to show that

$$N! [z^N] e^z \int_0^z \frac{1-e^{-t}}{t} dt = H_N.$$

Let’s follow the hint from the book. We start by differentiating (left shifting) the EGF for harmonic numbers

$$H'(z) = \sum_{N \ge 0} H_{N+1} \frac{z^N}{N!}.$$

We can setup the required differential equation by substituting the recurrence relation $H_{N+1} = H_N + \frac{1}{N+1}$ into the sum. We have

$$\begin{align*} H'(z) &= \sum_{N \ge 0} \left( H_N + \frac{1}{N+1} \right) \frac{z^N}{N!} \\ &= \underbrace{\sum_{N \ge 0} H_N \frac{z^N}{N!}}_{H(z)} + \sum_{N \ge 0} \frac{1}{N+1} \frac{z^N}{N!} \\ &= H(z) + \sum_{N \ge 0} \frac{z^N}{(N+1)!} \\ &= H(z) + \frac{e^z-1}{z}. \end{align*}$$

To prove the statement from the book, we just need to follow the steps for solving a linear first-order differential equation with variable coefficients. As a side note, since $H_0=0$ the constant of integration is zero. Therefore,

$$H(z) = e^z \int_0^z \frac{1 - e^{-t}}{t} \, dt.$$

$H(z)=\sum H_N \frac{z^N}{N!} \implies N! [z^N]H(z)=H_N$.

Exercise 3.13

By definition $A(z)=\sum_{k\ge 0}a_k\cfrac{z^k}{k!}$. We also know that

$$N![z^N]B(z)=\sum_{0 \le k \le N} N! \frac{a_k}{k!}=\sum_{0 \le k \le N} \binom{N}{k}a_k(N-k)!,$$

where $B(z)$ is the unknown EGF. The last summation suggests that it’s a binomial convolution of $A(z)$ and $1/(1-z)$. Hence,

$$B(z)=\frac{A(z)}{1-z}.$$

Exercise 3.14 🌟

This exercise introduces the Laplace transform for converting from the EGF for a sequence to the OGF for the same sequence.

By definition $A(z)=\sum_{k\ge 0}a_k\cfrac{z^k}{k!}$. We must prove that

$$\int_0^\infty A(zt) e^{-t} \, dt=\sum_{k\ge 0} a_k z^k,$$

provided the integral exists. The proof revolves around computing the definite integral. We have

$$\begin{align*} \int_0^\infty A(zt) e^{-t} \, dt &= \int_0^\infty \left( \sum_{k \ge 0} a_k t^k\frac{ z^k}{k!} \right) e^{-t} \, dt \\ &= \sum_{k \ge 0} a_k\frac{ z^k}{k!} \underbrace{\int_0^\infty t^k e^{-t} \, dt}_{\text{$\Gamma(k+1) = k!$}} && \text{(assuming convergence to flip $\sum$ and $\int$)} \\ &= \sum_{k \ge 0} a_k\frac{ z^k}{k!} \cdot k! \\ &= \sum_{k \ge 0} a_k z^k. \end{align*}$$

The second line uses the notion of a gamma function. This establishes the desired identity.

Examples

If $A(z)=e^{cz}$ then

$$\begin{align*} \int_0^\infty A(zt) e^{-t} \, dt &= \int_0^\infty e^{-(1-cz)t} \, dt \\[0.4cm] &= \frac{1}{1-cz}. \end{align*}$$

Type the following snippet into Sage to evaluate the above integral:

var('t c z')
integrate(e**(-(1 - c*z) * t), (t, 0, oo), algorithm="sympy")

If $A(z) =ze^z$ then

$$\begin{align*} \int_0^\infty zte^{zt} e^{-t} \, dt &= \frac{z}{(1-z)^2}. \end{align*}$$

Type the following snippet into Sage to evaluate the above integral:

var('t z')
integrate(e**(-t) * z*t * e**(z*t), (t, 0, oo), algorithm="sympy")

Exercise 3.15

We need to multiply the recurrence by $z_n/n!$ and sum on $n$ in the first step. Now, $F(z)=\sum_{k\ge0} F_k \frac{z^k}{k!}$, hence we get the following differential equation

$$\begin{align*} &F(z)=\int_0^z F(t)\,dt + \int_0^z \left(\int_0^z F(t)\, dt\right) \, dt +z\\ &F(z)''=F(z)'+F(z), \end{align*}$$

with initial conditions $F(0)=F_0=0$ and $F'(0)=F_1=1$. For the sake of variety. let’s solve it using WolframAlpha. After issuing the command y'' - y' - y = 0, y(0) = 0, y'(0) = 1 we get

$$F(z)=\frac{1}{\sqrt 5}(e^{\phi z}-e^{\hat\phi z}).$$

Exercise 3.16 🌟

This exercise elaborates the methodology of applying generating functions to solve linear recurrences with constant coefficients.

We describe the process in detail for the first example. The extra summand, which makes a recurrence valid for all $n$, is the Kronecker delta function.

$$\begin{align*} a_n &= -a_{n-1} + 6a_{n-2} && \text{ for $n > 1$ with $a_0 = 0$ and $a_1 = 1$} \\ \hline \\ a_n &= -a_{n-1} + 6a_{n-2} + \delta_{n1} && \text{1. Make it valid for all $n$.} \\ A(z) &= -zA(z)+6z^2A(z)+z && \text{2. Multiply by $z^n$ and sum on $n$.} \\ &= \frac{z}{1+z-6z^2} && \text{3. Solve.} \\ &= \frac{z}{(1-2z)(1+3z)} && \text{4. Simplify.} \\ &= \frac{1}{5}\left(\frac{1}{1-2z}-\frac{1}{1+3z}\right) \\ &\therefore \boxed{a_n= \frac{1}{5}2^n-\frac{1}{5}(-3)^n} && \text{5. Expand.} \end{align*}$$

Performing a partial fractions expansion is easy in WolframAlpha. For example, issue Apart[z/(1 + z - 6z^2)] to simplify the polynomial expression in the 4th step (see above).

We use EGF for the next recurrence to demonstrate how it unfolds and to avoid technical difficulties in implementing partial fractions expansion due to unwieldy roots. Solving a homogeneous third-order linear ordinary differential equation with constant coefficients is essentially the same as solving the corresponding recurrence via roots of the characteristic polynomial. The resulting EGF is easily mapped to a closed-form solution (see the previous two exercises).

$$\begin{align*} a_n &= 11a_{n-2} - 6a_{n-3} \space\space\space\space \text{ for $n > 2$ with $a_0 = 0$ and $a_2 = a_1 = 1$} \\ \hline \\ A'''(z) &= 11A'(z) - 6A(z) \space\space\space\space \text{with $A(0) = 0, A'(0) = 1, A''(0) = 1$} \\ &\text{...find the roots $r_1,r_2,r_3$ of the characteristic equation $z^3-11z+6=0$...} \\ A(z) &= c_0e^{r_1 z} + c_1 e^{r_2 z} + c_2 e^{r_3 z} \\ &\text{...solve for constants based on initial conditions...} \\ &=\frac{1}{4} e^{3z} + \frac{-17-\sqrt{17}}{136} e^{\left(\frac{-3+\sqrt{17}}{2}\right)z} + \frac{-17+\sqrt{17}}{136} e^{\left(\frac{-3-\sqrt{17}}{2}\right)z} \\ &\therefore \boxed{a_n = \frac{1}{4} \cdot 3^n + \frac{-17-\sqrt{17}}{136} \left(\frac{-3+\sqrt{17}}{2}\right)^n + \frac{-17+\sqrt{17}}{136} \left(\frac{-3-\sqrt{17}}{2}\right)^n}. \end{align*}$$

The next two examples have complex roots.

$$\begin{align*} a_n &= 3a_{n-1}-4a_{n-2} \space\space\space\space \text{ for $n > 1$ with $a_0 = 0$ and $a_1 = 1$} \\ \hline \\ a_n &= 3a_{n-1}-4a_{n-2} + \delta_{n1} \\ A(z) &= 3zA(z)-4z^2A(z)+z \\ &= \frac{z}{1-3z+4z^2} \\ &= \frac{i}{\sqrt 7}\left(\frac{1}{1-(3/2-i\sqrt 7/2)z}-\frac{1}{1-(3/2+i\sqrt 7/2)z}\right) \\ &\therefore \boxed{a_n= \frac{i}{\sqrt 7}\left(\left(\frac{3-i\sqrt 7}{2}\right)^n-\left(\frac{3+i\sqrt 7}{2}\right)^n\right)} . \end{align*}$$

Using the technique illustrated in Exercise 2.31, we can convert the above expression into trigonometric form. Thus, $\boxed{a_n = \cfrac{2^{n+1}}{\sqrt{7}} \sin\left(n \arccos\left(\frac{3}{4}\right)\right)}$.

$$\begin{align*} a_n &= a_{n-1}-a_{n-2} \space\space\space\space \text{ for $n > 1$ with $a_0 = 0$ and $a_1 = 1$} \\ \hline \\ a_n &= a_{n-1}-a_{n-2} + \delta_{n1} \\ A(z) &= zA(z)-z^2A(z)+z \\ &= \frac{z}{1-z+z^2} \\ &= \frac{i}{\sqrt 3}\left(\frac{1}{1-(1/2-i\sqrt 3/2)z}-\frac{1}{1-(1/2+i\sqrt 3/2)z}\right) \\ &\therefore \boxed{a_n= \frac{i}{\sqrt 3}\left(\left(\frac{1-i\sqrt 3}{2}\right)^n-\left(\frac{1+i\sqrt 3}{2}\right)^n\right)} \end{align*}$$

The trigonometric form is $\boxed{a_n = \cfrac{2}{\sqrt{3}} \sin\left(n \arccos\left(\frac{1}{2}\right)\right)= \cfrac{2}{\sqrt{3}} \sin\left(n \frac{\pi}{3}\right)}$.

Exercise 3.17

We need to solve the recurrence

$$a_n = 5a_{n-1}-8a_{n-2}+4a_{n-3}\space\space\space\space \text{ for $n > 2$ with $a_0 = 1$, $a_1 = 2$ and $a_2 = 4$}.$$

The book provides a solution for different initial conditions, but we can reuse some parts of it. More specifically,

$$\begin{align*} g(z) &= 1 –5z + 8z^2 – 4z^3 = (1 – z)(1 – 2z)^2 \\ f(z) &= 1 -3z+2z^2 =(1-z)(1-2z)\\ a(z) &= \frac{f(z)}{g(z)} = \frac{1}{1 – 2z}. \end{align*}$$

This is an elementary OGF from Table 3.1. We have $\boxed{a_n=2^n}$.

Exercise 3.18

$$\begin{align*} a_n &= 2a_{n-2}-a_{n-4}\space\space\space\space \text{ for $n>3$ with $a_0=a_1=0$ and $a_2=a_3=1$} \\ \hline \\ g(z) &= 1-2z^2+z^4=(1-z)^2(1+z)^2 \\ f(z) &= z^2+z^3=z^2(1+z) \\ a(z) &= \frac{z^2}{(1-z)^2(1+z)} = \frac{z}{(1-z)^2} \cdot \frac{z}{1+z}. \end{align*}$$

The resulting OGF is a convolution of basic OGFs. We have

$$\begin{align*} [z^N]\frac{z}{(1-z)^2} \cdot \frac{z}{1+z} &= \sum_{1 \le k <N}k(-1)^{N-k-1} \\ &= \frac{1}{4} (-1)^N (2N (-1)^N - (-1)^N + 1) \\ &= \begin{cases} \frac{N}{2} & \text{if } N \text{ is even}, \\ \frac{N-1}{2} & \text{if } N \text{ is odd}. \end{cases} \end{align*}$$

The above sum can be computed by entering Sum[k(-1)^(N-k-1),{k,1,N-1}] in WolframAlpha. It may be instructive to dissect the sum in detail, but this is the topic of other books, like, Concrete Mathematics: A Foundation for Computer Science (2nd ed.).

We can formulate a concise answer as

$$\boxed{a_n=\frac{n}{2} + \frac{(-1)^n - 1}{4}}.$$

Exercise 3.19 🌟

This exercise pinpoints an important fact about partial fractions expansion. Namely, sometimes it makes sense to work with higher degree polynomials. We wouldn’t gain anything by breaking up $(1+3z^2)$, since it is already a scaled elementary OGF from Table 3.1.

$$\begin{align*} a_n &= 6a_{n-1}-12a_{n-2}+18a_{n-3}-27a_{n-4} \space\space\space\space \text{ for $n>3$ with $a_0=0$ and $a_1=a_2=a_3=1$} \\ \hline \\ g(z) &= 1-6z+12z^2-18z^3+27z^4=(1-3z)^2(1+3z^2) \\ f(z) &= z-5z^2+7z^3 \\ a(z) &= \frac{z-5z^2+7z^3}{(1-3z)^2(1+3z^2)}=\frac{1}{72(1-3z)} + \frac{1}{36(1-3z)^2} + \frac{19z - 1}{24(1+3z^2)} \\ &= \frac{1}{72} \cdot \left(\frac{1}{1-3z}\right) + \frac{1}{z} \cdot \frac{1}{3 \cdot 36} \cdot \left(\frac{3z}{(1-3z)^2}\right) + z\cdot\frac{19}{24} \cdot \left(\frac{1 }{1-(i\sqrt 3 z)^2}\right) - \frac{1}{24} \cdot \left(\frac{1}{1-(i\sqrt 3 z)^2}\right). \end{align*}$$

Again, tool support is indispensable. The decomposition of $a(z)$ was done in WolframAlpha by issuing the Apart[(z - 5 z^2 + 7 z^3)/((1 - 3 z)^2 (1 + 3 z^2))] command.

The resulting OGF is a sum of scaled and/or shifted elementary OGFs. After simplifying terms, and reusing the analysis from the book about OGFs of the form $1/(1+z^2)$, we get

$$\begin{align*} a_n &= \dfrac{3^n(2n+3)}{72} + \dfrac{3^{n/2}}{24}\left(\dfrac{19}{\sqrt{3}} \cdot \dfrac{i^{n-1}+(-i)^{n-1}}{2}-\dfrac{i^n+(-i)^n}{2}\right) \\ &= \boxed{\dfrac{3^n(2n+3)}{72} + \dfrac{3^{n/2}}{24}\left(\dfrac{19}{\sqrt{3}}\sin\left(\dfrac{n\pi}{2}\right)-\cos\left(\dfrac{n\pi}{2}\right)\right)}. \end{align*}$$

Exercise 3.20

$$\begin{align*} a_n &= 3a_{n-1}-3a_{n-2}+a_{n-3} \space\space\space\space \text{ for $n>2$ with $a_0=a_1=0$ and $a_2=1$} \\ \hline \\ g(z) &= 1-3z+3z^2-z^3=(1-z)^3 \\ f(z) &= z^2 \\ a(z) &= \frac{z^2}{(1-z)^3} \\ &\therefore \boxed{a_n=\binom{n}{2}}. \end{align*}$$

$$\begin{align*} a_n &= 3a_{n-1}-3a_{n-2}+a_{n-3} \space\space\space\space \text{ for $n>2$ with $a_0=0$ and $a_2=a_1=1$} \\ \hline \\ g(z) &= 1-3z+3z^2-z^3=(1-z)^3 \\ f(z) &= z-2z^2 \\ a(z) &= \frac{z-2z^2}{(1-z)^3} \\ &= \frac{1}{z} \cdot \frac{z^2}{(1-z)^3} - 2\frac{z^2}{(1-z)^3} \\ &\therefore \boxed{a_n=\binom{n+1}{2}-2\binom{n}{2}=\frac{n(3-n)}{2}}. \end{align*}$$

Exercise 3.21 🌟

This exercise nicely demonstrates the power of generating functions. Imagine solving the given recurrence using "classical" methods.

Let $A(z)=\sum_{n\ge0} a_nz^n$ represent our sequence. We know that

$$[z^n]A(z)=\begin{cases} 0 &\text{if } n<t-1, \\ 1 &\text{if } n=t-1, \\ -\sum_{1\le k \le t} \binom{t}{k}(-1)^ka_{n-k} & \text{if $n \ge t$}. \end{cases}$$

Looking at the form of the coefficient for $n \ge t$, it’s definitely a convolution of some OGF $B(z)$ with $A(z).$ Therefore, we have the following functional equation

$$A(z)=z^{t-1}-B(z)A(z).$$

Observe the term $z^{t-1}$, which denotes the initial value $a_{t-1}=1$. The convolution only covers the case when $n \ge t$. The range of $k$ tells that the sequence represented with $B(z)$ has the following values:

$$0,\underbrace{-t,\binom{t}{2},\dots,(-1)^t}_{1 \le k \le t},0,\dots$$

By searching Table 3.1, it occurs that $B(z)=(1-z)^t-1$, since it is a scaled elementary OGF with a leading zero. Thus,

$$A(z)=\frac{z^{t-1}}{(1-z)^t} \implies \boxed{a_n=\binom{n}{t-1} \space\space\space\space \text{ for $n \ge 0$}}.$$

Exercise 3.22

Let $a(z)=\sum_{n \ge 1}a_nz^n$ with an implicit assumption that $a_0=0$.

$$\begin{align*} na_n &= (n-2)a_{n-1}+2 \space\space\space\space \text{ for $n>1$ with $a_1=1$} \\ \hline \\ \sum_{n \ge 2}na_nz^n &= \sum_{n \ge 2}(n-2)a_{n-1}z^n+2\sum_{n \ge 2}z^n \\ za'(z)-z &= \sum_{n \ge 2}na_{n-1}z^n-2\sum_{n \ge 2}a_{n-1}z^n+2\left(\frac{1}{1-z}-z-1\right) \\ za'(z)-z &= z(za(z))'-2za(z)+2\frac{z^2}{1-z} \\ a'(z)-1 &= a(z)+za'(z)-2a(z)+2\frac{z}{1-z} \\ (1-z)a'(z) &= -a(z)+\frac{1+z}{1-z}. \end{align*}$$

We obtain the solution to this differential equation by solving the corresponding homogeneous equation

$$\frac{\varrho'(z)}{\varrho(z)}=-\frac{1}{1-z},$$

to get an “integration factor” $\varrho(z)=1-z$. This gives

$$\begin{align*} \left(\frac{a(z)}{1-z}\right)' &= \frac{a'(z)(1-z)+a(z)}{(1-z)^2} \\ &= \frac{1+z}{(1-z)^3}. \end{align*}$$

Integrating (for example, by using WolframAlpha), we get the result

$$a(z)=\frac{z}{1-z} \implies \boxed{a_n=1 \space\space\space\space \text{ for $n>0$}}.$$

We have already encountered this recurrence in Exercise 2.11. This was another way to attain the same outcome.

Exercise 3.23

Let $a(z)=\sum_{n \ge 0}a_nz^n$. We assume that $t$ is a positive integer.

$$\begin{align*} na_n &= (n+t-1)a_{n-1} \space\space\space\space \text{ for $n>0$ with $a_0=1$} \\ \hline \\ \sum_{n \ge 1}na_nz^n &= \sum_{n \ge 1}(n+t-1)a_{n-1}z^n \\ za'(z) &= \sum_{n \ge 1}na_{n-1}z^n+(t-1)\sum_{n \ge 1}a_{n-1}z^n \\ za'(z) &= z(za(z))'+(t-1)za(z) \\ za'(z) &= z^2a'(z)+za(z)+(t-1)za(z) \\ a'(z) &= za'(z)+a(z)+(t-1)a(z) \\ a'(z) &= za'(z)+ta(z) \\ \frac{a'(z)}{a(z)} &= \frac{t}{1-z} \\ &\therefore a(z) = \frac{1}{(1-z)^t}=\frac{1}{z^{t-1}} \cdot \frac{z^{t-1}}{(1-z)^t}. \end{align*}$$

Thus, $a(z)$ is an elementary OGF, left shifted $t-1$ times. This gives

$$\boxed{a_n=\binom{n+t-1}{t-1} \space\space\space\space \text{ for $n \ge 0$}}.$$

Exercise 3.24

Fast forwarding the analysis from the book, our recurrence relationship corresponds to a differential equation on the generating function

$$a'(z)=\frac{2}{(1-z)^3}+t\frac{a(z)}{1-z}.$$

We obtain the solution to this differential equation by solving the corresponding homogeneous equation

$$\frac{\varrho'(z)}{\varrho(z)}=\frac{t}{1-z},$$

to get an “integration factor” $\varrho(z)=1/(1-z)^t$. This gives

$$\begin{align*} ((1-z)^ta(z))' &= (1-z)^ta'(z)-t(1-z)^{t-1}a(z) \\ &= (1-z)^t\left(a'(z)-t\frac{a(z)}{1-z}\right) \\ &= 2(1-z)^{t-3}. \end{align*}$$

Integrating (for example, by using WolframAlpha), we get the result (recall that $a(0)=a_0=0$)

$$a(z) = \frac{-2}{t-2} \cdot \frac{1}{(1-z)^2} + \frac{2}{t-2} \cdot \frac{1}{(1-z)^t}.$$

The first term is a left shifted elementary OGF, so it’s coefficient is proportional to $n$. The second term is $t-1$ times left shifted elementary OGF from Table 3.1, so behaves like $\binom{n+t-1}{t-1} \sim n^{t-1}$. We differentiate two cases:

1. If $t=2-\epsilon$, then $a_n=\Theta(n)=o(n\lg n)$.

2. If $t=2+\epsilon$, then $a_n=\Theta(n^{1+\epsilon})=\omega(n\lg n)$.

The threshold $t=2$ is a bifurcation point, where even a tiny disturbance entails an asymptotically different behavior.

Exercise 3.25

Expansion of $\sin(z)$

We have to find the derivatives of $\sin(z)$:

$$\begin{align*} \sin'(z) &= \cos(z) \\ \sin''(z) &= -\sin(z) \\ \sin'''(z) &= -\cos(z) \\ \sin^{(4)}(z) &= \sin(z). \end{align*}$$

Since $\sin^{(4)}(z) = \sin(z)$, this pattern repeats. We also know that $\sin(0)=0$ and $\cos(0)=1$. Thus, we get

$$\begin{align*} \sin(z) &= z-\frac{z^3}{3!}+\frac{z^5}{5!}-\frac{z^7}{7!} + \dots \\ &= \sum_{k \ge 0} \frac{(-1)^k}{(2k+1)!}z^{2k+1}. \end{align*}$$

Expansion of $2^z$

We already know the result for the exponential sequence. Since $2^z=e^{\ln 2^z}=e^{z\ln2}$, we have to substitute $z=z\ln 2$ in the formula from the book. We get

$$2^z=\sum_{k \ge 0} \frac{\ln^k 2}{k!}z^k.$$

Expansion of $ze^z$

We just need to multiply each term on the RHS of the expansion of $e^z$ with $z$. This gives

$$ze^z=\sum_{k \ge 1}\frac{z^k}{(k-1)!}.$$

Exercise 3.26 🌟

This exercise introduces the general Leibniz rule for computing the $n$th derivative of the product of two functions.

Let’s develop some intuition about the stated recurrence for coefficients. Tools are excellent in performing exploratory tasks like this. Issuing taylor series 1/(1-az-bz^2) in WolframAlpha gives us the terms of the expansion:

$$1 + a z + (a^2 + b)z^2 + (a^3 + 2 a b) z^3+ (a^4 + 3 a^2 b + b^2)z^4 + (a^5 + 4 a^3 b + 3 a b^2)z^5 + \dots$$

Let $c_n$ denote the $n$th coefficient. It seems to satisfy a second-order linear recurrence with constant coefficients

$$c_n=ac_{n-1}+bc_{n-2} \space\space\space\space \text{ for $n>1$ with $c_0=1$ and $c_1=a$.}$$

Now, we have to show that this holds for all $n>1$. Let $f(z) = (1 - az - bz^2)^{-1}$, so that

$$c_n = \frac{f^{(n)}(0)}{n!}.$$

We aim to establish relationship between the derivatives $f^{(n)}(0)$, $f^{(n-1)}(0)$ and $f^{(n-2)}(0)$. Let’s rewrite our original expression as

$$f(z)\underbrace{ (1 - az - bz^2)}_{g(z)}=1.$$

Notice that since $g(z)$ is a polynomial of degree 2, its derivatives vanish for $n>2$:

$$\begin{align*} g^{(0)}(z) &= 1 - az - bz^2 \\ g^{(1)}(z) &= -a - 2bz \\ g^{(2)}(z) &= -2b \\ g^{(n)}(z) &= 0 && \text{(for all $n \ge 3$)}. \end{align*}$$

Differentiating the equation $f(z)g(z) = 1$ $n$ times (where $n \ge 2$) gives:

$$\binom{n}{0} f^{(n)}(z) g^{(0)}(z) + \binom{n}{1} f^{(n-1)}(z) g^{(1)}(z) + \binom{n}{2} f^{(n-2)}(z) g^{(2)}(z) = 0.$$

Now we evaluate the differentiated equation above at $z=0$. This gives

$$\begin{align*} f^{(n)}(0) - a \cdot n \cdot f^{(n-1)}(0) - b \cdot n(n-1) \cdot f^{(n-2)}(0) &= 0 \\ \underbrace{\frac{f^{(n)}(0)}{n!}}_{c_n}- a \underbrace{\frac{f^{(n-1)}(0)}{(n-1)!}}_{c_{n-1}}-b \underbrace{\frac{f^{(n-2)}(0)}{(n-2)!}}_{c_{n-2}} &=0 && \text{(dividing by $n!$)} \end{align*}$$

This concludes the proof about the recurrence relation for coefficients.

Exercise 3.27

As in the previous exercise, we rely on the general Leibniz rule. Our starting point is

$$H(z)=\underbrace{\frac{1}{1-z}}_{f(z)} \cdot \underbrace{\ln\frac{1}{1-z}}_{g(z)}.$$

We have to find $c_n=H^{(n)}(0)/n!$. Notice that $g'(z)=f(z) \implies g^{(n-1)}(0)=f^{(n)}(0)$. We also know from the book that the $k$th derivative of $f(z)$ is $k!(1-z)^{-k-1}$. Consequently, $f^{(k)}(0)=k!$. Finally, $g^{(0)}(0)=g(0)=0$, so the summation in the Leibniz rule starts at index $k=1$. Combining all these facts, we have

$$\begin{align*} n! \cdot c_n &= \sum_{1 \le k \le n} \binom{n}{k} f^{(n-k)}(0)g^{(k)}(0) \\ &= \sum_{1 \le k \le n} \binom{n}{k} f^{(n-k)}(0)f^{(k-1)}(0) \\ &= \sum_{1 \le k \le n} \frac{n!}{k!(n-k)!} \cdot (n-k)!(k-1)! \\ &= \sum_{1 \le k \le n} \frac{n!}{k} \\ &\therefore \boxed{c_n = \sum_{1 \le k \le n} \frac{1}{k} = H_n}. \end{align*}$$

Exercise 3.28 🌟

This exercise introduces lots of novelties and derives an expansion of an important generating function.

We have to find an expression for

$$[z^n]\frac{1}{\sqrt {1-z}}\ln \frac{1}{1-z}.$$

Let’s follow the hint from the book and seek for the expansion of $(1-z)^{-\alpha}$. It’s given in the article on Wikipedia about the negative binomial series. We have

$$\begin{align*} [z^n](1-z)^{-\alpha} &= \binom{\alpha+n-1}{n} \\ &= \frac{\alpha(\alpha+1)\cdots(\alpha+n-1)}{n!} \\ &= \prod_{k=0}^{n-1} \frac{\alpha + k}{k+1}. \end{align*}$$

According to the hint, we should differentiate both sides with respect to $\alpha$. The LHS is

$$\begin{align*} \frac{d}{d\alpha} \left[(1-z)^{-\alpha}\right] &= \frac{d}{d\alpha} \left[e^{\ln (1-z)^{-\alpha}}\right] \\ &= \frac{d}{d\alpha} \left[e^{\alpha{\ln {(1-z)^{-1}}}}\right] \\ &= e^{\alpha{\ln (1-z)^{-1}}}\ln (1-z)^{-1} \\ &= (1-z)^{-\alpha} \ln \frac{1}{1-z}. \end{align*}$$

For the RHS, we’ll first convert the product into a sum using the natural logarithm. This gives

$$\begin{align*} \ln\binom{n+\alpha-1}{n} &= \sum_{k=0}^{n-1} \ln(\alpha + k) - \ln(k+1) \\ \frac{d}{d\alpha} \left[ \ln\binom{n+\alpha-1}{n} \right] &= \sum_{k=0}^{n-1} \frac{d}{d\alpha} [\ln(\alpha + k) ]-0 \\ \frac{1}{\binom{n+\alpha-1}{n}} \cdot \frac{d}{d\alpha} \left[\binom{n+\alpha-1}{n} \right] &= \sum_{k=0}^{n-1} \frac{1}{\alpha + k} \\ \frac{d}{d\alpha} \left[\binom{n+\alpha-1}{n} \right] &= \binom{n+\alpha-1}{n} \sum_{k=0}^{n-1} \frac{1}{\alpha + k} \\ &= \binom{n+\alpha-1}{n} \left(H_{n+\alpha-1}-H_{\alpha-1}\right). \end{align*}$$

Therefore, we have

$$\boxed{[z^n]\frac{1}{(1-z)^{\alpha}} \ln \frac{1}{1-z}=\binom{n+\alpha-1}{n} \left(H_{n+\alpha-1}-H_{\alpha-1}\right)}.$$

As a quick check, for $\alpha=2$ we indeed get the expansion of a left shifted OGF from Table 3.1.

In our case, $\alpha=1/2$. This gives

$$[z^n]\frac{1}{\sqrt{1-z}} \ln \frac{1}{1-z} = \binom{n-\frac{1}{2}}{n} \bigl(H_{n-\frac{1}{2}} - H_{-\frac{1}{2}}\bigr).$$

We can use the identity below, pertaining to the generalized binomial coefficients, to simplify the first term in the RHS. The book already shows the derivation of $\binom{-\frac{1}{2}}{n}$.

$$\binom{n-\frac{1}{2}}{n} = (-1)^n \binom{-\frac{1}{2}}{n}=\frac{1}{4^n} \binom{2n}{n}.$$

The digamma function provides a continuous interpolation of the harmonic numbers. As stated on Wikipedia about it’s relation to harmonic numbers, we have

$$\begin{align*} H_{n-\frac{1}{2}} &= \psi\!\left(n+\frac{1}{2}\right) + \gamma= - 2\ln 2 + 2H_{2n} - H_n \\ H_{-\frac{1}{2}} &= \psi\!\left(\frac{1}{2}\right) + \gamma=-2\ln 2. \end{align*}$$

After bundling together all components, we get

$$\boxed{[z^n]\frac{1}{\sqrt{1-z}} \ln \frac{1}{1-z} = \frac{1}{4^n} \binom{2n}{n} \bigl(2H_{2n} - H_n\bigr)}.$$

Exercise 3.29

We already have an expression for a generic parameter $\alpha$ (see the previous exercise). Thus,

$$\boxed{[z^n]\frac{1}{(1-z)^{t}} \ln \frac{1}{1-z}=\binom{n+t-1}{n} \left(H_{n+t-1}-H_{t-1}\right)}.$$

Exercise 3.30

$$[z^N]\frac{1}{\sqrt {1-4z}} \cdot \frac{1}{\sqrt {1-4z}}=[z^N]\frac{1}{1-4z}.$$

Both OGFs are elaborated in the book.

Exercise 3.31

The differential equation (3) corresponds to (1), which is the basic recurrence describing the number of comparisons used by quicksort. Multiplying (3) by $(1-z)^2$ is equivalent to differencing the coefficients twice in succession. We get

$$\begin{align*} \underbrace{NC_N-(N-1)C_{N-1}-((N-1)C_{N-1}-(N-2)C_{N-2})}_{[z^N](1-z)^2C'(z)}&= \underbrace{N(N+1)-(N-1)N-((N-1)N-(N-2)(N-1))}_{[z^N](1-z)^2\frac{2}{(1-z)^3}}\\ & \hspace{1cm}+\underbrace{2\sum_{1 \le k \le N} C_{k-1}-2\sum_{1 \le k \le N-1} C_{k-1}-\left(2\sum_{1 \le k \le N-1} C_{k-1}-2\sum_{1 \le k \le N-2} C_{k-1}\right)}_{[z^N](1-z)^2\frac{2C(z)}{(1-z)}} \\ NC_N-2(N-1)C_{N-1}+(N-2)C_{N-2} &= 2+2(C_{N-1} -C_{N-2})\\ &\therefore \boxed{C_N= 2C_{N-1}-C_{N-2}+\frac{2}{N}} \qquad \text{for $N>1$}. \end{align*}$$

We could have arrived at the same result iteratively by factoring $(1-z)^2=(1-z)(1-z)$.

Exercise 3.32

Let $A(z)=\sum_{n \ge 0}a_nz^n$. The initial differential equation corresponds to the recurrence

$$\begin{align*} (n+1)a_{n+1}&=-a_n+\sum_{0 \le k \le n} a_k && \text{(for $n\ge0$)} \\ &= -a_n+a_n+\sum_{0 \le k < n} a_k \\ &\therefore \boxed{(n+1)a_{n+1}=\sum_{0 \le k < n} a_k}. \end{align*}$$

If we multiply both sides of the equation by $(1-z)$ then we get

$$\begin{align*} (n+1)a_{n+1}-na_n&=-(a_n-a_{n-1})+a_n && \text{(for $n>0$)} \\ &= a_{n-1} \\ &\therefore \boxed{(n+1)a_{n+1}=na_n+a_{n-1}}. \end{align*}$$

This recurrence is describing probabilities of derangements. If we substitute $a_n=d_n/n!$, simplify factorials, multiply through by $n!$, then we get MathWorld's equation (5) with the index shifted by 1 (see the previous link). The equivalent equation (6) can be solved using the method presented in Exercise 2.14. We would arrive at the same result, as shown below.

An easier path is to directly find the OGF and expand.

$$\begin{align*} \frac{A'(z)}{A(z)} &= \frac{z}{1-z} \\ &\therefore A(z) = e^{-z} \cdot \frac{1}{1-z} && \text{($A(0)=1$)}. \end{align*}$$

This gives

$$[z^n]A(z)=a_n=\sum_{0 \le k \le n} \frac{(-1)^k}{k!}.$$

Exercise 3.33 🌟

This exercise shows how new identities may improve performance.

The LHS is the convolution of two series (see Table 3.1):

$$(1 + z)^r = \sum_{k \ge 0} \binom{r}{k} z^k \quad \text{and} \quad (1 - z)^s = \sum_{k \ge 0} \binom{s}{k} (-1)^k z^k.$$

The RHS is also a convolution of two series:

$$(1 - z^2)^s = \sum_{k \ge 0} \binom{s}{k} (-1)^k z^{2k} \quad \text{and} \quad (1 + z)^{r-s} = \sum_{k \ge 0} \binom{r-s}{k} z^k.$$

By equating $[z^n]$ from both sides, we obtain the identity:

$$\sum_{k=0}^n (-1)^k \binom{s}{k} \binom{r}{n-k} = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom{s}{k} \binom{r-s}{n-2k}.$$

What’s the benefit of this identity? Albeit both sides being semantically equivalent, the RHS effectively halves the computation time.When $r$ and $s$ are real numbers, then accuraccy is potentially increased, as well.

Exercise 3.34

$$[z^t]\frac{z^s}{(1-z)^{s+1}} \cdot \frac{z^r}{(1-z)^{r+1}}=[z^t]\frac{1}{z} \cdot \frac{z^{r+s+1}}{(1-z)^{r+s+2}}.$$

Exercise 3.35

We need to compute $\sum_{0 \le k\le N} F_k$. The book contains the OGF for Fibonacci numbers

$$F(z)=\frac{z}{1-z-z^2},$$

where $[z^N]F(z)=F_N$. Observe that the sum of Fibonacci numbers can be represented as a partial sum of $F(z)$. This gives

$$\begin{align*} \frac{F(z)}{1-z} &= \frac{z}{1-z-z^2} \cdot \frac{1}{1-z} \\[0.4cm] &= \underbrace{\frac{1}{1-z-z^2}}_{F_{N+1}}+\underbrace{\frac{1}{1-z-z^2}}_{F_{N}}-\underbrace{\frac{1}{1-z}}_{1} && \text{(via partial fractions expansion)} \\ &\therefore \boxed{\sum_{0 \le k \le N} F_k=F_{N+2}-1}. \end{align*}$$

Exercise 3.36

Wikipedia contains a derivation of the sum expression for $-[z^n]$ as part of the proof. The generating function in this exercise is a negative of the one associated with Bernoulli numbers.

Exercise 3.37

The idea is to employ substitution, as for Fibonacci numbers in the book, and afterward transform the substituted term with another power series. We have

$$\begin{align*} \frac{1}{2 - e^z} &= \frac{1}{2} \cdot \frac{1}{1 - \undergroup{\cfrac{e^z}{2}}}_{y} \\[0.9cm] &= \frac{1}{2} \sum_{k \ge 0} y^k \\ &= \sum_{k \ge 0} \cfrac{e^{kz}}{2^{k+1}} \\ &= \sum_{k \ge 0} \frac{1}{2^{k+1}} \left( \sum_{n \ge 0} \frac{k^n}{n!} z^n \right) && \text{$\left(e^z = \sum_{n \ge 0} \frac{z^n}{n!}\right)$} \\ &= \sum_{n \ge 0} \left( \underbrace{\frac{1}{n!}\sum_{k \ge 0} \frac{k^n}{2^{k+1}}}_{[z^n]\frac{1}{2 - e^z}} \right) z^n. \end{align*}$$

If we treat the generating function from this exercise as an EGF, then it describes the ordered Bell numbers.

Exercise 3.38

We employ the same approach as in the previous exercise. This gives

$$\begin{align*} e^{e^z-1} &= e^{-1}e^{\undergroup{e^z}_{y}} \\ &= e^{-1}e^y \\ &= \sum_{k \ge 0} e^{-1} \frac{y^k}{k!} \\ &= \sum_{k \ge 0} e^{-1} \frac{e^{kz}}{k!} \\ &= \sum_{k \ge 0} e^{-1} \frac{1}{k!} \left(\sum_{n \ge 0} \frac{k^n}{n!}z^n\right) \\ &= \sum_{n \ge 0} \left(\underbrace{e^{-1}\sum_{k \ge 0} \frac{k^n}{k!}}_{n![z^n]e^{e^z-1}}\right) \frac{z^n}{n!}. \end{align*}$$

The expression for the coefficient of the corresponding EGF is known as Dobiński's formula.

Exercise 3.39

Let $A(z)=\sum_n a_nz^n$. We need to show that

$$\begin{align*} [z^n]B(z) &= \sum_{k} \binom{n}{k} a_k (-1)^k \\ \hline \\ B(z) &= \frac{1}{1-z}A\left(\frac{z}{z-1}\right) \\ &= \frac{1}{1-z}A\left(-\frac{z}{1-z}\right) \\ &= \frac{1}{1-z} \sum_n a_n \left(-\frac{z}{1-z}\right)^n \\ &= \frac{1}{1-z} \sum_n a_n (-1)^n \frac{z^n}{(1-z)^n} \\ &= \sum_n a_n (-1)^n \frac{z^n}{(1-z)^{n+1}} \\ &= \sum_n a_n (-1)^n \sum_{k \ge n} \binom{k}{n} z^k \\ &= \sum_n \left(\undergroup{\sum_{k} \binom{n}{k} a_k (-1)^k} \right) z^n. \end{align*}$$

To understand the last step, fix $k=m\ge n$. The coefficient $[z^m]$ will "accumulate" contributions from all $n\le m$. Swapping the roles of $n$ and $k$ gives us the desired expression.

If we substitute $z=y/(y-1)$, then we get

$$A(y) = \frac{1}{1-y}B\left(\frac{y}{y-1}\right),$$

which, by symmetry, validates the opposite direction.

Exercise 3.40

Wikipedia contains an analysis of the binomial transform including the sketch of the proof without using generating functions.

More formally, suppose we start with an arbitrary sequence $\{a_n\}$. We can generate another sequence $\{b_n\}$ from it

$$b_n = \sum_{k=0}^{n} \binom{n}{k} (-1)^ka_k \iff b_n = (-1)^n \Delta^n a_0,$$

where $\Delta$ is the forward difference operator defined by $\Delta a_n = a_{n+1} - a_n$. The $n$th forward difference at index 0 is given by:

$$\Delta^n a_0 = \sum_{k=0}^{n} \binom{n}{k} (-1)^{n-k} a_k.$$

Multiplying both sides by $(-1)^n$ yields the previously stated equivalence.

The transformation is symmetrical and $a_n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k b_k$. We can see this by introducing the shift operator $a_{n+1}=Ea_n=Ia_n+\Delta a_n=(I+\Delta)a_n$, where $I$ is an identity operator. We want to express $a_n$ in terms of applying the shift operator $n$ times to $a_0$. This gives

$$a_n = E^n a_0 = (I + \Delta)^na_0 = \sum_{k=0}^{n} \binom{n}{k} \Delta^k a_0= \sum_{k=0}^{n} \binom{n}{k} (-1)^kb_k.$$

Observe, that $I^k\Delta^{n-k}=\Delta^{n-k}$. This concludes the proof.

Exercise 3.41 🌟

This exercise explains the composition of generating functions.

Wikipedia contains the formal power series version of the Faà di Bruno’s formula, based on the application of the multinomial theorem. An important detail is the precondition $g(0)=0$, which makes the composition valid.

Exercise 3.42

Let’s follow the hint from the book and find a differential equation satisfied by the function

$$\begin{align*} f(z) &= e^{z+z^2/2} \\ \hline \\ f'(z) &= e^{z+z^2/2}(1+z)=f(z)(1+z). \end{align*}$$

Using Table 3.4, we can convert the above differential equation into recurrence relation on coefficients. This gives

$$\begin{align*} f_{n+1} &= f_n+nf_{n-1} && \text{(for $n \ge 1$)} \\ f_n &= f_{n-1}+(n-1)f_{n-2} && \text{(for $n \ge 2$)}. \end{align*}$$

Exercise 3.43

Let $f(z)=\sum_n f_n \frac{z^n}{n!}$, thus $f(z/2)=\sum_n \frac{f_n}{2^n} \frac{z^n}{n!}$. Then, provided that $f(0)=1$, we must have

$$\begin{align*} f(z) &= e^{-z}f\left(\frac{z}{2}\right)+e^{2z}-1 \\ &= e^{-z}(e^{-\frac{z}{2}}f\left(\frac{z}{4}\right)+e^z-1)+e^{2z}-1 \\ &=\undergroup{e^{-z}(e^{-\frac{z}{2}}(e^{-\frac{z}{4}}f\left(\frac{z}{8}\right)+e^{\frac{z}{2}}-1)+e^z-1)}+e^{2z}-1 \\ &\dots \\ &= e^{-2z}-e^{-2z}+1+e^{2z}-1 \\ &= e^{2z}. \end{align*}$$

Let’s dissect in detail the grouped section, to reveal the pattern. The leading term is similar to the example from the book, just with an opposite sign. This provides the first $e^{-2z}$ summand. The following steps are done from inside out

$$\begin{align*} e^{-z}(e^{-\frac{z}{2}}(\dots+e^{\frac{z}{2}}-1)+e^z-1) &= e^{-z}(\dots+1-e^{-\frac{z}{2}}+e^z-1) \\ &= e^{-z}(\dots-e^{-\frac{z}{2}}+e^z) \\ &= \dots\undergroup{-e^{-\frac{z}{2}-z}}+1. \end{align*}$$

Continuing these iterations will result in a geometric progression that sums to $e^{-2z}$. The constant terms annihilate with a remaining +1 at the end. This cancels the -1 in the original formula. As mentioned in the book, technically, we need to justify carrying out the iteration indefinitely, but the solution is easily verified from the original recurrence. Indeed, replacing $f(z)=e^{2z}$ verifies this statement.

Therefore, the recurrence relation and its solution are

$$f_n=2^n+\sum_k (-1)^{n-k}\binom{n}{k}\frac{f_k}{2^k}=2^n \space\space\space\space \text{for $n>0$ with $f_0=1$.}$$

Observe that -1 (from the initial expression) disappears, since it doesn’t influence coefficients for $n>0$. The sum evaluates to zero, recall that $f_k=2^k$, as stated on Wikipedia about partial sums of binomial coefficients.

Exercise 3.44 🌟

This exercise showcases a more intricate functional equation, where interplay of two sub-functions define the OGF.

We need to find an explicit formula for the OGF of the sequence satisfying the divide-and-conquer recurrence

$$\begin{align*} f_{2n} &= f_{2n-1} + f_n && \text{for $n \ge 1$ with $f_0 = 0$}, \\ f_{2n+1} &= f_{2n} && \text{for $n > 0$ with $f_1 = 1$}. \end{align*}$$

Since the recurrence relations distinguish between even and odd indices, let’s split $f(z)$ accordingly

$$f(z) = \sum_{k\ge0} f_k z^k=\underbrace{\sum_{n\ge0} f_{2n} z^{2n}}_{f_e(z)} + \underbrace{\sum_{n\ge0}f_{2n+1} z^{2n+1}}_{f_o(z)}.$$

Examining the Odd Terms

We can write the odd part as

$$\begin{align*} f_o(z) &= f_1 z + \sum_{n\ge1} f_{2n+1} z^{2n+1} \\ &= z + \sum_{n\ge1} f_{2n} z^{2n+1} && \text{($f_1 = 1$ and $f_{2n+1} = f_{2n}$)} \\ &= z + z \sum_{n\ge1} f_{2n} z^{2n} \\ &= z + z \sum_{n\ge0} f_{2n} z^{2n} && \text{($f_0 = 0$ so we can start $n$ at 0)} \\ &\therefore \boxed{f_o(z)=z + z f_e(z)}. \end{align*}$$

Examining the Even Terms

We can write the even part as

$$\begin{align*} f_e(z) &= f_0 + \sum_{n\ge1} f_{2n} z^{2n} \\ &= \sum_{n\ge1} (f_{2n-1} + f_n) z^{2n} \\ &= \undergroup{\sum_{n\ge1} f_{2n-1} z^{2n}}_{S_1} + \undergroup{\sum_{n\ge1} f_n z^{2n}}_{S_2}, \end{align*}$$

$$\begin{align*} S_1 &= z \sum_{n\ge1} f_{2n-1} z^{2n-1} \\ &= z \sum_{n\ge0} f_{2n+1} z^{2n+1} \\ &= z f_o(z), \end{align*}$$

$$\begin{align*} S_2 &= \sum_{n\ge1} f_n (z^2)^n \\ &= f(z^2) - f_0 \\ &= f(z^2), \end{align*}$$

$$\boxed{f_e(z) = z f_o(z) + f(z^2)}.$$

Solving the Full System

We’ve a system of equations

$$\begin{align*} f(z) &= f_e(z) + f_o(z) && \text{(1)} \\ f_o(z) &= z(1 + f_e(z)) && \text{(2)} \\ f_e(z) &= z f_o(z) + f(z^2) && \text{(3)} \end{align*}$$

At this point, we should switch to Sage. The following code presents the solution for $f(z)$.

# f_sq=f(z^2) is treated as a constant symbol.
var('z f_e f_o f f_sq')

eq1 = f == f_e + f_o
eq2 = f_o == z * (1 + f_e)
eq3 = f_e == z * f_o + f_sq

solutions = solve([eq1, eq2, eq3], f_e, f_o, f)
f_solution = solutions[0][2].rhs() 
show(f_solution)

$$f(z) =-\frac{f(z^2)+z}{z-1} =\frac{z}{1-z} + \frac{1}{1-z}f(z^2).$$

Explicit Formula via Iteration

We can solve this functional equation by repeatedly applying it to itself. The objective is to figure out the underlying pattern. This gives

$$\begin{align*} f(z) &= \frac{z}{1-z} + \frac{1}{1-z}f(z^2) \\ &= \frac{z}{1-z} + \frac{1}{1-z}\left[ \frac{z^2}{1-z^2} + \frac{1}{1-z^2}f(z^4) \right] \\ &= \frac{z}{1-z} + \frac{z^2}{(1-z)(1-z^2)} + \frac{1}{(1-z)(1-z^2)}f(z^4) \\ &\dots \\ &\therefore \boxed{f(z) = \sum_{n\ge0} \frac{z^{2^n}}{\prod_{k=0}^{n} (1-z^{2^k})}}. \end{align*}$$

Exercise 3.45

The aim is to repeat the process until a distinct pattern emerges.

$$\begin{align*} f(z) &= 1+zf\left(\frac{z}{1+z}\right) \\ &= 1+z\left(1+\frac{z}{1+z}f\left(\frac{z}{1+2z}\right)\right) \\ &= 1+z\left(1+\frac{z}{1+z}\left(1+\frac{z}{1+2z}f\left(\frac{z}{1+3z}\right)\right)\right) \\ &\dots \\ &=1+z+\frac{z^2}{1+z}+\frac{z^3}{(1+z)(1+2z)}+\dots \\ &\therefore \boxed{f(z)=\sum_{n \ge 0}\frac{z^n}{\prod_{k=0}^{n-1}(1+kz)}}. \end{align*}$$

We can prove the correctness of the formula by induction on $n$. The base case is trivially satisfied; recall that an empty product equals one. The inductive step is based on the following expansion rule

$$f\left(\frac{z}{1+(n-1)z}\right) = 1+\frac{z}{1+(n-1)z}f\left(\frac{z}{1+nz}\right).$$

Therefore, the series in the $n$th iteration becomes

$$\underbrace{\sum_{m = 0}^{n-1}\frac{z^{m}}{\prod_{k=0}^{m-1}(1+kz)}}_{\text{by the inductive hypothesis}}+\frac{z^{n-1}}{\prod_{k=0}^{n-2}(1+kz)} \cdot \frac{z}{1+(n-1)z}=\sum_{m = 0}^n\frac{z^m}{\prod_{k=0}^{m-1}(1+kz)}.$$

Exercise 3.46

Given $f(z)$ defined by the equation $f(z)=z/(1-f(z^2))$ we have to find explicit expressions for $a(z)$ and $b(z)$ with $f(z) = a(z)/b(z)$. We assume that $f(z)$ is analytic at $z=0$, thus $f(0)=a(0)=0$ and $b(0)=1$ (actually, any scaling factor would work).

Substituting $f(z) = a(z)/b(z)$ into the given equation, we get

$$\frac{a(z)}{b(z)} = \frac{z}{1 - \frac{a(z^2)}{b(z^2)}} = \frac{z b(z^2)}{b(z^2) - a(z^2)}.$$

Comparing the numerators and denominators, we can set up the following system of equations:

$$\begin{align*} a(z) &= z b(z^2) && \text{(1)} \\ b(z) &= b(z^2) - a(z^2) && \text{(2)} . \end{align*}$$

Substituting (1) into (2), we get $b(z) = b(z^2) - z^2 b(z^4)$. We can now solve for $b(z)$. Let $b(z) = \sum_{n\ge0} b_n z^n$, so by substituting this series into the recurrence, we get

$$\sum_{n\ge0} b_n z^n = \sum_{n\ge0} b_n z^{2n} - \sum_{n\ge0} b_n z^{4n+2}.$$

Apparently, the RHS has only even powers, hence $b_{2n+1}=0$ for $n \ge 0$.

If $n$ is even, then $b_n=b_{n/2}-b_{(n-2)/4}.$ It helps to view $n$ as a binary number, where division by 2 is right-shifting by one position. The next 4 cases illustrate what happens under the hood, as recursion unfolds until reaching the base case $n=0$. $X_2$ denotes any binary prefix.

1. If $n=X_2010$, then $b_{n/2}=0$ (odd index) and $b_{(n-2)/4}=-b_{X_20}$.

2. If $n=X_2000$, then $b_{n/2}=b_{X_200}$ and $b_{(n-2)/4}=0$ (non-integer index).

3. If $n=X_2100$, then $b_{n/2}=b_{X_210}$ and $b_{(n-2)/4}=0$ (non-integer index).

4. If $n=X_2110$, then $b_{n/2}=0$ (odd index) and $b_{(n-2)/4}=0$ (odd index) .

Thus, by induction on bit position, $b_n$ is non-zero if and only if the binary expansion of $n$ contains no consecutive 1s. Furthermore, advancing via $b_{n/2}$ drops a trailing zero, whilst $b_{(n-2)/4}$ removes a binary 1 and flips a sign. Thus,

$$\begin{align*} b(z) = \sum_{n \in S} (-1)^{\nu_n} z^{2n} \\ a(z) = \sum_{n \in S} (-1)^{\nu_n} z^{4n+1}, \end{align*}$$

where $S$ is a sequence registered under A003714 and $\nu_N$ is the population count (see Chapter 2 in the book). Observe that $\nu_N=\nu_{2N}$.

Exercise 3.47

Only $f(z)=0$ satisfies that $f(z)=\sin(f(z))$, where $f(z)=\sum_{n \ge 1}f_nz^n$.

Suppose, for the sake of contradiction, that there is also another power series $g(z) \neq 0$ of the same form, satisfying the same condition. Let $g_k$ be the lowest indexed non-zero coefficient for $k \ge 1$. Using Taylor's expansion of the sine function, and passing $g(z)$ as an argument, we have

$$\sin(g(z)) = g(z) - \frac{g(z)^3}{6} + \frac{g(z)^5}{120} - \dots$$

But this entails that

$$g(z) = g(z) - \frac{g(z)^3}{6} + \frac{g(z)^5}{120} - \dots$$

since $g(z)=\sin(g(z))$ by definition. Subtracting $g(z)$ from both sides, we get

$$0 = - \frac{g(z)^3}{6} + \frac{g(z)^5}{120} - \dots$$

The lowest term in the RHS is $-\frac{1}{6}g_k^3z^{3k}$, since the others have higher powers of $z$, so $g_k$ must be zero. But this contradicts our assumption that $g_k \neq 0$. Therefore, $f(z)=0$ is a unique solution.

Exercise 3.48

The text of this exercise in the book is imprecise. The paper Singularity Analysis Of Generating Functions* contains a section about 2-3 trees, where the matching functional equation represents the number of such trees with n external nodes.

Let $f(z) = \sum_{n \ge 0} f_n z^n$ be the OGF for the number of 2–3 trees , where $f_n$ denotes the number of trees with $n$ external nodes. Based on the functional equation $f(z) = z + f(z^2 + z^3)$, we see that $f_0=0$ and $f_1=1$. Notice, that the second summand generates higher-order terms, so for $n>1$ the first summand has no effect. We can substitute the form of OGF into the functional equation to get

$$\undergroup{\sum_{n \ge 2} f_n z^n = \sum_{n \ge 2} f_n (z^2 + z^3)^n}_{LHS}=\undergroup{\sum_{k \ge 2} f_k \sum_{j=0}^k \binom{k}{j} z^{2j}z^{3(k-j)}=\sum_{k \ge 2} f_k \sum_{j=0}^k \binom{k}{j} z^{3k-j}}_{RHS}.$$

To find the recurrence for $f_n$, we equate coefficients of the same rank on both sides. This gives the following constraints on $k$, using the fact that $0 \le j \le k$, for which there is always some $j$ such that $3k-j=n$:

• $3k-j\le n \implies 2k \le n \implies k \le \lfloor n/2 \rfloor.$

• $3k-j\ge n \implies 3k \ge n \implies k \ge \lceil n/3 \rceil.$

Thus, for any fixed $n>1$, we have

$$f_n = \sum_{k=\lceil n/3 \rceil}^{\lfloor n/2 \rfloor} \binom{k}{3k - n} f_k.$$

The next Python script computes the number of 2–3 trees of 100 external nodes.

from math import ceil, comb

f = [0 for _ in range(101)]
f[1] = 1
for n in range(2, 101):
    f[n] = sum(comb(k, 3 * k - n) * f[k] for k in range(ceil(n / 3), n // 2 + 1))
print(f[100])

It prints $5,520,498,313,790,316,062$.

As a verification step, it’s advisable to search for the sequence in the online encyclopedia. For instance, by displaying 20 values generated by this script (including the initial terms), we can confirm that it corresponds to A014535.

Exercise 3.49 🌟

We show by induction on $t$ that $(1-z)^tC^{(t)}(z)=\Psi(\Psi+1)\dots (\Psi+t-1)C(z)$.

The book, at the time of this writing, has an error; $t+1$ must be replaced by $t-1$.

Observe, that $\Psi$ can be manipulated as any other "symbol" in arithmetic expressions. For the sake of completeness, let’s show that $(\Psi+m)(\Psi+n)F(z)=(\Psi+n)(\Psi+m)F(z)$ for any nonnegative integers $n$, $m$ and arbitrary function $F(z)$. We have

$$\begin{align*} (\Psi+m)(\Psi+n)F(z) &= (\Psi+m)((1-z)F'(z)+nF(z)) \\ &= \Psi((1-z)F'(z))+\Psi(nF(z))+m(1-z)F'(z)+mnF(z) \\ &= -(1-z)F'(z)+(1-z)^2F''(z)+n(1-z)F'(z)+m(1-z)F'(z)+mnF(z) \\ &= (1-z)^2F''(z)+(n+m-1)(1-z)F'(z)+nmF(z) \\ \hline \\ (\Psi+n)(\Psi+m)F(z) &= (\Psi+n)((1-z)F'(z)+mF(z)) \\ &= \Psi((1-z)F'(z))+\Psi(mF(z))+n(1-z)F'(z)+nmF(z) \\ &= -(1-z)F'(z)+(1-z)^2F''(z)+m(1-z)F'(z)+n(1-z)F'(z)+nmF(z) \\ &= (1-z)^2F''(z)+(n+m-1)(1-z)F'(z)+nmF(z). \end{align*}$$

We proceed by induction on $t$ .The base case is trivially satisfied, since $\Psi C(z)≡(1-z)C'(z)$. For the inductive step, we have

$$\begin{align*} (\Psi+t-1)((1-z)^{t-1}C^{(t-1)}(z)) &= \Psi((1-z)^{t-1}C^{(t-1)}(z)) + (t-1)(1-z)^{t-1}C^{(t-1)}(z) \\ &= (1-z)(-(t-1)(1-z)^{t-2}C^{(t-1)}(z)+(1-z)^{t-1}C^{(t)}(z)) + (t-1)(1-z)^{t-1}C^{(t-1)}(z) \\ &= -(t-1)(1-z)^{t-1}C^{(t-1)}(z)+(1-z)^tC^{(t)}(z)+ (t-1)(1-z)^{t-1}C^{(t-1)}(z) \\ &\therefore (1-z)^tC^{(t)}(z) = (\Psi+t-1)\underbrace{\Psi(\Psi+1)\dots (\Psi+t-2)C(z)}_{\text{by the inductive hypothesis}}. \end{align*}$$

By successively swapping neighboring elements, we can move $(\Psi+t-1)$ into the last position without disturbing the relative ordering of the other terms. This proves that the statement of this exercise holds for any $t \ge 1$.

Exercise 3.50

Sedgewick’s paper The Analysis of Quicksort Programs contains a full analysis of median-of-three quick-sort algorithm (see section 3.2). It derives the base formula in a more detailed manner than the book itself.

Exercise 3.51

Section 3.3 of the paper mentioned in the previous exercise shows the analysis of the median of $2t+1$ quick-sort algorithm. Therefore, for a sample size of 5 we would use $t=2$.

Exercise 3.52 🌟

This exercise examines advanced calculus concepts and is indirectly related to the book, via linkage to generating functions. In order to encompass diverse perspectives, the answer is more focused on the methodology itself, whilst low-level details are skipped (like, step-by-step derivations of intermediate results). Otherwise, writing up everything would demand a separate chapter.

Understanding the Problem

The specific ordinary differential equation (ODE) with variable coefficients considered here is

$$\sum_{j=0}^{r} (1-z)^{r-j} \frac{d^j}{dz^j} f(z)=0,$$

and its inhomogeneous counterpart,

$$\sum_{j=0}^{r} (1-z)^{r-j} \frac{d^j}{dz^j} f(z)= (1-z)^{\alpha}.$$

Unlike the classical Euler-Cauchy equation, where the power of the independent variable scales directly with the order of the derivative, this equation exhibits an inverse scaling relationship: as the order of the derivative $j$ increases, the power of the coefficient $(1-z)^{r-j}$ decreases.

Leading-Coefficient Observation

Let’s expand the LHS

$$a_r(z) f^{(r)}(z)+a_{r-1}(z) f^{(r-1)}(z)+\dots+a_0(z) f(z),$$

with $a_j(z)=(1-z)^{r-j}$. The coefficient of the highest derivative is

$$a_r(z)=(1-z)^{r-r}=(1-z)^0=1,$$

so the leading coefficient is nonzero at $z=1$. Consequently, for the homogeneous equation the point $z=1$ is an ordinary point in the sense that the normalized coefficients $a_j(z)/a_r(z)$ are analytic at $z=1$. This implies homogeneous solutions are analytic at $z=1$ and admit Taylor expansions about that point.

The inhomogeneous term $(1-z)^{\alpha}$ may be non-analytic at $z=1$, so requires a careful analysis. Our focus will be on the Frobenius method. While it’s traditionally taught as a tool for regular singular points, its utility extends to constructing particular solutions for inhomogeneous equations, as in our case. We’ll showcase the Frobenius method in "inverted" regime.

The method of Frobenius can be viewed as a superset of the power series method. This is another reason why it’s a natural choice for this exercise related to a chapter about generating functions.

Change of Variable

Let $x=1-z$, such that

$$\frac{d}{dz}=-\frac{d}{dx},\qquad \frac{d^j}{dz^j}=(-1)^j\frac{d^j}{dx^j},$$

so the equation becomes

$$\sum_{j=0}^{r} (-1)^j x^{\,r-j} f^{(j)}(x)=x^{\alpha}$$

for the inhomogeneous problem. Because the coefficient of $f^{(r)}(x)$ is $(-1)^r x^{r-r}=(-1)^r$, a nonzero constant, the homogeneous equation has analytic coefficients at $x=0$. The above canonical transformation centers a potential singularity at the origin.

First-Order Case $r=1$

It always make sense to start with the simplest form to develop intuition and cement understanding of the task. The transformed equation is

$$f'(x)-x f(x)=\begin{cases}0 &\text{homogeneous variant} \\ -x^{\alpha} &\text{inhomogeneous variant} \end{cases},$$

The closed-form solution of the homogeneous version is $f(x) = C e^{x^2/2}$, where $C$ is an arbitrary constant. This is an entire function, as expected.

For solving the other version, we apply an integrating factor $I(x)=\exp\!\big(-\tfrac{x^2}{2}\big)$. Multiplying through and integrating gives

$$f(x)=C e^{x^2/2}-e^{x^2/2}\int x^{\alpha} e^{-x^2/2}\,dx.$$

Second-Order Case $r=2$

The transformed equation is

$$f''(x)-x f'(x)+x^2 f(x)=\begin{cases}0 &\text{homogeneous variant} \\ x^{\alpha} &\text{inhomogeneous variant} \end{cases}.$$

The homogeneous part can be solved using OGFs. Let $f_H(x)=\sum_{n\ge0} a_n x^n$, so substitution yields the recurrence

$$\begin{align*} (n+2)(n+1)a_{n+2}-n a_n + a_{n-2} &= 0 \qquad (\text{for }n\ge2) \\ &\therefore \boxed{a_{n+2} = \frac{n a_n - a_{n-2}}{(n+2)(n+1)}}, \end{align*}$$

with initial relations $a_2=0$ and $a_3=a_1/6$. The recurrence links coefficients of the same parity, hence the solution space splits into an even $\{e_n\}$ and odd $\{o_n\}$ series. To peek into the derivation details, it’s instructive to read an analysis of the Hermite differential equation.

For finding the particular solution, we employ the Frobenius method. We start with the default ansatz

$$f_P(x)=x^k\sum_{n \ge0} b_n x^n.$$

The lowest term is from $f_P''(x)$, thus matching to $x^{\alpha}$ yields $k=\alpha+2$. This gives

$$f_P(x)=\sum_{n \ge0} b_n x^{\alpha+2+n}.$$

Matching coefficients for power $x^{\alpha+n}$ produces a recurrence of the form

$$(\alpha+n+2)(\alpha+n+1)b_n-(\alpha+n)b_{n-2}+b_{n-4}=\delta_{n0}.$$

Solving the system for $n=0,1,2,3$ gives

$$\begin{align*} b_0 &= \frac{1}{(\alpha+1)(\alpha+2)} \\ b_1 &= 0 \\ b_2 &= \frac{1}{(\alpha+1)(\alpha+3)(\alpha+4)} \\ b_3 &= 0 . \end{align*}$$

Apparently, odd terms vanish. The full solution is

$$f(x) = A\sum_{n\ge0} e_nx^{2n} + B \sum_{n\ge0} o_nx^{2n+1} + \sum_{n\ge0} b_{2n} x^{\alpha+2+2n},$$

where $A$ and $B$ are arbitrary constants.

Exceptional Case

If the denominator of any coefficient becomes zero, for instance, when $\alpha=-2$, then we have to modify the ansatz. The Frobenius method mandates the inclusion of a logarithmic term

$$f_P(x)=x^{\alpha+2}\left(A\ln x\sum_{n\ge0} b_n x^n+\sum_{n\ge0} c_n x^n\right).$$

The logarithmic coefficients are determined by substituting this ansatz and solving the resulting linear system.

General Case $r>2$

The transformed equation is

$$\sum_{j=0}^{r} (-1)^j x^{r-j} f^{(j)}(x)=\begin{cases}0 &\text{homogeneous variant} \\ x^{\alpha} &\text{inhomogeneous variant} \end{cases}.$$

Again, the homogeneous part can be solved using OGFs. The recurrence relation becomes a difference equation of order $r$. Specifically, the coefficient of $x^n$ in the expansion involves terms from $a_{n+r}$ down to $a_{n-r}$; $x^{r-j}$ is paired with $d^j/dx^j$, so the shift in power is always $(r-j) - j = r - 2j$. Thus, the parity of the shifts (even vs odd) is fixed by the parity of $r$. There are two cases:

• If $r$ is even, then every shift is even. The recurrence links coefficients whose indices differ by even integers only, so the power‑series splits into two independent parity subspaces (even and odd). Each parity subspace supplies independent solutions. We have already seen example of this with $r=2$.

• If $r$ is odd, then every shift is odd. The recurrence links coefficients of opposite parity (indices differing by odd integers), so even and odd coefficients are coupled together. There is no decomposition into two independent parity subspaces; the recurrence mixes both parities and produces a single chain of coupled coefficients that yields the full set of $r$ independent solutions.

The parity decomposition is a computational convenience (it halves the work) whenever $r$ is even.

For finding the particular solution, we employ the Frobenius method, starting with the default ansatz. The highest-derivative term $f^{(r)}$ produces the lowest power, thus matching to $x^{\alpha}$ gives

$$k-r=\alpha\implies k=\alpha+r.$$

Hence, the particular solution begins at $x^{\alpha+r}$

$$f_P(x)=\sum_{n\ge0} b_n x^{\alpha+r+n}.$$

We must manage exceptional cases, as in the situation with $r=2$.

Exercise 3.53

The answer is given already in Exercise 3.51.

Exercise 3.54

We define $T$ to be the set of all binary trees, and adopt the notation $|t|$ to represent, for $t \in T$, the number of external nodes in $t$. Then we have the following derivation:

$$\begin{align*} T(z) &= \sum_{t \in T}z^{|t|} \\ &= z + \sum_{t_L \in T}\sum_{t_R \in T} z^{|t_L|+|t_R|} \\ &= z + T(z)^2. \end{align*}$$

The first line is an alternative way to express $T(z)$ from its definition. Each tree with exactly $k$ external nodes contributes exactly $1$ to the coefficient of $z^k$, so the coefficient of $z^k$ in the sum “counts” the number of trees with $k$ external nodes. The second line follows from the recursive definition of binary trees: either a binary tree has one external node (which accounts for the $z$), or it can be decomposed into two independent binary trees whose external nodes comprise the external nodes of the original tree, without the root (internal node). The third line follows because the index variables $t_L$ and $t_R$ are independent.

In this case $T(0)=0$. It is always worthwhile to check our the math with a computer. The next Sage snippet correctly prints the first few known initial values and $T_6=42=\frac{1}{6}\binom{10}{5}$:

ZP.<z> = ZZ[]
z+(z+z^2+2*z^3+5*z^4+14*z^5)*(z+z^2+2*z^3+5*z^4+14*z^5)

Exercise 3.55 🌟

This and the next exercise show how the usage of generating functions can improve performance that wouldn’t be possible by purely technological measures.

The given OGF is a rational function

$$D(z) = \frac{1}{(1-z)(1-z^5)(1-z^{10})(1-z^{25})(1-z^{50})}.$$

The book contains a remark, that we can learn much about asymptotic behavior of coefficients by looking at singularities of the generating function. A $k$th root of unity $\omega$ for $k \in\{1,5,10,25,50\}$ makes the denominator zero. To understand the coefficients, we look at the partial fraction decomposition of $D(z)$ and connect it to these singularities.

The value $z=1$ has order $5$, as it makes any factor $1-z^k$ zero in the denominator. The matching summand in the decomposition of $D(z)$ would participate as $C/(1-z)^5$, where $C$ is some constant. Looking at Table 3.1, this would be represented in expanded form as $\sum_{N \ge 0} \binom{N+4}{N}z^N$. Therefore, the coefficient of $z^N$ would grow as $\Theta(N^4)$. Observe, that the other roots of unity are associated with lower multiplicities. Nevertheless, they do introduce cyclic fluctuations to the count, since they are periodic.

Combining the polynomial growth from $z=1$ and the periodicity from the other roots of unity, we get that the form of $[z^N]D(z)$ is a quasi-polynomial. If we denote by $r \equiv N \pmod{50}$, where $50$ is a least common multiple of the coin denominations, then we have

$$[z^N]D(z) = a_4(r)N^4 + a_3(r)N^3 + a_2(r)N^2 + a_1(r)N + a_0(r),$$

where the coefficients $a_i(r)$ depend on the remainder $r$.

Exercise 3.56

The next Python program uses the mathematical model from the previous exercise. The idea is to precompute coefficients for $r \in [0,49]$ and afterward evaluate the quasi-polynomial for a given $N$. The implementation employs dynamic programming as well as fast linear equations solver from the Numpy package. The system of linear equations is represented as a Vandermonde matrix.

import numpy as np

class ChangeDollar:
    def __init__(self):
        self.coins = [1, 5, 10, 25, 50]
        self._period = 50
        self._degree = 4
        self._coeffs = self._precompute_coefficients()

    def _solve(self, limit):
        dp = [0] * (limit + 1)
        dp[0] = 1
        for coin in self.coins:
            for i in range(coin, limit + 1):
                dp[i] += dp[i - coin]
        return dp

    def _precompute_coefficients(self):
        # To find 5 coefficients for a degree 4 poly, we need 5 points for each r.
        limit = self._period * self._degree + (self._period - 1)
        dp = self._solve(limit)
        coeffs = [0] * (self._period + 1)
        for r in range(self._period):
            # Points for interpolation: N = r, r+50, r+100, r+150, r+200
            x = np.array([r + self._period * i for i in range(self._degree + 1)], dtype=float)
            y = np.array([dp[int(val)] for val in x], dtype=float)

            # Solve the system of linear equations (Vandermonde matrix)
            # a4*x^4 + a3*x^3 + a2*x^2 + a1*x + a0 = y
            linear_system = np.vander(x, self._degree + 1)
            coeffs[r] = np.linalg.solve(linear_system, y)
        return coeffs

    def solve(self, n):
        if n < 0:
            return 0
        r = n % self._period
        result = np.polyval(self._coeffs[r], n)
        return int(round(result))

solver = ChangeDollar()
for n in (100, 200, 3731, 10**12):
    print(f"Number of ways to change {n} cents: {solver.solve(n)}")

Running this program produces the following output:

Number of ways to change 100 cents: 292
Number of ways to change 200 cents: 2435
Number of ways to change 3731 cents: 135730300
Number of ways to change 1000000000000 cents: 666666666793332747200572713557045308030976

LeetCode also offers this problem under Coin Change II, although covers only small cases.

Exercise 3.57

This is a simple variation of Polya's problem of changing a dollar. Instead of coins, we have powers of 2 excluding $2^0$. Let the index $p_i$ denote the number of $2^i$ factors. This gives

$$\begin{align*} T(z) &= \sum_{p_1,p_2,\dots \ge 0}z^{p_12^1+p_22^2+\dots} \\ &= \sum_{p_1}z^{p_12^1}\sum_{p_2}z^{p_22^2}\dots \\ &= \prod_{k \ge 1} \frac{1}{1-z^{2^k}}. \end{align*}$$

Each configuration of powers of 2 that adds up to $N$ clearly contributes exactly 1 to the coefficient of $z^N$. The second line follows since the indices of summation are all independent. The last line is a translation based on Table 3.1 from the book.

Exercise 3.58 🌟

This exercise derives the foundational identity that $1-z$ and $f(z)=\sum_nz^n$ are inverses of each other and provides the proof of the Euler’s identity.

We can show this by treating $f(z)$ as a formal power series

$$\begin{align*} (1-z)\sum_{n \ge 0}z^n &= \sum_{n \ge 0}z^n - z\sum_{n \ge 0}z^n \\ &= 1 + \sum_{n \ge 1}z^n - \sum_{n \ge 1}z^n \\ &= 1. \end{align*}$$

First, we prove by induction on $t$ that

$$\prod_{n=0}^{t-1}{(1+z^{2^n})}=\sum_{n=0}^{2^t-1}z^n= \frac{z^{2^t}-1}{z-1}.$$

The base case $t=1$ is trivially satisfied. For $t>1$ we have

$$\begin{align*} \prod_{n=0}^{t-1}{(1+z^{2^n})} &= \prod_{n=0}^{t-2}{(1+z^{2^n})}(1+z^{2^{t-1}}) \\ &= \left(\sum_{n=0}^{2^{t-1}-1}z^n\right)(1+z^{2^{t-1}}) && \text{(by the inductive hypothesis)} \\ &= \sum_{n=0}^{2^{t-1}-1}z^n + z^{2^{t-1}}\sum_{n=0}^{2^{t-1}-1}z^n \\ &= \sum_{n=0}^{2^{t-1}-1}z^n + \sum_{n=2^{t-1}}^{2^t-1}z^n \\ &= \sum_{n=0}^{2^t-1}z^n. \end{align*}$$

When $t \to \infty$ then $\sum_nz^n=\prod_n{(1+z^{2^n})}$, so Euler's identity follows.

The identity reflects the fact that every non-negative integer has a unique binary representation. Expanding the product is equivalent to forming exponents by summing distinct powers of 2. Since every integer $n$ can be written as a sum of powers of 2 in exactly one way, every term $z^n$ appears exactly once in the resulting series.

Exercise 3.59

In base 2, the digits are $\{0, 1\}$, so the factors were $(1 + z^{2^n}) = (z^{0 \cdot 2^n} + z^{1 \cdot 2^n})$.

In base 3, the digits are $\{0, 1,2\}$. This means that for each position $n$ (representing the value $3^n$), we need a term that offers the choice of adding $0 \cdot 3^n$, $1 \cdot 3^n$, or $2 \cdot 3^n$ to the exponent. Therefore, the generalized identity is

$$\frac{1}{1-z} = \prod_n \left(1 + z^{3^n} + z^{2 \cdot 3^n}\right).$$

All the other details are analogous to the previous exercise.

Exercise 3.60

As in Exercise 3.58, expanding the product is equivalent to forming exponents by summing distinct powers of 2. But this time the expansion also happens with a sign flip. Adding each power of 2 is equivalent to increasing the number of ones in a binary representation of $N$ by 1. We start with the factor $1-z$, hence even number of ones are designated with +1, whilst odd number of ones with -1. This gives

$$[z^N](1-z)(1-z^2)(1-z^4)\dots = (-1)^{\nu_N},$$

where $\nu_N$ is the population count.

Exercise 3.61

The expected value of $X$ expressed in terms of $r_k$ is known as the tail-sum formula.

$$\begin{align*} \operatorname{var}(X) &= \mathbb{E}(X^2) - [\mathbb{E}(X)]^2 \\ &= \sum_{k \ge 0} k^2p_k -[\mathbb{E}(X)]^2\\ &= \sum_{k\ge0} \left(p_k \sum_{i=0}^{k-1} (2i+1)\right) - [\mathbb{E}(X)]^2 && \text{($\sum_{i=0}^{k-1} (2i+1)=k^2$)} \\ &= \sum_{i\ge0} \left((2i+1) \sum_{k\ge i+1} p_k\right) - [\mathbb{E}(X)]^2 \\ &= \sum_{k\ge0} (2k+1)(1 - r_k) -[\mathbb{E}(X)]^2 \\ &= 2 \sum_{k \ge 0} k(1 - r_k) + \mathbb{E}[X] - \mathbb{E}[X]^2. \end{align*}$$

Exercise 3.62

We define a combined function $R(x) = P(x)Q(x)$ and apply standard calculus rules. Recall that $P(1)=Q(1)=1$ is given as a precondition.

To prove the mean we must express $R'(1)$ in terms of $P'(1)$ and $Q'(1)$. This gives

$$\begin{align*} R'(x) &= P'(x)Q(x) + P(x)Q'(x) \\ R'(1) &= P'(1) + Q'(1) \\ &\therefore \mathbb{E}(PQ)=\mathbb{E}(P)+\mathbb{E}(Q) \qquad \checkmark \end{align*}$$

The variance is handled in a similar way, but we have to first find the second derivative of $R(x)$.

$$\begin{align*} R''(x) &= \frac{d}{dx}[P'(x)Q(x) + P(x)Q'(x)] \\ &= [P''(x)Q(x) + P'(x)Q'(x)] + [P'(x)Q'(x) + P(x)Q''(x)] \\ &= P''(x)Q(x) + 2P'(x)Q'(x) + P(x)Q''(x) \\ R''(1) &= P''(1) + 2P'(1)Q'(1) + Q''(1). \end{align*}$$

We can now substitute $R''(1)$ and $R'(1)$ into the definition of variance, thus

$$\begin{align*} \operatorname{var}(PQ) &= R''(1) + R'(1) - R'(1)^2 \\ &= [P''(1) + 2P'(1)Q'(1) + Q''(1)] + [P'(1) + Q'(1)] - [P'(1) + Q'(1)]^2 \\ &= P''(1) + 2P'(1)Q'(1) + Q''(1) + P'(1) + Q'(1) - (P'(1)^2 + 2P'(1)Q'(1) + Q'(1)^2) \\ &= [P''(1) + P'(1) - P'(1)^2] + [Q''(1) + Q'(1) - Q'(1)^2] \\ &= \operatorname{var}(P)+\operatorname{var}(Q) \qquad \checkmark \end{align*}$$

Exercise 3.63

The derivates of $P_n(u)$ can be easily computed using WolframAlpha; the second derivate is one the alternative forms offered by the tool.

$$\begin{align*} P'_n(u) &= \frac{(n - 1) u^n - n u^{n-1} + 1}{n (1 - u)^2} \\ P''_n(u) &= \frac{n^2 (u - 1)^2 u^{n - 2} + n (1 - u) (3 u - 1) u^{n - 2} + 2 (u^n - 1)}{n (u - 1)^3}. \end{align*}$$

Using l’Hôpital’s rule we can compute the derivatives at 1. Again, WolframAlpha can help a lot in finding derivates of complicated numerators.

$$\begin{align*} \lim_{u \to 1}P'_n(u) &= \lim_{u \to 1} \frac{(n - 1) u^n - n u^{n-1} + 1}{n (1 - u)^2} \\ &= \lim_{u \to 1} \frac{(n - 1) n u^{n-1} - n(n-1) u^{n-2}}{-2n (1 - u)} \\ &= \lim_{u \to 1} \frac{(n - 1)^2 n u^{n-2} - n(n-1)(n-2) u^{n-3}}{2n} \\ &= \frac{n-1}{2} \qquad \checkmark \end{align*}$$

$$\begin{align*} \lim_{u \to 1}P''_n(u) &= \lim_{u \to 1} \frac{n^2 (u - 1)^2 u^{n - 2} + n (1 - u) (3 u - 1) u^{n - 2} + 2 (u^n - 1)}{n (u - 1)^3} \\ &= \lim_{u \to 1} \frac{n (n^2 - 3 n + 2) (u - 1)^2 u^{n - 3}}{3n (u - 1)^2} \\ &= \lim_{u \to 1} \frac{n (n^2 - 3 n + 2) (u - 1) (n (u - 1) - u + 3) u^{n - 4}}{6n(u-1)} \\ &= \lim_{u \to 1} \frac{n (n^2 - 3 n + 2) u^{n - 5} (n^2 (u - 1)^2 + n (-3 u^2 + 10 u - 7) + 2 (u^2 - 6 u + 6))}{6n} \\ &= \frac{n^2-3n+2}{3} \\ &= \frac{(n-2)(n-1)}{3} \qquad \checkmark \end{align*}$$

Exercise 3.64

Let $X$ be the random variable that counts the number of leading zeros in a random binary string. For a string of size $n$ with independent fair bits, the probability mass function is

$$p_k = \begin{cases} \left(\cfrac{1}{2}\right)^k \cdot \cfrac{1}{2} = \cfrac{1}{2^{k+1}} &\text{if } 0 \le k < n \\ \cfrac{1}{2^n} &\text{if } k = n \end{cases}.$$

The corresponding PGF is

$$P_n(u) = \frac{1}{2} +\frac{u}{4}+\frac{u^2}{8}+ \dots + \frac{u^{n-1}}{2^n}+\frac{u^n}{2^n}= \frac{u^n}{2^n} + \frac{1 - \frac{u^n}{2^n}}{2 - u}.$$

The mean is $P_n'(1)=1-\frac{1}{2^n}$.

For the variance we need $P''_n(1)=2-\frac{n+1}{2^{n-1}}$, so

$$\operatorname{var}(X)=2-\frac{n+1}{2^{n-1}}+1-\frac{1}{2^n}-\left(1-\frac{1}{2^n}\right)^2=2-\frac{n}{2^{n-1}}-\frac{1}{2^{2n}}-\frac{1}{2^n}.$$

The standard deviation is $\sigma_X=\sqrt{\operatorname{var}(X)}$. When $n \to \infty$ then the mean is 1 and the standard deviation is $\sqrt2$.

Exercise 3.65

We must find the only missing piece $p''_n(1)$. We have

$$p''_n(u)=n(n-1)(1+u)^{n-2} \implies p''_n(1)=n(n-1)2^{n-2}.$$

After substituting all known quantities into the formula from Table 3.5, we get that the variance for the number of 1 bits in a random binary string of length $n$ is $n/4$.

Exercise 3.66

Let’s focus our attention on $[z^n]$, since we want to find the mean for the binomial distribution with size $n$. We know that $[z^n]q_k(z)=\binom{n}{k}$, so $0 \le k \le n$. Furthermore, $[z^n]P(z,1)=2^n$. We also have

$$[z^n]r_k(z)=\sum_{0 \le j \le k} \binom{n}{j}.$$

Substituting all these into the formula for the cumulated cost gives

$$\begin{align*} [z^n]\sum_{k \ge 0}(P(z,1)-r_k(z)) &= \sum_{0 \le k \le n}\left(2^n-\sum_{0 \le j \le k} \binom{n}{j}\right) \\ &= (n+1)2^n-\sum_{0 \le k \le n}\sum_{0 \le j \le k} \binom{n}{j} \\ &= (n+1)2^n-\frac{(n+1)2^n+2^n}{2} \\ &= \frac{n}{2} \cdot 2^n. \end{align*}$$

The double sum can be easily calculated by drawing a symmetric square matrix of size $(n+1) \times (n+1)$. The $k$th row should be filled with $\binom{n}{k}$. All columns sum to $2^n$ and the main diagonal also sums to $2^n$. Our double sum is half the total sum of all entries. There is only one caveat; we must add once again the sum of entries at the main diagonal before dividing by 2.

Finally, the mean is simply the cumulated cost divided by $2^n$, which results in $n/2$.

Exercise 3.67

The book doesn’t provide details about derivation of the functional equation that must be satisfied by the BGF. This is important for understanding this and the next exercise. So, we’ll fill the gap here.

Derivation of the Functional Equation

We are given the recurrence for the PGF

$$Q_N(u) = \frac{1}{N} \sum_{k=1}^{N} u^{N+1} Q_{k-1}(u) Q_{N-k}(u),$$

that is defining the exponential BGF

$$Q(z, u) = \sum_{N \geq 0} Q_N(u) z^N.$$

Notice that $Q(z, 1)$ represents the sum of probabilities for each $N$, so it must designate a sequence of all ones, hence $Q(z, 1)=1/(1-z)$.

When dealing with permutations, there is an inherent duality between an exponential BGF and a "probability" ordinary BGF. Namely, the division by $N!$ moves into the kernel of an EBGF, which gets "activated" once we read out the coefficients of partial derivatives evaluated at $u=1$. It’s unnecessary to perform the division by the number of structures, as this calculation has already been done "from" the kernel. As a matter of fact, stricly dividing by $[z^N]Q(z,1)=1$ is redundant.

Let’s differentiate this BGF with respect to $z$ and substitute the recurrence of $Q_N(u)$ into it. We use the compact notation for partial derivatives, as introduced in the book.

$$\begin{align*} Q_z(z, u) &= \sum_{N \ge 1} Q_N(u) Nz^{N-1} \\ &= \sum_{N \ge 1} \left( \sum_{k=1}^{N} u^{N+1} Q_{k-1}(u) Q_{N-k}(u) \right) z^{N-1} \\ &= u^2\sum_{N \ge 1} \left( \sum_{k=1}^{N} Q_{k-1}(u) Q_{N-k}(u) \right) (uz)^{N-1} \\ &= u^2\sum_{N \ge 1} \left( \sum_{k=0}^{N-1} Q_k(u) Q_{N-1-k}(u) \right) (uz)^{N-1} \\ &= u^2\sum_{N \ge 0} \left( \sum_{k=0}^N Q_k(u) Q_{N-k}(u) \right) (uz)^N \\ &= u^2Q^2(zu, u) && \text{(self-convolution of Q(zu, u))}. \end{align*}$$

The correct initial condition is $Q(0,u)=Q_0(u)=1$, which tells that sorting an empty array has zero cost with absolute certainty (probability is 1). The book shows the arguments in permuted order.

Solution of the Exercise

We know that $Q_N(1)=1$, since $Q_N(u)$ is a PGF. This gives

$$\begin{align*} Q'_N(u) &= \frac{1}{N} \sum_{k=1}^{N} \left((N+1)u^N Q_{k-1}(u) Q_{N-k}(u) + u^{N+1}(Q'_{k-1}(u) Q_{N-k}(u)+Q_{k-1}(u) Q'_{N-k}(u))\right) \\ &\therefore Q'_N(1) = N+1 + \frac{1}{N}\sum_{k=1}^{N} (Q'_{k-1}(1)+Q'_{N-k}(1)). \end{align*}$$

Notice that $Q'_N(1)$ satisfies the standard quicksort recurrence that the book addressed in section 3.3, so it must have the same solution. Consequently,

$$q^{[1]}(z)=Q_u(z, u)\bigg|_{u=1}=\sum_{N \geq 0} Q'_N(1) z^N=\frac{2}{(1-z)^2} \ln \frac{1}{1-z}.$$

To verify the expression for $q^{[2]}(z)$ we must differentiate the functional equation that $Q(z,u)$ must satisfy twice with respect to $u$. To make the exposition manageable, due to convoluted terms, let’s introduce the following substitutions:

• $A(z)=Q(z,1)=1/(1-z)$ implying that $A'(z)=A^2(z)$.

• $x\equiv uz$, $y \equiv u$ and $B(x,y)=Q(x,y)$ implying that $B_u=zB_x+B_y$. This follows from applying the multivariable chain rule.

Let’s differentiate $Q_z=u^2B^2$ once w.r.t. $u$ to get

$$Q_{zu}=2u\,B^2+2u^2\,B\,B_u.$$

Repeating the previous step once more we arrive at

$$Q_{zuu}=2B^2+8uBB_u+2u^2\bigl(B_u^2+B\,B_{uu}\bigr).$$

Evaluated at $u=1$ this becomes

$$(q^{[2]})'(z)=2A^2+8A\,B_u(z,1)+2\Bigl(B^2_u(z,1)+A\,B_{uu}(z,1)\Bigr).$$

It remains to compute $B_{uu}(z,1)$. Since $B_u=zQ_z(uz,u)+Q_u(uz,u)$ we have

$$\begin{align*} B_{uu} &=z\Bigl(zQ_{zz}(uz,u)+Q_{zu}(uz,u)\Bigr)+\Bigl(zQ_{zu}(uz,u)+Q_{uu}(uz,u)\Bigr) \\ &\therefore B_{uu}(z,1)=z^2Q_{zz}(z,1)+2z\,Q_{zu}(z,1)+q^{[2]}(z). \end{align*}$$

Now

$$Q_{zz}(z,1)=A''(z)=2A(z)^3,\qquad Q_{zu}(z,1)=(q^{[1]})'(z).$$

We can eliminate $Q$ from $B_{uu}$

$$B_{uu}(z,1)=2z^2A^3+2z(q^{[1]})'(z)+q^{[2]}(z).$$

We also have

$$B_u(z,1)=zA^2+q^{[1]}(z) =\frac{z}{(1-z)^2}+\frac{2}{(1-z)^2}\ln\frac1{1-z}.$$

Substituting into the expression for $(q^{[2]})'(z)$ and simplifying yields a linear first-order ODE, with $q^{[2]}(0)=0$, of the form

$$(q^{[2]})'(z)-\frac{2}{1-z}\,q^{[2]}(z)= \frac{14}{(1-z)^4} - \frac{12}{(1-z)^3} + \frac{24}{(1-z)^4}\ln\frac{1}{1-z} - \frac{8}{(1-z)^3}\ln\frac{1}{1-z} + \frac{8}{(1-z)^4}\ln^2\frac{1}{1-z}.$$

The integrating factor is $(1-z)^2$. The solution confirms that

$$q^{[2]}(z) = \frac{6}{(1-z)^3} + \frac{8}{(1-z)^3}\ln\frac{1}{1-z} + \frac{8}{(1-z)^4}\ln^2\frac{1}{1-z} + \frac{8}{(1-z)^2} - \frac{12}{(1-z)^2}\ln\frac{1}{1-z} - \frac{4}{(1-z)^2}\ln^2\frac{1}{1-z}.$$

Exercise 3.68

Let’s start with the sum

$$q^{[2]}(z)+q^{[1]}(z)= \frac{6}{(1-z)^3} +\frac{8}{(1-z)^3}\ln\frac1{1-z} +\frac{8}{(1-z)^4}\ln^2\frac1{1-z} +\frac{8}{(1-z)^2} -\frac{10}{(1-z)^2}\ln\frac1{1-z} -\frac{4}{(1-z)^2}\ln^2\frac1{1-z}.$$

The following list shows the necessary coefficient extraction toolbox. The first identity is a left-shifted elementary OGF from Table 3.1. The second identity is given in Exercise 3.28. The last one is derived by differentiating both sides of the second identity w.r.t. $\alpha$.

• $[z^N]\frac1{(1-z)^\alpha}=\binom{N+\alpha-1}{\alpha-1}$

• $[z^N]\frac{1}{(1-z)^\alpha}\ln\frac1{1-z} =\binom{N+\alpha-1}{\alpha-1}\bigl(H_{N+\alpha-1}-H_{\alpha-1}\bigr)$.

• $[z^N]\frac{1}{(1-z)^\alpha}\ln^2\frac1{1-z} =\binom{N+\alpha-1}{\alpha-1}\Bigl(\bigl(H_{N+\alpha-1}-H_{\alpha-1}\bigr)^2-\bigl(H_{N+\alpha-1}^{(2)}-H_{\alpha-1}^{(2)}\bigr)\Bigr)$.

Now it’s a matter of getting coefficients for each summand and consolidating the result. Recall that variance is defined as

$$\operatorname{var}(C_N)=[z^N](q^{[2]}(z)+q^{[1]}(z))-([z^N]q^{[1]}(z))^2.$$

Using a computer algebra tool we can confirm the exact expression for the variance given in Theorem 3.9.

Exercise 3.69

$$\begin{align*} \sum_{n,k \ge 0} \binom{n}{k} u^k \frac{z^n}{n!} &= \sum_{n \ge 0} \left( \sum_{k \ge 0} \binom{n}{k} u^k \right) \frac{z^n}{n!} \\ &= \sum_{n \ge 0} (1+u)^n \frac{z^n}{n!} \\ &= \sum_{n \ge 0} \frac{((1+u)z)^n}{n!} \\ &= e^{(1+u)z} && \text{(see Table 3.4)}. \end{align*}$$

$$\begin{align*} \sum_{n,k \ge 0} k! \left[ \begin{matrix} n \\ k \end{matrix} \right] u^k \frac{z^n}{n!} &= \sum_{k \ge 0} k! u^k \left( \sum_{n \ge 0} \left[ \begin{matrix} n \\ k \end{matrix} \right] \frac{z^n}{n!} \right) \\ &= \sum_{k \ge 0} k! u^k \left[ \frac{1}{k!} \left( \ln \frac{1}{1-z} \right)^k \right] && \text{(see Table 3.6)} \\ &= \sum_{k \ge 0} \left(u \ln \frac{1}{1-z} \right)^k \\ &= \frac{1}{1 - u \ln \left( \frac{1}{1-z} \right)}. \end{align*}$$

$$\begin{align*} \sum_{n,k \ge 0} k! \left\{ \begin{matrix} n \\ k \end{matrix} \right\} u^k \frac{z^n}{n!} &= \sum_{k \ge 0} k! u^k \left( \sum_{n \ge 0} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} \frac{z^n}{n!} \right) \\ &= \sum_{k \ge 0} k! u^k \left[ \frac{1}{k!} (e^z - 1)^k \right] && \text{(see Table 3.6)} \\ &= \sum_{k \ge 0} (u (e^z - 1))^k \\ &= \frac{1}{1 - u(e^z - 1)}. \end{align*}$$

Exercise 3.70

$$\underbrace{\frac{z^k}{(1-z)^{k+1}}}_{\sum_n\binom{n}{k}z^n} = \underbrace{\frac{z^{k+1}}{(1-z)^{k+1}}}_{\sum_n\binom{n-1}{k}z^n}+\underbrace{\frac{z^k}{(1-z)^k}}_{\sum_n\binom{n-1}{k-1}z^n}.$$

By matching coefficients on both sides, we obtain the desired identity.

Exercise 3.71

$$\begin{align*} \sum_{k} {n \brack k}u^k &= u^{\overline{n}} = u(u+1)(u+2)\cdots(u+n-1) \\ &= \underbrace{u(u+1)\cdots(u+n-2)}_{\sum_{k}{n-1 \brack k}u^k} \cdot (u + n - 1) \\ &= (n-1)\sum_{k}{n-1 \brack k}u^k + u\sum_{k}{n-1 \brack k}u^k \\ &= \sum_{k}(n-1){n-1 \brack k}u^k + \sum_{k}{n-1 \brack k-1}u^k. \end{align*}$$

By matching coefficients on both sides, we obtain the desired identity.

Exercise 3.72

$$\begin{align*} \underbrace{\frac{z^k}{(1-z)(1-2z)\dots(1-kz)}}_{\sum_n{n \brace k}z^n} = \underbrace{\frac{kz^{k+1}}{(1-z)(1-2z)\dots(1-kz)}}_{\sum_nk{n-1 \brace k}z^n}+\underbrace{\frac{z^k}{(1-z)(1-2z)\dots(1-(k-1)z)}}_{\sum_n{n-1 \brace k-1}z^n}. \end{align*}$$

By matching coefficients on both sides, we obtain the desired identity.

Exercise 3.73

In both cases, we assume nothing about $m$, so the conclusions apply for all $m>1$.

Setting $x = 0$ in the definition yields

$$B_m(0) = \sum_k \binom{m}{k} B_k \cdot 0^{m-k} = \binom{m}{m} B_m \cdot 1 = B_m.$$

Considering the EGF of the Bernoulli polynomials for $x=1$ and using Table 3.6 gives

$$\begin{align*} \sum_{m\ge0} B_m(1) \frac{z^m}{m!} &= \frac{z e^z}{e^z - 1} \\ &=\frac{z}{e^z - 1} + z \\ &= \sum_{m\ge0} B_m \frac{z^m}{m!} + z. \end{align*}$$

By matching coefficients on both sides, we have

• $B_0(1)=B_0$

• $B_1(1) = B_1 + 1$

• $B_m(1) = B_m$ for $m>1$.

Exercise 3.74

We start with the EGF of the Bernoulli numbers (see Table 3.6)

$$f(z)=\frac{z}{e^z - 1} = \sum_{m\ge0} B_m \frac{z^m}{m!}.$$

Let’s define $g(z)=f(z)+z/2$. It is easy to show that $g(-z)=g(z)$, which means $g(z)$ is even. Expanding $g(z)$ gives

$$\begin{align*} g(z) &= \sum_{m\ge0} B_m \frac{z^m}{m!} + \frac{z}{2} \\ &= B_0 + B_1 z + \sum_{m\ge 2} B_m \frac{z^m}{m!} + \frac{z}{2} \\ &= 1 + \left(-\frac{1}{2}\right) z + \frac{z}{2} + \sum_{m\ge 2} B_m \frac{z^m}{m!} \\ &= 1 + \sum_{m\ge 2} B_m \frac{z^m}{m!}. \end{align*}$$

Since $g(z)$ is even, its series expansion contains only even powers of $z$. Therefore, $B_k$ is zero for $k$ odd, $k \ge 3$. This concludes the proof.

Exercise 3.75

This exercise is a simple generalization of the DGF for even numbers from the book. Observe that a positive integer $N$ ending in $k \ge 0$ zeros has the form $N=2^kM$, where $M \ge 1$. This gives

$$\sum_{\substack{N \ge 1\\\text{ends in $k$ 0s}}} \frac{1}{N^z}=\sum_{N \ge 1} \frac{1}{(2^kN)^z}=\frac{1}{2^{kz}}\zeta(z).$$

Exercise 3.76

The previous exercise already provides much of the answer, we just need to sum up DGFs for all $k \ge 1$, since absence of a kernel component entails a count of zero (odd number). This gives

$$\sum_{N\ge1}\frac{\psi_N}{N^z}=\sum_{k\ge1}\frac{1}{2^{kz}}\zeta(z)=\zeta(z)\sum_{k\ge1}\left(\frac{1}{2^{z}}\right)^k=\frac{\zeta(z)}{2^z-1}.$$

Exercise 3.77

We want to have kernel components only for perfect squares. Using the same idea as for even numbers (see also Exercise 3.75), we have

$$\sum_{N \ge 1}\frac{1}{(N^2)^z}=\sum_{N \ge 1}\frac{1}{N^{2z}}=\zeta(2z).$$

Exercise 3.78

This directly follows from the definition of the Lambert series.