# Generating Function For Catalan Numbers Type Sequence

I've been working my way through an old post, but I don't think the solution offered can be correct.

The question is;

Find the generating function (within a choice of sign) for: $$c_{n+1} = 2\sum_{k=0}^{n}c_k c_{n-k},\;\;\;n=1,2,3,4,\dots\\c_0=1, \;c_1=3$$

I think this recurrence relation generates the numbers $$1, 3, 12, 66, 408, 2712, ...$$

The solution offered is;

Let $$g(x)=\sum_{n\ge 0}c_nx^n$$ be the ordinary generating function for the sequence. Then the standard formula for the Cauchy product of two summations yields

$$\big(g(x)\big)^2=\left(\sum_{n\ge 0}c_nx^n\right)^2=\sum_{n\ge 0}\left(\sum_{k=0}^nc_kc_{n-k}\right)x^n=\frac12\sum_{n\ge 0}c_{n+1}x^n\;,$$

and multiplication by $$2x$$ gives us

$$2x\big(g(x)\big)^2=x\sum_{n\ge 0}c_{n+1}x^n=\sum_{n\ge 1}c_nx^n=g(x)-c_0\;.$$

This is a quadratic in $$g(x)$$, so it can straightforwardly be solved for $$g(x)$$.

From this I've deduced that $$g(x)=\frac{1-\sqrt(1-8x)}{4x}$$

I've gone through this proof carefully and can't see an error but I know from Wolfram Alpha that it does not generate the numbers I was expecting. It also makes no use of the fact that $$c_1 = 3$$ which can't be right. I think the correct generating function is; $$GF=\frac{1-\sqrt(1-8x-8x^2)}{4x}$$ but can't see how to obtain this. It generates the numbers I was expecting and is in Sloan : https://oeis.org/search?q=1%2C3%2C12%2C66%2C408&language=english&go=Search

FYI : The original post, from 2013, is here : How do you find generating function?

For anyone interested in The Catalan Numbers, this would be a good 'one step on' question so if anyone can spot where the glitch is, I think it would be most useful.

The trouble seems to be in this step: $$\sum_{n\ge 0}\left(\sum_{k=0}^nc_kc_{n-k}\right)x^n= \frac12\sum_{n\ge 0}c_{n+1}x^n.\tag{*}$$ It is true that $$\sum_{k=0}^nc_kc_{n-k}=\frac12 c_{n+1},$$ but only for $$n\ge1$$. The constant term in (*) is $$c_0^2 = 1$$, which is not $$\frac12 c_1 = \frac32$$.
Taking this into account, one instead finds $$g(x)^2 = \frac12\sum_{n\ge 0}c_{n+1}x^n - \frac12,$$ and the resulting quadratic is $$2x(g(x))^2 = g(x) - x - 1.$$ One of the solutions of this quadratic is exactly the result you expected.
By the way, to find the error I found it helpful to write out the low-order terms of $$g(x)$$ and $$g(x)^2$$. Those terms are where the complications are typically found in generating function problems.
Thinking about it some more, and to clarify for anyone looking at this later on, the key step was moving from $$c_{n+1} = 2\sum_{k=0}^{n}c_k c_{n-k},\;\;\;n=1,2,3,4,\dots\\$$ to $$\sum_{k=0}^{n}c_k c_{n-k}=\frac{c_n+1}{2}\;\;\;n=1,2,3,4,\dots\\$$ This needed this to be valid for $$n=0,1,2,3,4,...$$ in order to make the substitution to carry the main thread of the argument onward. So, clearly great care must be taken over such extensions to include $$n=0$$.