Catalan numbers formula derivation

Question

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

Answer 1

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}

Answer 2

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