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}$$. ***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 🌟 {% hint style="success" %} This exercise demonstrates how to extract coefficients from OGFs. {% endhint %} 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]\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](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](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/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]\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 🌟 {% hint style="success" %} 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. See also the next exercise. {% endhint %} The solution is available as part of the [course material](https://aofa.cs.princeton.edu/online/slides/AA03-GFs.pdf) on the book’s website (see slide 13). ## Exercise 3.5 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](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/A\(z\)B\(z\)) = \sum\_{k=M}^{N-1} \binom{k}{M} \frac{1}{N-k}. $$ *** Another possible grouping is $$ \underbrace{ \frac{z^M}{(1-z)^M} }*{C(z)} \cdot \underbrace{ \frac{1}{1-z} \ln \frac{1}{1-z} }*{D(z)}. $$ Again, both are essentially elementary OGFs from Table 3.1. We have by definition $$ [z^N](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/C\(z\)D\(z\)) = \sum\_{k=M}^{N-1} \binom{k-1}{M-1} H\_{N-k}. $$ *** Another possible grouping is $$ \underbrace{ \frac{z^{M-1}}{(1-z)^{M-1}} }*{E(z)} \cdot \underbrace{ \frac{z}{(1-z)^2} \ln \frac{1}{1-z} }*{F(z)}. $$ Again, both are essentially elementary OGFs from Table 3.1. We have by definition $$ [z^N](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/E\(z\)F\(z\)) = \sum\_{k=M-1}^{N-1} \binom{k-1}{M-2} (N-k)(H\_{N-k}-1). $$ *** Looking at the initial OGF, we see that it is $$ z^M \cdot \underbrace{\frac{1}{(1-z)^{M+1}}}*{P(z)} \cdot \underbrace{\ln \frac{1}{1-z}}*{Q(z)}. $$ Therefore, $$[z^N](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/A\(z\)B\(z\)) =[z^{N-M}](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/P\(z\)Q\(z\))$$. The book [Concrete Mathematics: A Foundation for Computer Science (2nd ed.)](https://www-cs-faculty.stanford.edu/~knuth/gkp.html) contains an identity (7.43) $$ P(z)Q(z)=\sum\_{N \ge 0} (H\_{M+N}-H\_M)\binom{M+N}{N}z^N. $$ *** By combining all components, we get $$ \boxed{\sum\_{k=M}^{N-1} \binom{k}{M} \frac{1}{N-k} = \sum\_{k=M}^{N-1} \binom{k-1}{M-1} H\_{N-k} =\sum\_{k=M-1}^{N-1} \binom{k-1}{M-2} (N-k)(H\_{N-k}-1)= \binom{N}{M}(H\_N - H\_M)}. $$ ## Exercise 3.6 See the remark in [Exercise 3.1](#exercise-3.1) how to interpret the definition of the sequence. 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}=\frac{ \ln^2(1-z)}{z^2}. $$ ## Exercise 3.7 🌟 {% hint style="success" %} This exercise shows an advanced case study of reconstructing the corresponding OGF. {% endhint %} Assume the same interpretation of this definition as in [Exercise 3.1](#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](https://en.wikipedia.org/wiki/Dilogarithm). 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 🌟 {% hint style="success" %} This exercise shows an advanced coefficient extraction case study. {% endhint %} 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 the previous two exercises $$ \[z^N]A(z)=\sum\_{0\[z^N]\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\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!}}$$. ***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 🌟 {% hint style="success" %} This exercise demonstrates how to extract coefficients from EGFs. {% endhint %}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 immediately gives $$N!\[z^N]A(z)=N!H\_N$$. ***A(z)=\ln^2 \frac{1}{1-z}
Using the same reasoing (see [Exercise 3.8](#exercise-3.8)) we have $$N!\[z^N]A(z)=2(N-1)!H\_{N-1}$$ for $$N>1$$. For $$N \le1$$ the coefficients are zeros. ***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 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](https://en.wikipedia.org/wiki/Linear_differential_equation#First-order_equation_with_variable_coefficients). 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 🌟 {% hint style="success" %} This exercise introduces the Laplace transform for converting from the EGF for a sequence to the OGF for the same sequence. {% endhint %} By definition $$A(z)=\sum\_{k\ge 0}a\_k\cfrac{z^k}{k!}$$. Prove that $$ \int\_0^\infty A(zt) e^{-t} , dt=\sum\_{k\ge 0} a\_k z^k, $$ provided the integral exists. Check this for sequences that appear in Tables 3.1 and 3.3. *** 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](https://en.wikipedia.org/wiki/Gamma_function) (see also [Exercise 4.60](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/6pjaXyRo8WpOT0GFIIZ1#exercise-4.60)). 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\*} $$ {% hint style="info" %} 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") ``` {% endhint %} *** If $$A(z) =ze^z$$ then $$ \begin{align\*} \int\_0^\infty zte^{zt} e^{-t} , dt &= \frac{z}{(1-z)^2}. \end{align\*} $$ {% hint style="info" %} 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") ``` {% endhint %} ## 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 🌟 {% hint style="success" %} This exercise elaborates the methodology of applying generating functions to solve linear recurrences with constant coefficients. {% endhint %} 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](https://en.wikipedia.org/wiki/Kronecker_delta). $$ \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\*} $$ {% hint style="info" %} 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). {% endhint %} *** 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. $$ \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\*} $$ {% hint style="info" %} Using the technique illustrated in [Exercise 2.31](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/Sy1KF5Jq9j0bEpfHwXvN#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)}$$. {% endhint %} $$ \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\*} $$ {% hint style="info" %} 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)}$$. {% endhint %} ## Exercise 3.17 🌟 {% hint style="success" %} This exercise shows how to compute the numerator polynomial $$f(z)$$ using a shortcut based on modular arithmetic. {% endhint %} 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+2z+4z^2)g(z) \mod z^3=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 \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}$$, substitute $$z=z\ln 2$$ into the formula from the book. So, $$ 2^z=\sum\_{k \ge 0} \frac{\ln^k 2}{k!}z^k. $$ ***Expansion of ze^z
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 🌟 {% hint style="success" %} This exercise introduces the [general Leibniz rule](https://en.wikipedia.org/wiki/General_Leibniz_rule) for computing the $$n$$th derivative of the product of two functions. {% endhint %} 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’ve 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 a 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. $$ Evaluated at $$z=0$$ 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](https://en.wikipedia.org/wiki/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 🌟 {% hint style="success" %} This exercise introduces lots of novelties and derives an expansion of an important generating function. {% endhint %} Let’s expand $$(1-z)^{-\alpha}$$ using Newton’s formula $$ \begin{align\*} [z^n](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/1-z)^{-\alpha} &= \frac{\alpha(\alpha+1)\cdots(\alpha+n-1)}{n!} \\ &= \binom{n+\alpha-1}{n} \\ &= \prod\_{k=0}^{n-1} \frac{\alpha + k}{k+1}. \end{align\*} $$ {% hint style="info" %} Observe that -1 from the negative exponent and -1 of $$z$$ cancel during derivations. {% endhint %} 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, $$ \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)}. $$ {% hint style="info" %} As a quick check, for $$\alpha=2$$ we indeed get the expansion of a left shifted OGF from Table 3.1. {% endhint %} 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](https://en.wikipedia.org/wiki/Binomial_coefficient#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](https://en.wikipedia.org/wiki/Digamma_function) provides a continuous [interpolation](https://en.wikipedia.org/wiki/Harmonic_series_\(mathematics\)#Interpolation) of the harmonic numbers. As stated on Wikipedia about it’s [relation to harmonic numbers](https://en.wikipedia.org/wiki/Digamma_function#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}](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/1-z)^2C'(z)}&= \underbrace{N(N+1)-(N-1)N-((N-1)N-(N-2)(N-1))}*{[z^{N-1}](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/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}](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/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\*} $$ {% hint style="info" %} We could have arrived at the same result iteratively by factoring $$(1-z)^2=(1-z)(1-z)$$. Notice that we’re referencing the $$(N-1)$$th coefficient. This is due to the simplified equation (3) in the book, where $$z$$ was removed on both sides. {% endhint %} ## 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](https://mathworld.wolfram.com/Derangement.html). 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](https://evarga.gitbook.io/sh-aofa/discrete-mathematical-methods/pages/Sy1KF5Jq9j0bEpfHwXvN#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 🌟 {% hint style="success" %} This exercise shows how new identities may improve performance. {% endhint %} 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}. $$ {% hint style="info" %} 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 accuracy is potentially increased, as well. {% endhint %} ## 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{z}{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](https://en.wikipedia.org/wiki/Bernoulli_number#Generating_function) for $$-\[z^m]$$ 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\*} $$ {% hint style="info" %} If we treat the generating function from this exercise as an EGF, then it describes the [ordered Bell numbers](https://en.wikipedia.org/wiki/Ordered_Bell_number). {% endhint %} ## 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\*} $$ {% hint style="info" %} The expression for the coefficient of the corresponding EGF is known as [Dobiński's formula](https://en.wikipedia.org/wiki/Dobi%C5%84ski%27s_formula). {% endhint %} ## 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\ge n$$. The coefficient $$\[z^k]$$ will "accumulate" contributions from all $$n\le k$$. 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](https://en.wikipedia.org/wiki/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](https://mathworld.wolfram.com/ForwardDifference.html), as mentioned in Chapter 2 of the book, 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 🌟 {% hint style="success" %} This exercise explains the composition of generating functions. {% endhint %} Wikipedia contains the [formal power series version](https://en.wikipedia.org/wiki/Fa%C3%A0_di_Bruno%27s_formula#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](https://en.wikipedia.org/wiki/Formal_power_series#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 leaving +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](https://en.wikipedia.org/wiki/Binomial_coefficient#Partial_sums). ## Exercise 3.44 🌟 {% hint style="success" %} This exercise showcases a more intricate functional equation, where interplay of two sub-functions define the OGF. {% endhint %} 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)}. $$ 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\*} $$ 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)}. $$ 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). $$ We can solve this functional equation by iterating. 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’ve 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\_{i\ge0} b\_i z^{2i} - \sum\_{j\ge0} b\_j z^{4j+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](https://oeis.org/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 $$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$$ 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 (see [Exercise 3.25](#exercise-3.25)), and passing $$g(z)$$ as an argument, we’ve $$ \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 {% hint style="danger" %} The text of this exercise in the book is imprecise. The paper [Singularity Analysis Of Generating Functions\*](https://algo.inria.fr/flajolet/Publications/FlOd90b.pdf) contains a section about 2-3 trees, where the matching functional equation represents the number of such trees with n **external** nodes. {% endhint %} Let $$f(z) = \sum\_{n \ge 0} f\_n z^n$$ be the OGF for the number of [2–3 trees](https://en.wikipedia.org/wiki/2%E2%80%933_tree) , 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 $$z$$ 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\_{k \ge 2} f\_k (z^2 + z^3)^k}*{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. ```python 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$$. {% hint style="info" %} 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](https://oeis.org/A014535). {% endhint %} ## Exercise 3.49 🌟 {% hint style="success" %} We show by induction on $$t$$ that $$(1-z)^tC^{(t)}(z)=\Psi(\Psi+1)\dots (\Psi+t-1)C(z)$$. {% endhint %} {% hint style="danger" %} The book, at the time of this writing, has an error; $$t+1$$ must be replaced by $$t-1$$. {% endhint %} 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](https://sedgewick.io/wp-content/themes/sedgewick/papers/1977Analysis.pdf) 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 🌟 {% hint style="success" %} 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. {% endhint %} ### Understanding the Problem The specific [ordinary differential equation](https://en.wikipedia.org/wiki/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, $$ with 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](https://en.wikipedia.org/wiki/Cauchy%E2%80%93Euler_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](https://tutorial.math.lamar.edu/classes/de/seriessolutions.aspx) in the sense that the normalized coefficients $$a\_j(z)/a\_r(z)$$ are [analytic](https://en.wikipedia.org/wiki/Analytic_function) 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](https://mathworld.wolfram.com/FrobeniusMethod.html). 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. {% hint style="info" %} 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. {% endhint %} #### 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 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](https://en.wikipedia.org/wiki/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 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](https://mathworld.wolfram.com/HermiteDifferentialEquation.html). For finding the particular solution, we employ the Frobenius method. We start with the default [ansatz](https://en.wikipedia.org/wiki/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 coefficient is determined by substituting this ansatz and solving the resulting linear system. ### General Case 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$$. By the fundamental theorem of linear ODEs, an $$r$$th order homogeneous equation at an ordinary point is guaranteed to have exactly $$r$$ linearly independent solutions. In the context of our power series $$f(x) = \sum a\_n x^n$$, these $$r$$ independent solutions are uniquely determined by the $$r$$ arbitrary initial conditions: $$a\_0, a\_1, \dots, a\_{r-1}$$. The parity of $$r$$ simply dictates how these $$r$$ degrees of freedom are processed by the recurrence: * When $$r$$ is even: The $$r$$ initial conditions are split evenly across the two independent parity subspaces ($$r/2$$ even coefficients, $$r/2$$ odd coefficients). The recurrence propagates them independently, yielding $$r/2$$ purely even solutions and $$r/2$$ purely odd solutions, totaling $$r$$ independent solutions. We’ve already seen example of this with $$r=2$$. * When $$r$$ is odd: All $$r$$ initial conditions ($$a\_0, \dots, a\_{r-1}$$) feed into the same unified recurrence chain. By setting one of these initial coefficients to 1 and the other $$r-1$$ coefficients to 0, and repeating this for each $$a\_k$$ ($$0 \le k < r$$), the single recurrence naturally generates the full fundamental set of $$r$$ linearly independent solutions. 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 See [Exercise 3.51](#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. {% hint style="info" %} 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.