Is there a closed form for a sequence invariant under "Cauchy square"?

108 Views Asked by At

For two sequences $a=(a_n), b=(b_n),$ define the Cauchy product as $a*b=(c_n),$ where $c_n=\sum_{k=0}^{n}a_kb_{n-k}.$ Then is there a closed form expression for a sequence $(a_n)$ whose product with itself is itself: $a*a=a$ (given some initial conditions)?
In particular, I would like to find the sequence defined recursively by $$\begin{cases}a_0=0\\ a_1=1\\ a_n=\sum_{k=1}^{n-1}a_ka_{n-k}\end{cases}.$$
I tried to look at the generating funciton of this sequence, but then it leads to a polynomial $G(x)$ with $G(x)^2=G(x)-x,$ which does not seem to give a closed form relation.
I use a program to compute the first $15$ numbers: $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,$
but I don't see a clear pattern.
Any hint, reference, and suggestion are greatly welcomed, thanks in advance.
P.S. This sequence arises when I tried to compute the number of ways $n$ numbers can be added together: for example, $(x_1+x_2)+x_3,$ and $x_1+(x_2+x_3).$
Edit: Thanks to Pedro Tamaroff, the answer is: $a_n=\binom{2n-1}{n}\cdot\frac{1}{2n-1},$ for a reference.

1

There are 1 best solutions below

2
On BEST ANSWER

Your generating function approach is fine. From $G^2-G+x=0$ you get that $2G=1\pm \sqrt{1-4x}$. You need to find out which sign to take. Look up Catalan numbers.