<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] Note that
$$
\begin{align}
f(x)
&=\sum_{n=1}^\infty\color{#C00}{a_n}x^n\tag1\\
&=\color{#C00}{a_1}x+\sum_{n=2}^\infty\color{#C00}{\sum_{k=1}^{n-1}a_ka_{n-k}}x^n\tag2\\
&=x+\left(\sum_{n=1}^\infty a_nx^n\right)^2\tag3\\[9pt]
&=x+f(x)^2\tag4
\end{align}
$$
Explanation:
$(1)$: $f$ is the generating function for $a_n$
$(2)$: use the recurrence for $a_n$
$(3)$: $a_1=1$ and the Cauchy Product of the sum in $(2)$
$(4)$: $f$ is the generating function for $a_n$
Since, $f(x)^2-f(x)+x=0$,
$$
\begin{align}
f(x)
&=\frac{1-\sqrt{1-4x}}2\tag5\\
&=\sum_{n=1}^\infty\frac1{4n-2}\binom{2n}{n}x^n\tag6
\end{align}
$$
Explanation:
$(5)$: apply the Quadratic Formula
$(6)$: apply the Generalized Binomial Theorem 
Since $f$ is the generating function for $a_n$,
$$
a_n=\frac1{4n-2}\binom{2n}{n}=\frac1n\binom{2n-2}{n-1}\tag7
$$
</s>