Functional equations and generating functions

Question

The problem asks to find the functional equations for the generating functions whose coefficients satisfy $$ a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1 $$

There's an example that's similar to it in the text, prior to the exercises, but all I'm doing is mimicking. I don't understand how to solve this and what the double coefficient in the summand mean (an intuitive explanation would be very much appreciated).

Answer 1

Consider the generating function of $a_k$ $$ f(x)=\sum_{k=0}^\infty a_kx^k\tag{1} $$ Apply the recursion above: $$ \begin{align} f(x) &=\sum_{k=0}^\infty a_kx^k\\ &=1+\sum_{k=1}^\infty\sum_{j=0}^{k-1}a_ja_{k-j-1}x^k\\ &=1+x\sum_{k=1}^\infty\sum_{j=0}^{k-1}a_ja_{k-j-1}x^jx^{k-j-1}\\ &=1+x\sum_{k=0}^\infty\sum_{j=0}^\infty a_jx^j\,a_kx^k\\ &=1+xf(x)^2\tag{2} \end{align} $$ The steps in $(2)$ are related to the Cauchy Product Formula.

Solving $(2)$ for $f(x)$ with the quadratic formula and applying the binomial theorem to $(1-4x)^{1/2}$ yields $$ \begin{align} f(x) &=\frac{1-\sqrt{1-4x}}{2x}\\ &=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^k\tag{3} \end{align} $$ Comparing $(1)$ and $(3)$, we get $$ a_k=\frac1{k+1}\binom{2k}{k}\tag{4} $$ Note that these are the Catalan Numbers. You can see the recursion above here.

---

Binomial Expansion of $\boldsymbol{(1-4x)^{1/2}}$

$$ \begin{align} (1-4x)^{1/2} &=1+\frac{\frac12}{1}(-4x)+\frac{\frac12(-\frac12)}{1\cdot2}(-4x)^2 +\frac{\frac12(-\frac12)(-\frac32)}{1\cdot2\cdot3}(-4x)^3+\dots\\ &=1-\sum_{k=1}^\infty\frac{(2k-3)!!}{2^kk!}4^kx^k\\ &=1-\sum_{k=1}^\infty\frac{(2k-2)!}{2^{k-1}(k-1)!k!}2^kx^k\\ &=1-\sum_{k=1}^\infty\frac2k\binom{2k-2}{k-1}x^k\tag{5} \end{align} $$ Thus, $$ \begin{align} \frac{1-\sqrt{1-4x}}{2x} &=\sum_{k=1}^\infty\frac1k\binom{2k-2}{k-1}x^{k-1}\\ &=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^k\tag{6} \end{align} $$

Answer 2

Hint:

If $$f(x) = a_0 + a_1 x + a_2 x^2 + \dots$$

then what is $(f(x))^2$? (when we attempt to express as power series).

For sake of completion, the coefficient of $x^{k}$ in $(f(x))^2$ is

$$ a_0 a_k + a_1 a_{k-1} + a_{2} a_{k-2} + \dots + a_{k-1}a_{1} + a_{k}a_{0} = \sum_{i=0}^{k} a_i a_{k-1}$$

Since we have that $$a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}$$

The coefficient of $x^{n-1}$ in $(f(x))^2$ is same as the coefficient of $x^n$ in $f(x)$ and since $a_0 = 1$, we get the functional equation

$$f(x) = 1 + x (f(x))^2$$