Chapter 5

Exercise 5.1 🌟

This exercise illustrates the symbolic method and its efficacy in simplifying the analysis of combinatorial structures. A formal language is employed to define the combinatorial class, which corresponds to an associated generating function. Extracting coefficients then involves identifying the relevant values pertaining to the object under consideration.

Consider the class $G$ of binary strings having no three consecutive 0 bits. Such strings are either ∊, a single 0, a double 00, or 1 or 01 or 001 followed by a string with no three consecutive 0 bits. Symbolically, this argument gives the combinatorial construction

$$G = ∊ + Z_0 + Z_0×Z_0+(Z_1 + Z_0 × Z_1+Z_0×Z_0 × Z_1) × G.$$

Theorem 5.1 allows us to translate this immediately into a formula for the generating function $G(z)$ that enumerates such strings:

$$G(z) = 1 + z +z^2 + (z + z^2+z^3)G(z) \\ \therefore G(z)=\frac{1+z+z^2}{1-z-z^2-z^3}.$$

The numerator is consisted of shift factors, as in the example from the book. The denominator is a well-known polynomial describing Tribonacci numbers (see Exercise 4.18). Therefore, the number of strings of length $N$ with no three consecutive 0 bits is $T_N+T_{N+1}+T_{N+2}=T_{N+3}$, a sequence registered under A000073.

Exercise 5.2

We can express our class $G$ symbolically as

$$G=SEQ(Z_1) \times SEQ(Z_0).$$

This gives

$$G(z)=\frac{1}{(1-z)^2} \\[0.2cm] \therefore [z^N]G(z)=N+1.$$

Exercise 5.3

This is a simple variation of the example from the book. The class $U$ matches the construction

$$U = Z_\square + Z_\blacksquare × U × U.$$

We translate both $Z$ classes as $z$ to get

$$U(z)=z+zU(z)^2 \\[0.2 cm] \therefore U(z)=\frac{1-\sqrt{1-4z^2}}{2z}.$$

It’s always wise to check our OGF. For example, WolframAlpha can expand the generating function with series \frac{1-\sqrt{1-4z^2}}{2z} to order 9.

Exercise 5.4

The total number of binary trees with $N$ nodes is given by the $N$th Catalan number. We need to figure out the number of binary trees with $N$ nodes without superleaves. The ratio of these numbers specifies the required fraction. The recursive decomposition of our combinatorial structure is

$$T=Z_\square+Z_\blacksquare \times T \times T-Z_\blacksquare \times Z_\blacksquare \times Z_\blacksquare.$$

Notice that we must exclude a symmetric tree with 3 internal nodes that produces a superleaf at the root. This translates to

$$T^\blacksquare(z)=1+zT^\blacksquare(z)^2-z^3 \\[0.2 cm] \therefore T^\blacksquare(z)=\frac{1-\sqrt{1-4z+4z^4}}{2z}.$$

With the help of WolframAlpha we can confirm that the coefficients divided by the Catalan numbers produce the desired ratios. There is only one caveat, that trees with less than 3 nodes never produce a superleaf, so instead of zero their ratios should give one.

Exercise 5.5 🌟

This exercise introduces a new operation set of, where $B$ is defined as the collection of all finite subsets of $A$.

We can regard $B$ as a series of independent decisions. The combinatorial construction for a decision $D$ about any single object of size $n$ in $A$ is

$$D=\epsilon+Z_n \implies D(z)=1+z^n.$$

In other words, we either skip it or include it in our collection. Now, if we have $A_n$ distinct objects of size $n$ in $A$, then we make such decisions for every object. The construction is simply a sequence of $A_n$ decisions that translates to $(1+z^n)^{A_n}$. Finally, the whole product comes from repeating this endeavor for every possible size $n$.

The second part of the proof follows from turning a product into a sum by taking a logarithm and employing Taylor expansion of $\ln(1+x)$. This gives

