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.
 A: 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.
A: Thanks so much for your answer FredH. I agree with what you say.
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$.
