Find the general term in the sequence with generating function

Question

Let $a_n$ be the sequence defined by $$a_0 = 1,$$ $$2a_{n+1}=\sum_{i=0}^n\binom{n}{i}a_ia_{n-i}$$ I want to find the general term. I have noticed that $$\sum_{i=0}^n\binom{n}{i} = 2^n$$ but don't know how to go beyond that. Really need help here.

Answer 1

There might be a more elegant way to manipulate the recurrence directly without a helper sequence, but this is the way I determined.

Define the sequence $b_n=\frac{a_n}{n!}$. We have that $b_0=1$ and $2(n+1)b_{n+1}=\sum_{i=0}^n b_ib_{n-i}$.

If $B(x)=\sum_{i=0}^\infty b_ix^i$, then note that $\sum_{i=0}^n b_ib_{n-i}$ is the coefficient of $x^n$ in $B(x)^2$. Moreover, $2(n+1)b_{n+1}$ is the coefficient of $x^n$ in $2B'(x)$. Since $2B'(x)$ and $B(x)^2$ have the same coefficients for all $n$, it follows that $$2B'(x)=B(x)^2$$ $$\frac{2B'(x)}{B(x)^2}=1$$ $$\int \frac{2B'(x)}{B(x)^2}\, dx=\int 1\, dx$$ $$-\frac{2}{B(x)}=x+C$$ $$B(x)=-\frac{2}{x+C}$$ There is also a singular solution of $B(x)\equiv 0$. However, since $B(0)=1$ (since $b_0=1$), we know that we must have $B(x)=-\frac{2}{x-2}$.

So $B(x)=\frac{1}{1-\frac{x}{2}}=\sum_{n=0}^\infty \frac{x^n}{2^n}$. Hence, $b_n=2^{-n}$ and $a_n=\boxed{2^{-n}(n!)}$