$$\begin{align*} B(z) &= \prod_{n \ge 1}(1+z^n)^{A_n} \\ &= \exp\bigg\{ \sum_{n \ge 1} A_n\ln(1+z^n)\bigg\} \\ &= \exp\bigg\{ \sum_{n \ge 1} A_n(z^n-z^{2n}/2+z^{3n}/3- \cdots)\bigg\} \qquad \text{(see section 4.2 in the book)} \\ &= \exp\bigg\{\sum_{n \ge 1} A_nz^n - \frac{1}{2}\sum_{n \ge 1} A_n(z^2)^n + \frac{1}{3}\sum_{n \ge 1} A_n(z^3)^n - \cdots \bigg\} \\ &= \exp\bigg\{A(z) - \frac{1}{2}A(z^2) + \frac{1}{3}A(z^3) - \cdots\bigg\}. \end{align*}$$

Exercise 5.6 🌟

This exercise introduces a new operation multiset of, where $B$ is defined as the collection of all finite multisets of $A$ (subsets with repetitions allowed).

We can regard $B$ as a series of independent decisions. The combinatorial construction for a decision $D$ about any single object of size $n$ in $A$ is

$$D=\epsilon+Z_n+Z_n \times Z_n+Z_n \times Z_n \times Z_n + \cdots = SEQ(Z_n) \implies D(z)=\frac{1}{1-z^n}.$$

In other words, we either skip it, include it once, or twice, or any number of times (infinite geometric series). Now, if we have $A_n$ distinct objects of size $n$ in $A$, then we make such decisions for every object. The construction is simply a sequence of $A_n$ decisions that translates to $1/(1-z^n)^{A_n}$. Finally, the whole product comes from repeating this endeavor for every possible size $n$.

For the second part of the proof, we follow the same approach as in the previous exercise

$$\begin{align*} B(z) &= \prod_{n \ge 1}\frac{1}{(1-z^n)^{A_n}} \\ &= \exp\bigg\{- \sum_{n \ge 1} A_n\ln(1-z^n)\bigg\} \qquad \text{($\ln 1=0$)} \\ &= \exp\bigg\{-\sum_{n \ge 1} A_n(-z^n-z^{2n}/2-z^{3n}/3- \cdots)\bigg\} \qquad \text{(see section 4.2 in the book)} \\ &= \exp\bigg\{\sum_{n \ge 1} A_nz^n + \frac{1}{2}\sum_{n \ge 1} A_n(z^2)^n + \frac{1}{3}\sum_{n \ge 1} A_n(z^3)^n + \cdots \bigg\} \\ &= \exp\bigg\{A(z) + \frac{1}{2}A(z^2) + \frac{1}{3}A(z^3) + \cdots\bigg\}. \end{align*}$$

Exercise 5.7

This is a variation of the generalized derangements problem. The combinatorial construction is

$$P^*_{ODD} = SET(CYC_1(Z)+CYC_3(Z)+CYC_5(Z)+\cdots).$$

The EGF associated with the combinatorial class $P^*_{ODD}$ is

$$\begin{align*} P^*_{ODD}(z) &= exp\bigg\{z+\frac{z^3}{3}+\frac{z^5}{5}+\cdots\bigg\} \\[0.3 cm] &=exp\bigg\{\ln \frac{1}{1-z}-\frac{z^2}{2}-\frac{z^4}{4}-\cdots\bigg\} \\[0.3 cm] &=\frac{e^{-\sum_{k \ge 1} \frac{z^{2k}}{2k}}}{1-z} \\[0.3 cm] &=\frac{e^{\frac{1}{2}\ln (1-z^2)}}{1-z} \\[0.3 cm] &=\frac{\sqrt{1-z^2}}{1-z}= \sqrt{\frac{1+z}{1-z}}. \end{align*}$$

Exercise 5.8

Symbolically, we have the construction

$$G=SEQ(CYC(Z)),$$

which, by the cycle and sequence rules in Theorem 5.2, gives the EGF

