How to solve the recurrence relation $ a_{n}=\sum_{i=1}^{n-1}a_{i}a_{n-i} $

Question

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.

Answer 1

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.