# Solving $a_n=1+\sum_{k=0}^n a_k a_{n-k}$.

We define a sequence by $$a_0=0$$ and $$a_n=1+\sum_{k=0}^n a_k a_{n-k}\quad n\ge1$$ Find a non-recursive formula for $$a_n$$.

Not homework, this is a question from my friend. I tried to use summation by parts $$\sum_{k=m}^na_kb_k =A_nb_n-A_{m-1}b_m-\sum_{k=m}^{n-1}A_k(b_{k+1}-b_k)$$ But it doesn't make this problem easier. I am wondering if this problem is a special one ($$a_0=0$$) and then it has a non-recursive formula. Any hints would be highly appreciated!

• @ClaudeLeibovici Yes, it's $n$. Apr 10, 2020 at 10:24
• It doesn't make much difference, since the terms involving $a_n$ are $a_0a_n$ and $a_na_0$, which both are $0$. If you know about generating functions, they will be very useful for this problem Apr 10, 2020 at 10:28
• @Wojowu Could you please explain more about it? I know a little about generating functions but I didn't figure out how to use it. Thanks! Apr 10, 2020 at 10:33

Here is a sketch of a solution using generating functions. Let $$F(x)=\sum_{n=0}^\infty a_nx^n$$. We then have $$F(x)^2=\sum_{n=1}^\infty\left(\sum_{k=0}^n a_ka_{n-k}\right)x^n=\sum_{n=1}^\infty(a_n-1)x^n=F(x)-\frac{x}{1-x}.$$ Using the quadratic formula you can now solve for $$F(x)$$. To get the formula for the coefficients, you may want to use the binomial series.
Note we can drop the $$k=n$$ term because then $$a_{n-k}=0$$. Your sequence is the binomial transform of the Catalan numbers. It can be described with many formulae, including yours, credited to Cloitre 2004. The closed form is $$F(\tfrac12,\,-n;\,2;\;-4)$$ in terms of the ordinary hypergeometric function.