<s>[INST] Proof involving generating function The following is part of a proof that the number of ways of associating a product with $n$ terms (different ways of inserting parentheses) is $$
a_1 = 1,\ a_n = \frac{1}{n} \binom{2n-2}{n-1},$$
and the relationship$$
a_{n+1} = a_1a_n + a_2a_{n-1} + a_3a_{n-2} + \cdots + a_na_1$$
is already established.
The proof starts with the generating function $$f_A(x) = \sum_{n=1}^\infty a_nx^n,$$
then by the relationship, $$f_A(x) = x + \sum_{n=2}^\infty (a_1a_{n-1} + \cdots + a_{n-1}a_1)x^n.$$
I am unclear about the next step:
$$f_A(x) = x + \left(\sum_{n=1}^\infty a_nx^n\right)\left(\sum_{n=1}^\infty a_nx^n\right).$$
I tried using an upper bound of three in each expression. For the first expression I obtained $$a_1^2x^2 + 2a_1a_2x^3.$$
For the second expression I obtained $$a_1^2x^2 + 2a_1a_2x^3 + a_2^2x^4 + 2a_2a_3x^5 + a_3^2x^6.$$
As it appears the first two terms are the same. Can we ignore the extra terms as the upper bound approaches infinity?
 [/INST] Let 
$$f_n = \frac{1}{n} \binom{2n-2}{n-1} = \frac{1}{2n - 1} \binom{2n-1}{n}$$

\begin{align}
f(x) &= \sum_{n=1}^\infty f_nx^n\tag{1}\\
     &= \sum_{n=1}^\infty \frac{1}{2n - 1} \binom{2n-1}{n}x^n\\
     &= \sum_{n=1}^\infty \frac{(2n-2)!}{n!(n-1)!}x^n\\
     &= \sum_{n=1}^\infty \frac{1}{n} \binom{2n-2}{n-1}x^n\tag{2}\\
     &= \frac{1}{2} - \frac{1}{2}\sqrt{1 - 4x}\\
\end{align}


$$x + \left(\sum_{n=1}^\infty f_nx^n\right)\left(\sum_{n=1}^\infty f_nx^n\right) =x + [f(x)]^2 = f(x)$$

But from equation (1), 
$$[f(x)]^2 = \sum_{n=2}^\infty\left(\sum_{i=1}^{n-1}f_if_{n-1}\right)x^n$$
Therefore, 
$$x + \sum_{n=2}^\infty\left(\sum_{i=1}^{n-1}f_if_{n-1}\right)x^n = \sum_{n=1}^\infty f_nx^n$$


An observation $f_n = \frac{1}{n} \binom{2n-2}{n-1} = \frac{(2n-2)!}{n!(n-1)!} = C_{n-1}$. Where $C_n$ is the Catalan Number
</s>