Trouble deriving the Catalan numbers (near the last step)

Question

The final result should be $C(n) = \frac{1}{n+1}\binom{2n}{n}$, for reference.

I've worked my way down to this expression in my derivation:

$$C(n) = \frac{(1)(3)(5)(7)...(2n-1)}{(n+1)!} 2^n$$

And I can see that if I multiply the numerator by $2n!$ I can convert that product chain into $(2n)!$ like so, also taking care to multiply the denominator all the same:

$$C(n) = \frac{(2n)!}{(n+1)!(2n!)} 2^n =\frac{1}{n+1} \cdot \frac{(2n)!}{n!n!} 2^{n-1} = \frac{1}{n+1} \binom{2n}{n} 2^{n-1}$$

Where did I go wrong? Why can't I get rid of that $2^{n-1}$?

Answer 1

You should multiply top and bottom by $n!$ instead:

$$n!\cdot 2^n=2\cdot4\cdot6\cdot\ldots\cdot(2n)\;,$$

and multiplying this by $1\cdot3\cdot5\cdot\ldots\cdot(2n-1)$ gives you $(2n)!$.

In the denominator you’ll have $(n+1)!n!=(n+1)n!n!$, so the whole thing will be

$$\frac1{n+1}\binom{2n}n\;,$$

just as you want.

Multiplying the product of the odd integers by $(2n)!$ just makes it messy; you need to multiply it by $2\cdot4\cdot\ldots\cdot(2n)$, the product of the missing even factors, to get $(2n)!$, and that’s $2^nn!$. You already have the $2^n$ so you just need the $n!$.

Answer 2

$$\frac{(2n-1)!!}{(n+1)!}2^n = \frac{(2n)!}{(2n)!! (n+1)!}2^n = \frac{(2n)!}{2^n n! (n+1)!}2^n = \frac{1}{n+1}\cdot\frac{(2n)!}{n!^2}=\frac{1}{n+1}\binom{2n}{n}.$$