Is there an analytic expression for this recursive sum? $C_n = \sum _{k=0}^{n-1}C_k C_{n-1-k}$

Question

Is there an analytic expression for this recursive sum ? Say , $C_n = ?$

\begin{align*} C_n =& \sum _{k=0}^{n-1}C_k C_{n-1-k} \\ =& C_0C_{n-1} + C_1C_{n-2}+\cdots+C_{n-1}C_0 \end{align*}

Answer 1

Hint. One may recall the Cauchy product: $$ \left(\sum_{n=0}^\infty A_n \right)\!\left(\sum_{n=0}^\infty B_n \right) = \sum_{n=0}^\infty \left(\sum_{k=0}^n A_k B_{n-k}\right), \tag1 $$ then use it with $A_n=B_n=C_nx^n$ to get $$ \left(\sum_{n=0}^\infty C_n x^n\right)^2 = \sum_{n=0}^\infty \left(\sum_{k=0}^n C_k C_{n-k}\right)\!x^n =\sum_{n=1}^\infty \left(\sum_{k=0}^{n-1} C_k C_{n-1-k}\right)\!x^{n-1}. \tag2 $$ By hypothesis, the latter series is equal to $\displaystyle \sum_{n=1}^\infty C_n x^{n-1}$, thus $(2)$ rewrites $$ \left(\sum_{n=0}^\infty C_n x^n\right)^2 = \sum_{n=1}^\infty C_n x^{n-1} \tag3 $$$$ x\left(\sum_{n=0}^\infty C_n x^n\right)^2 = \left(\sum_{n=0}^\infty C_n x^n\right)-C_0 \tag4 $$ Setting $\displaystyle f(x):=\sum_{n=0}^\infty C_n x^n $, the ordinary generating function of the numbers $C_n$, then $(4)$ reads $$ x\:(f(x))^2=f(x)-C_0 \tag5 $$ giving $$ f(x)=\frac{1-\sqrt{1-4 C_0 x}}{2 x} \tag6 $$ for appropriate $C_0$. Using the binomial theorem, $(6)$ leads to $$ f(x)=\sum_{n=0}^\infty \frac1{n+1}\binom{2n}{n}\times (C_0)^{n+1}\times x^n \tag7 $$ and we conclude by identification between $\displaystyle f(x)=\sum_{n=0}^\infty C_n x^n$ and $(7)$ to get

$$ C_n=\frac1{n+1}\binom{2n}{n}\times (C_0)^{n+1}. \tag8 $$

The case $C_0=1$ gives Catalan's numbers.

Answer 2

Yes, this is known as the Catalan sequence: with $C_0 =1$:

$$ C_n = \frac{(2n)!}{n!(n+1)!} $$