2
$\begingroup$

I know that generating function for the Catalan number sequence is $$f(x) = \frac{1 -\sqrt{4x}}{2x}$$ but I wan to prove it.

So the sequence for the Catalan numbers is $$1,1,2,5,14....$$ as we all know.

Now I have to find a generating function that generates this sequence.

I read that we can prove it this way: Asssume that $f(x)$ is the generating function for the Catalan sequence then by the Cauchy product rule it can be shown that $xf(x)^2 = f(x) − 1$

And so this implies that $$xf(x)^2 - f(x) + 1 = 0$$ and so we can get that $$f(x) = \frac{1-\sqrt{4x}}{2x}$$

But I can't get to understand how is that possible ? Like assume that $f(x)$ is the generating function for the Catalan sequence, then how come by the Cauchy product we have that $xf(x)^2 = f(x) − 1$

I know that if we multiply the sequence $$1,1,2,5,14,....$$

By itself we would get in the resulting sequence $$1,1,5,14,...$$

Because we have that $c_k = a_0b_k + a_1b_{k-1}+ ........ + a_kb_0$ using the cauchy product formula but still how do we have that $xf(x)^2 = f(x) − 1$

and how did we get that $$f(x) = \frac{1-\sqrt{4x}}{2x}$$ from

$xf(x)^2 = f(x) − 1$ ? did we use the quadratic formula some how ?

$\endgroup$
  • $\begingroup$ From oeis.org/A000108 : G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). G.f. A(x) satisfies A = 1 + x*A^2. $\endgroup$ – Lisa Dec 1 '15 at 22:06
  • $\begingroup$ The first part of this answer gives the derivation in quite a bit of detail. $\endgroup$ – Brian M. Scott Dec 2 '15 at 6:57
4
$\begingroup$

The $n^{th}$ catalan number $C_n$ is the number of ways to arrange $2n$ parentheses in a way that makes sense. For example, there are exactly $2$ ways for $n=2$: (()) and ()(). This gives us a recursive way to calculate $C_n$. To find $C_3$, note that there will be a first time in each sequence of parentheses when every left parenthesis is matched by a right parenthesis. In (())(), this happens for the first time after (()). So each sequence starts off with (x), where x is a valid, possibly empty, sequence of parentheses. There are $C_2$ ways for x to have length 2. There are $C_1$ ways for x to have length 1, and $C_1$ ways to fill in the last 2 parentheses in the sequence. There are $C_0$ ways for x to be empty, and $C_2$ ways to fill in the last four parentheses. So we have $C_3=C_2C_0+C_1C_1+C_0C_2$. This can give us the formula we want in general, $C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1}$. So if we start with the generating function $f(x)=\sum_{i=0}^{\infty} C_ix^i$ and square it, we get $f(x)^2=\sum_{i=0}^{\infty} (\sum_{j=0}^{i}C_iC_{i-j})x^i=\sum_{i=0}^{\infty} C_{i+1}x^i=\frac{f(x)-1}{x}$. Rearranging,

$xf(x)^2-f(x)+1=0$
Now you have a quadratic equation in $f(x)$, so you can use the quadratic formula to get: $$f(x)=\frac{1-\sqrt{1-4x}}{2x}$$

$\endgroup$

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.