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.

  • $\begingroup$ 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. $\endgroup$ – Martin Hansen Mar 7 '19 at 13:54
  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.