$$G(z)=\frac{1}{1-\ln \frac{1}{1-z}}=\frac{1}{1+\ln (1-z)}.$$

Exercise 5.9

Symbolically, we have the construction that omits an empty sequence

$$G=CYC(SEQ_{\ge 1}(Z)),$$

which, by the cycle and sequence rules in Theorem 5.2, gives the EGF

$$G(z)=\ln \frac{1}{1-\frac{z}{1-z}}=\ln \frac{1-z}{1-2z}.$$

Exercise 5.10

The proof is available on Analytic Combinatorics by RS and PF book’s website (see slide 12).

Exercise 5.11

The first part of the proof is

$$\begin{align*} \sum_{c \in A + B} \frac{z^{|c|}}{|c|!} u^{\text{cost}(c)} &= \sum_{a \in A} \frac{z^{|a|}}{|a|!} u^{\text{cost}(a)} + \sum_{b \in B} \frac{z^{|b|}}{|b|!} u^{\text{cost}(b)} \\ &= A(z, u)+B(z, u). \end{align*}$$

For the labeled product $A \star B$, we have

$$\begin{align*} \sum_{c \in A \star B} \frac{z^{|c|}}{|c|!} u^{\text{cost}(c)} &= \sum_{a \in A} \sum_{b \in B} \binom{|a| + |b|}{|a|} \frac{z^{|a|+|b|}}{(|a|+|b|)!} u^{\text{cost}(a) + \text{cost}(b)} \\ &= \sum_{a \in A} \sum_{b \in B} \frac{(|a| + |b|)!}{|a|!|b|!} \frac{z^{|a|}z^{|b|}}{(|a|+|b|)!} u^{\text{cost}(a)} u^{\text{cost}(b)} \\ &= \left( \sum_{a \in A} \frac{z^{|a|}}{|a|!} u^{\text{cost}(a)} \right) \left( \sum_{b \in B} \frac{z^{|b|}}{|b|!} u^{\text{cost}(b)} \right) = A(z, u)B(z, u). \end{align*}$$

Having established both the labelled summation and product, the remainder of the proof proceeds identically to that presented for Theorem 5.2.

Exercise 5.12

$$B_u(z,1)=\frac{z}{(1-(1+u)z)^2}\bigg|_{u=1}=\frac{z}{(1-2z)^2}=\frac{1}{2}\,\frac{2z}{(1-2z)^2}.$$

Thus, the average number of 1 bits in a random bitstring of length $N$ is

$$\frac{[z^N]B_u(z,1)}{2^N}=\frac{N2^{N-1}}{2^N}=N/2.$$

Exercise 5.13

Symbolically, we have the construction (see the book)

$$G = \epsilon + Z_0 + (Z_1 + Z_0 × Z_1) × G.$$

We should translate each $Z_1$ as $uz$, to get

$$G(z,u)=\frac{1+z}{1-uz(1+z)}.$$

The cumulative number of 1 bits is

$$G_u(z,1)=\frac{z(1+z)^2}{(1-uz(1+z))^2}\bigg|_{u=1}=\frac{1+z}{(1-z-z^2)^2} - \frac{1+z}{1-z-z^2}.$$

The second summand is an OGF for $F_{N+2}$. The first summand can be rewritten as

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

The OGF inside parenthesis is a self-convolution of Fibonacci numbers (there is a closed-form solution). Hence, after combining all components and simplifying, we get that the average number of 1 bits in a random bitstring of length $N$ having no 00 is

$$\frac{[z^N]G_u(z,1)}{F_{N+2}}=\frac{4NF_{N+2}-(N+2)F_N}{5F_{N+2}}.$$

Exercise 5.14

The book contains the formula for the number of derangements $D_N$. We can tweak the combinatorial construction, by marking cycles with $u$, to derive the cumulative generating function

