<s>[INST] Understanding derivation of Catalan Numbers 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
 [/INST] 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*}
</s>