Generating function satisfying a second degree equation

Question

I got this problem in an exercise list:

Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation:

$$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, C_0=C_1=1.$$

Show that $xG(x)^2 - G(x)+1=0$ and conclude that

$$G(x)=\frac{1-\sqrt{1-4x}}{2x}.$$

Then, show that

$$G(x)=\sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n.$$

What I tried to do:

Since $G(x)=\sum_{n=0}^{\infty}C_nx^n$,we have that $$xG(x)^2 - G(x)+1=x\left(\sum_{n=0}^{\infty}C_nx^n\right)^2-\sum_{n=0}^{\infty}C_nx^n+1$$ $$=\left(\sum_{n=0}^{\infty}C_nx^n\right)\left(\sum_{n=0}^{\infty}C_nx^{n+1}-1\right)+1$$ $$=x\left(\sum_{n=0}^{\infty}C_nx^n\right)\left(\sum_{n=1}^{\infty}C_nx^n\right)+1$$

But I really don't know how to conclude that this thing is 0.

Besides that, let's assume just for a second that I was able to prove that $xG(x)^2 - G(x)+1=0$.

From the equation above, we get that

$$G(x)=\frac{1+\sqrt{1-4x}}{2x}$$

or

$$G(x)=\frac{1-\sqrt{1-4x}}{2x}$$

How do I know which is the right one?

Now, let's pretend again that I fully understood the problem until this point, and that I know why $G(x)=\dfrac{1-\sqrt{1-4x}}{2x}$, how can I conclude that $G(x)=\sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n?$

Hints, solutions, everything here is welcome... Thanks!

Answer 1

$\def\fr#1#2{{\textstyle{\frac{#1}{#2}}}}$ Hints. To prove the equation for $G(x)$, start with $$G(x)^2=\Bigl(\sum_{k=0}^\infty C_kx^k\Bigr)^2 =\sum_{n=1}^\infty\Bigl(\sum_{k=0}^{n-1}C_kC_{n-1-k}\Bigr)x^{n-1}\ ;$$ the second equality is true because if $n\ge1$, then the coefficient of $x^{n-1}$ in the square of the sum is the coefficient of $x^0$ times the coefficient of $x^{n-1}$, plus the coefficient of $x^1$ times the coefficient of $x^{n-2}$, and so on. Now multiply both sides by $x$ and use the given recurrence.

Solving the quadratic gives two possible answers as you have noted. To choose the correct one, note that from the series we have $G(0)=C_0=1$. Now in the quadratic solutions you cannot take $x$ equal to $0$ because you have $x$ in the denominator; but you can take the limit as $x$ approaches $0$.

For the final part, use the binomial theorem to expand $\sqrt{1-4x}$. We have $$\sqrt{1-4x}=(1-4x)^{1/2}=\sum_{n=0}^\infty C(\fr{1}{2},n)(-4x)^n$$ and we evaluate the binomial coefficient starting thus: $$\eqalign{C(\fr{1}{2},n) &=\frac{\frac{1}{2}(-\frac{1}{2})(-\frac{3}{2})\cdots(\frac{3}{2}-n)}{n!}\cr &=\frac{(-1)^{n-1}}{2^n}\frac{(2n-3)\cdots3\times1}{n!}\cr &=\frac{(-1)^{n-1}}{2^n}\frac{(2n-3)\cdots3\times1}{n!} \frac{(2n-2)(2n-4)\cdots4\times2}{(2n-2)(2n-4)\cdots4\times2}\cr &=\frac{(-1)^{n-1}}{2^n}\frac{(2n-2)!}{n!\,2^{n-1}(n-1)!}\ .\cr}$$ See if you can take it from here.

Answer 2

You can tell that the minus sign is correct, since you know that $G(x)$ is a power series, and if you used the plus sign, the numerator would start $1+1+...$, so that $G(x)$ would have a term $\frac{1}{x}$. To see that $G(x) = \sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n$, note that $$(1+x)^{1/2} = \sum_0^\infty \dbinom{1/2}{k}x^k.$$ Now, $\dbinom{1/2}{k} = (-1)^k2^{1-2k}\frac{1}{k}\dbinom{2k-2}{k-1}$ for $k>0$, as you can see by just expanding the series for the left-hand side and simplifying. Thus $$(1+x)^{1/2} = \dbinom{1/2}{0} + \sum_{k=1}^\infty \dbinom{1/2}{k}x^k = 1 + \sum_{k=1}^\infty (-1)^{k-1}2^{1-2k}\frac{1}{k}\dbinom{2k-2}{k-1}x^k.$$ Now replace $x$ by $-4x$ to get $$(1-4x)^{1/2} = 1 + \sum_{k=1}^\infty (-1)^{k-1}2^{1-2k}\frac{1}{k}\dbinom{2k-2}{k-1}(-1)^k2^{2k}x^k = 1 + \sum_{k=1}^\infty (-2)\frac{1}{k}\dbinom{2k-2}{k-1}x^k.$$ Thus $$(1-4x)^{1/2}-1 = \sum_{k=1}^\infty (-2)\frac{1}{k}\dbinom{2k-2}{k-1}x^k = \sum_{k=0}^\infty (-1)\frac{1}{k+1}\dbinom{2k}{k}x^k.$$ Now multiply through by $-\frac{1}{2}$ to get $$\frac{1-\sqrt{1-4x}}{2} = \sum_{k=0}^\infty \frac{1}{k+1}\dbinom{2k}{k}x^k.$$