Generating Function For Catalan Numbers Type Sequence

Question

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.

Answer 1

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.

Answer 2

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$.