$$D_u(z, 1) = \underbrace{\frac{e^{-z}}{1-z}}_{\sum_{N \ge 0}D_N\frac{z^N}{N!}} \underbrace{\left( \ln \frac{1}{1-z} - z \right)}_{\sum_{N \ge 2}(N-1)!\frac{z^N}{N!}} \\[0.3 cm] \therefore \frac{N! [z^N] D_u(z, 1)}{D_N} = \frac{\sum_{k=2}^N \binom{N}{k} (k-1)! D_{N-k}}{D_N}.$$

Informally, we already know from the book that in a random permutation, the average number of cycles is $H_N$. Let $X$ be a random variable counting the number of fixed points (unary cycles) in a random permutation with $N$ elements. We have $X=\sum_kX_k$, where $X_k$ is an indicator random variable telling whether the $k$th element remains on its current position. Apparently,

$$\Pr\{X_k=1\}=1/N \implies \mathbb{E}[X]=\sum_k \Pr\{X_k=1\}=1.$$

Therefore, the average number of cycles in a random derangement for large $N$ is $\sim H_N-1$. Of course, this back-of-the-envelope calculation makes some unjustified assumptions about independence of events, but gives an indication about what happens at the limit.

Exercise 5.15 🌟

This exercise illustrates the symbolic method for parameters in great detail.

The total number of binary trees with $N$ nodes is given by the $N$th Catalan number. The recursive decomposition of our combinatorial structure is

$$T=\epsilon+Z_\blacksquare+2Z_\blacksquare \times (T - \epsilon)+Z_\blacksquare \times (T - \epsilon)^2.$$

In plain English, a tree is one of the following:

1. An empty tree (external node).

2. A leaf.

3. A root with one non-empty subtree (either left or right).

4. A root with two non-empty subtrees; we must mark this root.

This gives the following BGF

$$\begin{align*} T(z,u) &= 1 + z + 2z(T(z,u)-1) + uz(T(z,u)-1)^2 \\[0.3cm] &= \frac{1 - 2z(1-u) - \sqrt{1 - 4z + 4z^2(1-u)}}{2uz}. \end{align*}$$

Finding a partial derivative directly is quite complicated, even with a help of a computer algebra system. Instead, we will use the functional equation. By differentiating it implicitly, we get

$$T_u(z,u) = 2zT_u(z,u) + z(T(z,u)-1)^2 + 2uz(T(z,u)-1)T_u(z,u) \\[0.3cm] \therefore T_u(z,1)= \frac{z(T(z,1)-1)^2}{1 - 2zT(z,1)}= \frac{z(T(z,1)-1)^2}{\sqrt{1-4z}}=\frac{z^3 T(z,1)^4}{\sqrt{1-4z}}.$$

Recall that $T(z)=T(z,1)=1+zT(z,1)^2$, a standard equation for binary trees. This enables the last simplification. Extracting the coefficient is trivial by employing equation (5.72) from the book Concrete Mathematics by Graham, Knuth and Patashnik

$$[z^N]T_u(z,1)=\binom{2N-2}{N-3} .$$

The aforementioned book is an indispensable source when dealing with convoluted equations, as it contains numerous identities, like the one we have just used.

The average number of internal nodes in a binary tree of size $N$ with both children internal is

$$\frac{[z^N]T_u(z,1)}{[z^N]T(z,1)}= \frac{(N-1)(N-2)}{2(2N-1)}.$$

The formula checks perfectly for trees in Figure 5.2.

Exercise 5.16

This is a variation of the previous exercise. The only difference is that we must mark the internal node connected to a single non-empty subtree. This gives

$$\begin{align*} T(z,u) &= 1 + z + 2uz(T(z,u)-1) + z(T(z,u)-1)^2 \\[0.3cm] &=1-u + \frac{1 - \sqrt{(1-2z(u+1))(1-2z(u-1))}}{2z}. \end{align*}$$

Following the same approach as previously, we arrive at

$$T_u(z,1) = \frac{2z^2 T(z,1)^2}{\sqrt{1-4z}}.$$

