# Functional equations and generating functions

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

• The "double coefficient" is nothing more than multiplication: $xy$ means $x$ times $y$. – anon Apr 9 '13 at 7:35
• @AlanH: You've changed spacing and changed it back. Are you trying to bump the question on the main list? What is it that you don't understand? – robjohn Apr 9 '13 at 21:59
• @robjohn I was curious what rollback was. I'll change it back; I didn't edits bumped questions up. Sorry. I'm still going through your response. – AlanH Apr 9 '13 at 22:01

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}

• okay so you used the generalized binomial theorem, then how do you get the coefficient of $x^k$ in (3)? – AlanH Apr 9 '13 at 22:36
• @AlanH: added a section to the answer. – robjohn Apr 9 '13 at 23:35
• oh wow...Thanks for that. – AlanH Apr 9 '13 at 23:40

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

Write your recurrence as: $$a_{n + 1} = \sum_{0 \le k \le n} a_k a_{n - k}$$ Define $A(z) = \sum_{n \ge 0} a_n z^n$. Multiply by $z^n$, sum over $n \ge 0$. The LHS is just: $$\frac{A(z) - a_0}{z}$$ the RHS is: $$A(z) \cdot A(z)$$ thus: $$A(z) = a_0 + z A^2 (z)$$ This gives: $$A(z) = \frac{1 \pm \sqrt{1 - 4 a_0 z}}{2 z}$$ The positive sign is spurious, $A(0) = a_0$ is finite. Expand the square root by the generalized binomial theorem: $$A(z) = \frac{1}{2 z} \, \left( 1 - \left( 1 + \sum_{n \ge 1} \frac{(-1)^{n - 1}}{n 2^{2 n - 1}} \, \binom{2 n - 2}{n - 1} \, (-4 a_ 0 z)^n \right) \right) = \sum_{n \ge 0} \frac{1}{n + 1} \binom{2 n}{n} a_0^{n + 1} z^n$$ and thus: $$a_n = \frac{1}{n + 1} \binom{2 n}{n} a_0^{n + 1}$$ This is intimetaly related to the famous Catalan numbers. A dead giveaway for them is their generating function's functional equation $C(z) = 1 + z C^2(z)$