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{1-4x}}{2x}$$ but I want 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{1-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{1-4x}}{2x}$$
from
$xf(x)^2 = f(x) − 1$ ? did we use the quadratic formula some how ?
 A: I'd like to ressurect this old post :)
To motivate the equation for the generating function you may do direct calculations (!) on the set of correct bracket sequences.
Let
$$
S = \square + () + (()) + ()() + ((())) + (())() + ()(()) + \ldots
$$
Multiplication is intuitive, like $() \cdot (()) = ()(())$.
As @Timur vural pointed out: look at the expression that is surrounded by the first bracket ( and its matching pair ).
$$
S = \square + (\square) \cdot \square + (())\cdot \square + (\square) \cdot () + ((()))\cdot \square + (())\cdot () + ()\cdot (()) + \ldots
$$
And now let the magic happen!
$$
S = \square + (\cdot S \cdot ) \cdot S
$$
Replace the pair of brackets with $x$ and $S$ with $f(x)$ and get the equation you want:
$$
f(x) = 1 + x\cdot f(x)\cdot f(x)
$$
A: 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+1}=\sum_{i=0}^{n}C_iC_{n-i}$. So if we start with the generating function $f(x)=\sum_{i=0}^{\infty} C_ix^i$ and square it, using properties of the Cauchy product we get: $f(x)^2=\sum_{i=0}^{\infty} (\sum_{j=0}^{i}C_jC_{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}$$