Using the same identity as before, we get

$$\frac{[z^N]T_u(z,1)}{[z^N]T(z,1)}=\frac{2 \dbinom{2n-2}{n-2}}{\cfrac{1}{n+1} \dbinom{2n}{n}} =\frac{n^2-1}{2n-1}.$$

The formula checks perfectly for trees in Figure 5.2.

Exercise 5.17 🌟

This exercise demonstrates how the symbolic method helps in finding various moments that would be very difficult to attain by other means.

The explicit formula for $T(z,u)$ is

$$\boxed{T(z,u) = \frac{1 - \sqrt{1 - 4z + 4z^2(1-u)}}{2z}}.$$

We should calculate variance as described in Table 3.5, so we need a second partial derivative

$$\left. \frac{\partial^2 T(z,u)}{\partial u^2} \right|_{u=1} = \frac{2z^3}{(1-4z)^{3/2}}.$$

To find $p''_n(1)$ we should use the following identities (see the previous two exercises)

$$\frac{1}{\sqrt{1-4z}} = \sum \binom{2k}{k} z^k \qquad \text{(by equation (5.72) with $r=0$)} \\[0.3cm] \frac{1}{(1-4z)^{3/2}} = \sum \frac{k+1}{2} \binom{2k+2}{k+1} z^k \qquad \text{(by the index multiply operation)}.$$

This gives (after right-shifting 3 positions due to $z^3$ and multplying by two)

$$p''_n(1)=(n-2)\binom{2n-4}{n-2}.$$

Plugging all components (see also the book) into the variance equation and simplifying gives

$$\sigma^2 = \frac{n(n+1)(n-1)(n-2)}{2(2n-1)^2(2n-3)}.$$

Exercise 5.18

We can employ the general Leibniz rule to get

$$[z^N]\frac{e^{-z}}{1-z}=\frac{1}{N!}\left(\sum_{0 \le k \le N}\binom{N}{k} (-1)^ke^{-z} (N-k)!(1-z)^{-(N-k)-1}\right)\bigg|_{z=0}=\sum_{0 \le k \le N} \frac{(-1)^k}{k!}.$$

Exercise 5.19

The root with the smallest modulus is $1/\phi$, so $\beta=\phi$. It is a simple algebra to show that

$$[z^N]\frac{f(z)}{g(z)}\sim\frac{\phi^{N+2}}{\sqrt 5}.$$

The book incorrectly has $N$ in the exponent instead of $N+2$.

Exercise 5.20

According to Exercise 2 $A(z)=\frac{1}{(1-z)^2}$. Here, $\beta=1$, $\nu=2$, $f(1)=1$ and $g''(1)=2$. Based on Theorem 4.1, an approximation for the number of bitstrings having no occurrence of 01 is

$$[z^N]\frac{f(z)}{g(z)}\sim N.$$

Exercise 5.21 🌟

This exercise showcases the methodology of using the radius-of-convergence bounds.

Let $f(z) = \exp\left(\frac{z}{1-z}\right)$. For the power series expansion of the exponent to converge, we must restrict our domain to $|z|<1$ (the criterion for a geometric series to converge). Therefore,

$$[z^n]f(z) \le \underset{x \in (0,1)}{\min} \frac{\exp\left(\frac{x}{1-x}\right)}{x^n}.$$

We should set $x$ to balance the growth of the numerator and the denominator as $n$ grows. Since we must prove that the bound is a function of $\sqrt n$, let’s try

$$x = 1 - \frac{1}{\sqrt{n}}.$$

This is a bit reminiscent of the trial and error process in finding particular solutions of nonhomogeneous differential equations.

We have

$$\exp\left(\frac{x}{1-x}\right) = \exp\left(\frac{1 - \frac{1}{\sqrt{n}}}{\frac{1}{\sqrt{n}}}\right) = \exp(\sqrt{n} - 1),$$

and

