Jtdylktuy

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 ?

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