I encountered a derivation for finding the nth Catalan Number $C_n$ using generating functions in the book Diskrete Strukturen, Band 1 (Steger 2007, p.178).
Given is the recursive function $C_0 := 1$, $C_n := \sum_{k=1}^n C_{k-1}C{n-k} \;\;\; (\forall n \geq 1)$.
The first part of the proof shows how to obtain the equality:
$$ C_n = -\frac{1}{2}\binom{1/2}{n+1}(-4)^{n+1}$$
I understand that part so no need to go into further detail on it. However, the following simplification steps are only sparsely commented in the book:
\begin{align*} C_n &= -\frac{1}{2}\binom{1/2}{n+1}(-4)^{n+1}\\ &= -\frac{1}{2}\frac{\frac{1}{2} (\frac{1}{2} - 1) (\frac{1}{2} - 2) \ldots(\frac{1}{2} - n)}{ (n+1)!}(-4)^{n+1}\\ &= \frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1) \cdot 2^n}{ (n+1)!}\\ &= \frac{1}{n+1}\frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1)}{ n!} \frac{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n}{1 \cdot 2 \cdot 3 \cdot \ldots \cdot n}\\ &= \frac{1}{n+1}\binom{2n}{n} \end{align*}
I can see how the first two equalities are justified, but I don't see how the the last three equalities came to be. I suspect that I am just missing some essential identities and that knowing these will make these steps rather easy. In any case, a more rigorous walkthrough would be much appreciated.
Thanks for the help & best wishes, Rafael
For the third equality, \begin{align*} -\frac{1}{2}\frac{\frac{1}{2} (\frac{1}{2} - 1) (\frac{1}{2} - 2) \ldots(\frac{1}{2} - n)}{ (n+1)!}(-4)^{n+1}&= (-1)^n\cdot\frac{1}{2}\cdot\left(\frac{1}{2}\right)^{n+1}\frac{1(2-1)(4-1)\cdots(2n-1)}{(n+1)!}(-1)^n4^{2n+2}\\ &= 2^{-n-2}4^{2n+2}\frac{1\cdot 3\cdot 5\cdots 2n-1}{(n+1)!} \\ &= \frac{1\cdot 3\cdot 5\cdots (2n-1)\cdot 2^n}{(n+1)!}. \end{align*} The fourth equality results from multiplying top and bottom by $1\cdot 2\cdot 3 \cdots n$ and distributing the factor of $2^n$ across these terms in the numerator. Finally, this gives \begin{align*} \frac{1}{n+1}\frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n-1)}{ n!} \frac{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n}{1 \cdot 2 \cdot 3 \cdot \ldots \cdot n} &= \frac{1}{n+1}\frac{1\cdot 2\cdot 3\cdots 2n}{n!(1\cdot 2\cdot 3\cdots n)} \\ &= \frac{1}{n+1} \frac{(2n)!}{(n!)^2} \\ &= \frac{1}{n+1}\binom{2n}{n}. \end{align*}