$$\frac{1}{x^n} = \left(1 - \frac{1}{\sqrt{n}}\right)^{-n}= \left(1 - \frac{1}{\sqrt{n}}\right)^{\sqrt n (-\sqrt n)} \le \exp(\sqrt n + 1).$$

See Exercise 4.39 to understand the last step. All in all, this concludes the proof

$$[z^n]f(z) \le \exp(\sqrt{n} - 1) \cdot \exp(\sqrt{n} + 1) = \exp(2\sqrt{n}).$$

We aren’t claiming that $C=2$ is optimal, just that there is such a constant.

Exercise 5.22

This is a variation of the previous exercise. Let $f(z)=\prod_{k=1}^\infty (1-z^k)^{-1}$. The radius of convergence is $|z|<1$. To deal with the infinite product, we take the natural logarithm and use the Taylor series expansion $\ln(1-x) = -\sum_{j=1}^\infty \frac{x^j}{j}$. This gives

$$\begin{align*} \ln f(x) &= -\sum_{k=1}^\infty \ln(1-x^k) \\ &= \sum_{k=1}^\infty \sum_{j=1}^\infty \frac{x^{jk}}{j} \\ &= \sum_{j=1}^\infty \frac{1}{j} \sum_{k=1}^\infty (x^j)^k && \text{(by absolute convergence of sums)} \\ &= \sum_{j=1}^\infty \frac{1}{j} \frac{x^j}{1-x^j}. \end{align*}$$

To bound this, we can use a standard algebraic identity (recall that $0 <x<1$)

$$1 - x^j = (1-x)(1 + x + x^2 + \dots + x^{j-1}) \ge (1-x) j x^{j-1}.$$

Substituting this back into our series

$$\frac{x^j}{1-x^j} \le \frac{x^j}{(1-x) j x^{j-1}} = \frac{x}{j(1-x)} \le \frac{1}{j(1-x)}.$$

We have

$$\ln f(x) \le \sum_{j=1}^\infty \frac{1}{j} \left( \frac{1}{j(1-x)} \right) = \frac{1}{1-x} \sum_{j=1}^\infty \frac{1}{j^2} \le \frac{\pi^2}{6(1-x)} \\ \therefore f(x) \le \exp\left( \frac{\pi^2}{6(1-x)} \right).$$

We had already encountered the Basel problem, which was applied above. This gives

$$[z^n]f(z) \le \underset{x \in (0,1)}{\min} \frac{f(x)}{x^n} \le \underset{x \in (0,1)}{\min}\exp\left( \frac{\pi^2}{6(1-x)} - n \ln x \right).$$

Let’s attempt with the same candidate

$$x= 1 - \frac{1}{\sqrt{n}}.$$

We have

$$\frac{\pi^2}{6(1-x)} = \frac{\pi^2}{6 \left(\frac{1}{\sqrt{n}}\right)} = \frac{\pi^2}{6} \sqrt{n},$$

and

$$-n \ln x = -n \ln\left(1 - \frac{1}{\sqrt{n}}\right) \le n\underbrace{\left( \frac{1}{\sqrt{n}} + \frac{1}{n} \right)}_{\overset{\text{Taylor expansion of}}{-\ln(1-x)}} = \sqrt{n} + 1.$$

Our overall bound becomes

$$[z^n]f(z) \le \exp\left( \left( \frac{\pi^2}{6} + 1 \right) \sqrt{n} + 1 \right)=O(\exp(C\sqrt n)).$$

For a more precise bound, take a look at the Wikipedia article about the partition function.

Exercise 5.23

The GF from Exercise 7 is

$$P^*_{ODD}(z) = \sqrt{\frac{1+z}{1-z}}.$$

Theorem 5.5 immediately gives the result with $\alpha=1/2$

$$[z^N]P^*_{ODD}(z) \sim \frac{\sqrt 2}{\sqrt {\pi N}}= \frac{1}{\sqrt {\pi N/2}}.$$

