<s>[INST] Stuck on a step for finding the closed formula for catalan numbers from generating function! I am looking at the Frazer Jarvis paper, entitled Catalan Numbers.
http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec01.pdf
In this paper, he derives the closed formula from the generating function.
The $nth$ Catalan number, denoted $C_n$, is the number of ways
of multiplying together $n$ symbols.
I am stuck on page 7, particularly the following steps:
$\begin{equation}C_n=-\frac{1}{2}\bigg\{\frac{\frac{1}{2}(-\frac{1}{2})(-\frac{3}{2})...(-\frac{2n-3}{2})}{n!}(-4)^n\bigg\}\end{equation}$
$C_n=\frac{1}{2}\bigg\{\frac{\frac{1}{2}(\frac{1}{2})(\frac{3}{2})...(\frac{2n-3}{2})(n-1)!}{n!(n-1)!}(2^2)^n)\bigg\}$
$C_n=\frac{1}{2}\bigg\{\frac{\frac{1}{2}[\frac{1}{2}\cdot 1 \cdot\frac{3}{2} \cdot 2...(n-2)(\frac{2n-3}{2})(n-1)]}{n!(n-1)!}2^{2n}\bigg\}$
$C_n=\frac{1}{2}\bigg\{\frac{\frac{1}{2}(1 \cdot 2 \cdot 3 \cdot 4...(2n-4)(2n-3)(2n-2)}{n!(n-1)!}2^{2}\bigg\}$
Particularly, from the 2nd to the 4th line, I am struggling to understand the steps taken here.
I am confused with what he is doing with the $\frac{1}{2}$. Is he pulling it out in the 3rd step? And most of all, I am very confused with how the $2^n$ went away in the 4th step. If anyone could please help me understand some of the steps that he skipped here, I would really appreciate it! Thank you so much!!!
 [/INST] In the first step he observed that there are $2n$ minus signs, so they cancel out, and he multiplied top and bottom by $(n-1)!$. In the next step he rearranged the factors in the numerator:
$$\begin{align*}
&\frac12\cdot\frac32\cdot\ldots\cdot\frac{2n-3}2(n-1)!\\
&\qquad=\frac12\cdot\frac32\cdot\ldots\cdot\frac{2n-3}2\cdot\color{red}1\cdot\color{red}2\cdot\ldots\cdot\color{red}{(n-1)}\\
&\qquad=\frac12\cdot\color{red}1\cdot\frac32\cdot\color{red}2\cdot\frac52\cdot\color{red}3\cdot\ldots\cdot\color{red}{(n-2)}\cdot\frac{2n-3}2\cdot\color{red}{(n-1)}\\
&\qquad=\frac12\cdot\color{red}{\frac22}\cdot\frac32\cdot\color{red}{\frac42}\cdot\frac52\cdot\color{red}{\frac62}\cdot\ldots\color{red}{\frac{2n-4}2}\cdot\frac{2n-3}2\cdot\color{red}{\frac{2n-2}2}\\
&\qquad=\frac{(2n-2)!}{2^{2n-2}}\,.
\end{align*}$$
Thus, the whole thing is
$$\begin{align*}
\frac12\cdot\frac{\frac12(2n-2)!}{2^{2n-2}n!(n-1)!}\cdot2^{2n}&=\frac14\cdot\frac{(2n-2)!}{n!(n-1)!}\cdot2^{2n-(2n-2)}\\
&=2^{-2}\cdot\frac{(2n-2)!}{n!(n-1)!}\cdot 2^2\\
&=\frac{(2n-2)!}{n!(n-1)!}\\
&=\frac1n\binom{2n-2}{n-1}\,.
\end{align*}$$
I wrote up essentially the same derivation in this answer, if you’d like to see a slightly different take on it.
</s>