Catalan numbers formula derivation I'm trying to follow a proof of the Catalan numbers being equal to $\frac{1}{n+1} {2n \choose n}$ from the recurrence relation $C_n = C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_{1}+C_{n-1}C_0$
Now it's seen that the generating function satisfies $xf^2-f+1=0$ so $f=\frac{1-\sqrt{1-4x}}{2x}$ since the other root has a pole at 0 but I'm struggling to see how $f=\frac{1-\sqrt{1-4x}}{2x}$ can be expanded to obtain the necessary power series
I've seen Wikipedia's proof but I don't see how ${ \frac{1}{2} \choose n} = \frac{(-1)^{n+1}}{4^n(2n-1)} {2n \choose n}$ nor how this gets lost into ${2n \choose n}$ via plugging y=-4x and putting it into the expression $f=\frac{1-\sqrt{1-4x}}{2x}$
 A: Hint: By binomial theorem, we have $$(1 + z)^\alpha = \sum\limits_{k \geq 0} \binom{\alpha}{k} z^k.$$
Use this for $\alpha = \frac{1}{2}$ on the square root term, and equate coefficients.

Edit: Here, we define $$\binom{\alpha}{k} = \frac{\alpha(\alpha - 1)\cdots(\alpha - (k-1))}{k!}.$$
Note that this agrees with our usual definition when $\alpha$ is an integer.

Edit 2: We have \begin{align}
\frac{1 + \sum_{n \geq 0} \binom{2n}{n} \frac{x^n}{2n - 1}}{2x} &= \frac{1 + (-1) + \sum_{n \geq 1} \binom{2n}{n} \frac{x^n}{2n - 1}}{2x} \\
&= \sum\limits_{n \geq 1}\binom{2n}{n} \frac{x^{n-1}}{(2n-1)2} \\
&= \sum\limits_{n \geq 0} \binom{2n+2}{n+1} \frac{x^n}{2(2n + 1)} \\
&= \sum\limits_{n \geq 0} \frac{(2n + 2)!}{(n+1)!(n+1)!} \frac{x^n}{2(2n + 1)} \\
&=\sum\limits_{n \geq 0} \frac{(2n + 2)(2n+1)(2n)!}{(n+1)(n+1)(n!)(n!)} \frac{x^n}{2(2n + 1)}\\
&= \sum\limits_{n \geq 0} \binom{2n}{n}\frac{x^n}{n + 1}
\end{align}
A: Here  as supplement to the answer of @MarcusM  we show the validity of the binomial identity
\begin{align*}
\binom{\frac{1}{2}}{n}=\frac{(-1)^{n+1}}{4^n(2n-1)} \binom{2n}{n}
\end{align*}
In the following we  use as definition of the binomial coefficient
\begin{align*}
\binom{\alpha}{n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}
\end{align*}

We obtain
  \begin{align*}
\binom{\frac{1}{2}}{n}
&=\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\left(\frac{1}{2}-2\right)\cdots\left(\frac{1}{2}-n+1\right)}{n!}\\
&=\frac{1(-1)(-3)\cdots(3-2n)}{2^nn!}\tag{1}\\
&=\frac{(-1)^{n-1}}{2^nn!}(2n-3)!!\tag{2}\\
&=\frac{(-1)^{n-1}}{2^nn!(2n-1)}(2n-1)!!\tag{3}\\
&=\frac{(-1)^{n-1}}{2^nn!(2n-1)}\cdot\frac{(2n)!}{(2n)!!}\tag{4}\\
&=\frac{(-1)^{n-1}}{2^nn!(2n-1)}\cdot\frac{(2n)!}{2^nn!}\tag{5}\\
&=\frac{(-1)^{n+1}}{4^n(2n-1)}\cdot\frac{(2n)!}{n!n!}\tag{6}\\
&=\frac{(-1)^{n+1}}{4^n(2n-1)}\binom{2n}{n}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we factor out $2^n$

*In (2) we factor out $(-1)^n$ use as convenient notation double factorial 
\begin{align*}
(2n)!!&=(2n)(2n-2)(2n-4)\cdots 4\cdot 2\\
(2n-1)!!&=(2n-1)(2n-3)(2n-5)\cdots 3\cdot 1\\
\end{align*}

*In (3) we multiply the expression with $\frac{2n-1}{2n-1}$ and use $(2n-3)!!(2n-1)=(2n-1)!!$

*In (4) we use the identity
\begin{align*}
(2n)!=(2n)!!(2n-1)!!
\end{align*}

*In (5) we use the identity
\begin{align*}
(2n)!!=(2n)(2n-2)\cdots4\cdot2=2^n n!
\end{align*}

*In (6) we do a small rearrangement
