Exercise 4.1.9* ($\binom{2n}{n}$ is even)

Question

Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

{\bf First proof.} 
\begin{proof} 
Let $n$ be a positive integer. Then
\begin{align*}
\frac{(2n)!}{(n!)^2} &= \binom{2n}{n}\
&= \frac{2n}{n}\, \frac{(2n-1)!}{(n-1)! n!}\
&= 2 \, \binom{2n-1}{n-1}.
\end{align*}
Therefore $(2n)!/(n!)^2$ is an integer, and is even.
\end{proof}

{\bf Second proof.} 
\begin{proof}
We estimate $
u_2((2n)!/(n!)^2)$ with the Legendre-de Polignac's formula.
\begin{align*}

u_2\left(\frac{(2n)!}{(n!)^2} ight)&= \sum_{i = 1}^\infty \left \lfloor \frac{2n}{2^i} ight floor - 2 \sum_{i=1} ^\infty  \left \lfloor \frac{n}{2^i} ight floor\
&= \sum_{i = 1}^\infty \left \lfloor \frac{n}{2^{i-1}} ight floor - 2 \sum_{i=1} ^\infty  \left \lfloor \frac{n}{2^i} ight floor\
&= n +  \sum_{j= 1}^\infty \left \lfloor \frac{n}{2^{j}} ight floor - 2 \sum_{j=1} ^\infty  \left \lfloor \frac{n}{2^j} ight floor &(j = i-1 	ext{ in the first sum})\
&= n - \sum_{j=1} ^\infty  \left \lfloor \frac{n}{2^j} ight floor\
&= n - 
u_2(n!).
\end{align*}
Moreover, $\left \lfloor \frac{n}{2^j} ight floor\leq \frac{n}{2^j}$ for all $j\geq 1$, and  $0 = \left \lfloor \frac{n}{2^j} ight floor<\frac{n}{2^j}$ if $\frac{n}{2^j} < 1$ (and $n
e 0$), therefore
\begin{align*}

u_2(n!) = \sum_{j=1} ^\infty  \left \lfloor \frac{n}{2^j} ight floor &< \sum_{j=1} ^\infty  \frac{n}{2^j}\
&= n \sum_{j=1} ^\infty \frac{1}{2^j}\
&= n.
\end{align*}
so $
u_2(n!) < n$. Since both $n$ and $
u_2(n!)$ are integers, $n - 
u_2(n!)) \geq 1$, so
$$
u_2\left(\frac{(2n)!}{(n!)^2} ight) \geq 1.$$
This shows that $\frac{(2n)!}{(n!)^2} = \binom{2n}{n}$ is an even integer.
\end{proof}

Exercise 4.1.9* ($\binom{2n}{n}$ is even)

Answers

Comments

Exercise 4.1.9* ($\binom{2n}{n}$ is even)

Answers

Comments

Add answer