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).
 A: 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}
$$
A: 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$$
A: 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)$
