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

## 2 Answers

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.

• Thanks for a quick response; I'm going to look at it very carefully after work finishes later, (following your advice), but it's the sort of small but very annoying error that I knew had to be in there somewhere. – Martin Hansen Mar 7 '19 at 13:54
• I've gone over this and am thoroughly satisfied with the argument now. I've added a note to the old post to point it here, and have also added a small further clarification here of exactly why the original six year old post derived a wrong answer. – Martin Hansen Mar 7 '19 at 21:31

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