Generating function satisfying a second degree equation 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!
 A: $\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.
A: 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.$$