Exercise 5.24

For the special case $f(z) \equiv1$, the extension of Theorem 5.5 to three terms is available on Analytic Combinatorics by RS and PF book’s website (see slide 14). We will reuse this asymptotic series for deriving a more precise version of Theorem 5.5 below (when handling the term $(1-z)^{-(\alpha - k)}$).

The asymptotic expansion follows from expanding $f(z)$ in a Taylor series about $z=1$

$$f(z) = \sum_{k=0}^{\infty} \frac{f^{(k)}(1)}{k!} (z-1)^k=\sum_{k=0}^{\infty} \frac{f^{(k)}(1)}{k!} (-1)^k(1-z)^k.$$

This gives

$$\frac{f(z)}{(1-z)^\alpha} = \sum_{k=0}^{\infty} (-1)^k \frac{f^{(k)}(1)}{k!} (1-z)^{k-\alpha} = \sum_{k=0}^{\infty} (-1)^k \frac{f^{(k)}(1)}{k!} (1-z)^{-(\alpha - k)}.$$

Substituting the first few terms $k \in [0,2]$ and collecting powers of $n$ gives

$$\begin{align*} [z^n] \frac{f(z)}{(1-z)^\alpha} &= \frac{n^{\alpha-1}}{\Gamma(\alpha)}\,f(1) \\ &\quad + \frac{n^{\alpha-2}}{\Gamma(\alpha-1)}\left( \frac{\alpha}{2}\,f(1) - f'(1) \right) \\ &\quad + \frac{n^{\alpha-3}}{\Gamma(\alpha-2)}\left( \frac{\alpha(3\alpha-1)}{24}\,f(1) - \frac{\alpha-1}{2}\,f'(1) + \frac{1}{2}\,f''(1) \right) \\ &\quad + O\!\left(n^{\alpha-4}\right). \end{align*}$$

Exercise 5.25

We follow the steps from the proof of Theorem 5.5. It is a matter to analyze the convolution

$$\begin{align*} [z^n]f(z) \ln \frac{1}{1-z} &= \frac{f_0}{n}+\frac{f_1}{n-1}+ \cdots +\frac{f_{n-1}}{1} \\ &= \frac{1}{n} \left(f_0+\frac{f_1}{1-1/n}+\frac{f_2}{1-2/n}+ \cdots +\frac{f_{k_0}}{1-k_0/n}+\cdots+\frac{f_{n-1}}{1/n}\right) \\ &\sim \frac{1}{n} \sum_k f_k = \frac{f(1)}{n}. \end{align*}$$

We have split the sum into two parts around the threshold value $k_0$; in spirit, aligned with the Laplace method for sums. A good choice is $k_0 = \lfloor \sqrt{n} \rfloor$; the head of the sum captures all of $f(1)$, where the denominators tend to one.

Assuming that $f(z)$ converges in a radius $r>1$, all terms indexed larger than $k_0$ tend to zero exponentially fast (recall that $[z^n]f(z)=O(r^{-n})$). Therefore, the tail sum is negligible.

Exercise 5.26

This is a variation of the previous exercise. From Table 3.1 we know that

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

We setup a convolution, just like in the proof of Theorem 5.5 from the book

$$[z^n] f(z) \left( \frac{1}{1-z} \ln \frac{1}{1-z} \right) = \sum_{k=0}^{n} f_k H_{n-k}.$$

We split the sum in the same way as previously, so the leading part is

$$\sum_{k=0}^{k_0} f_k H_{n-k} \sim H_n \sum_{k=0}^{k_0} f_k \sim f(1) \ln n.$$

This is true, since $H_{n-k} \sim H_n \sim \ln n$ for large $n$ and $k\le k_0=\sqrt n$. The tail sum is negligible for the same reason as in the previous exercise. Therefore,

$$[z^n] f(z) \frac{1}{1-z} \ln \frac{1}{1-z} \sim f(1) \ln n.$$