# Finding the generating function for the Catalan number sequence

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 ?

• 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. – Lisa Dec 1 '15 at 22:06
• The first part of this answer gives the derivation in quite a bit of detail. – Brian M. Scott Dec 2 '15 at 6:57

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}$$
• How did you immediately deduce $f(x)^2 = ...$? It is not clear. – Alex Ni Feb 22 at 23:19