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!!!
 A: 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.
A: Start from the second line,
$$
\begin{aligned}
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\}\\
\text{line 3     } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=&\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\}\\
=&\frac{1}{2}\bigg\{\frac{\frac{1}{2}[\frac{1}{2}\cdot \frac 22 \cdot\frac{3}{2} \cdot \frac 42...(\frac{2n-4}{2})(\frac{2n-3}{2})(\frac{2n-2}{2})]}{n!(n-1)!}2^{2n}\bigg\}\\
=&\frac{1}{2}\bigg\{\frac{1}{2^{2n-1}}\frac{(2n-2)!}{n!(n-1)!}2^{2n}\bigg\}\\
=& \frac{(2n-2)!}{n!(n-1)!}=\frac 1n \binom{2n-2}{n-1}.
\end{aligned}$$
A: Step 1 (in the question): $\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}$
Step 2: $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\}$
In step 1, $-\frac{1}{2}, -\frac{3}{2}... -\frac{2n-3}{2}$ has $(n-1)$ terms with negative signs as $2n - 3 = 1 + 2 (n-2)$ and there is $-\frac{1}{2}$ outside curly brackets too. So the negative sign is taken out in step 2 as $(-1)^n \times (-1)^n = (-1)^{2n} = 1$.
Also note there are $n$ $2's$ in the denominator of $\frac{1}{2} (-\frac{1}{2}), (-\frac{3}{2})... (-\frac{2n-3}{2})$
Step 3: $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\}$
i) Writing $4^n$ as $2^{2n}$, ii) In step 2, we multiplied numerator and denominator by $(n-1)!$. We now expand $(n-1)!$ in the numerator as $1 \times 2 \times 3 ...\times (n-1)$ and write in order.
Step 4: $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\}$
In this step we cancel $2^{2n-2}$ in the numerator with $2^{n-1}$ in denominator and we also use $2^{n-1}$ to double each term of $(n-1)!$ from $1 \times 2 \times 3 ..(n-1)$ to $2 \times 4 \times 6 ... \times (2n-2)$ which will lead to numerator as $(2n-2)!$
A: We add the missing even terms of $(2n-2)!$ from the $(n-1)!$ and one portion of $2^{n-1}$.
The other $2^{n-1}$ is cancelled by the $n-1$ pieces of $\frac12$.
