How to solve the recurrence relation $ a_{n}=\sum_{i=1}^{n-1}a_{i}a_{n-i} $ The relation is:
$$
a_{n}=\sum_{i=1}^{n-1}a_{i}a_{n-i}\\n>1,a_1=2
$$
I know I probably should create a generating function for $a_n$, like $G(x)=f(x)*g(x)$, but I'm not sure what $f(x)$ and $g(x)$ exactly should be, are they just $\sum a_ix^i$ and $\sum a_{n-i}x^{n-i}$ ? And are there any other methods to solve it? Any hint would be useful to me.
 A: We can use generating functions to solve this recurrence relation. We set according to the stated recurrence relation
\begin{align*}
A(x)=\sum_{n=1}^{\infty}a_nx^n=2x+\sum_{n=2}^{\infty}\left(\sum_{i=0}^{n-1}a_ia_{n-i}\right)x^n\tag{1}
\end{align*}
Note we start the generating function with $2x$ since the recurrence relation has initial condition $a_1=2$.

Since
\begin{align*}
\left(A(x)\right)^2&=\left(\sum_{k=1}^\infty a_kx^k\right)\left(\sum_{l=1}^\infty a_lx^l\right)\\
&=\sum_{n=2}^\infty \left(\sum_{{k+l=n}\atop{k,l\geq 1}}a_ka_l\right)x^n\\
&=\sum_{n=2}^{\infty}\left(\sum_{k=1}^{n-1}a_ka_{n-k}\right)x^n\tag{2}
\end{align*}
we obtain from (1) and (2) the functional equation
\begin{align*}
\left(A(x)\right)^2=A(x)-2x
\end{align*}
Solving this quadratic equation we find
\begin{align*}
\color{blue}{A(x)=\frac{1}{2}\left(1\pm\sqrt{1-8x}\right)}\tag{3}
\end{align*}
where we take the minus sign, since this provides a generating function with constant term zero.

Note: Evaluating the first few terms $a_n$ gives
\begin{align*}
A(x)&=\frac{1}{2}\left(1-\sqrt{1-8x}\right)\\
&=2x+4x^2+16x^3+80x^4+448x^5+\cdots
\end{align*}
We find the sequence $\left(a_n\right)_{n\geq 1}$ stored as A025225 in OEIS. There's also an explicit expression given for $a_n$:
\begin{align*}
a_n=\frac{2^n}{n}\binom{2n-2}{n-1}\qquad n=1,2,\ldots
\end{align*}
which can be easily derived from (3) and we find a strong connection with the ubiquituous Catalan numbers.
