<s>[INST] 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}$
 [/INST] 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
</s>