$\frac{(2n-1)!}{n! (n-1)!}$ is even whenever $n$ is not a power of $2$

Question

I am studying Higher Algebra by Barnard and Child.

I am asked to prove (in Exercise-I, Problem-$33$)

$\frac{(2n-1)!}{n! (n-1)!}$ is odd or even according as $n$ is, or is not, a power of $2$.

I deduce─ this is equivalent to the following─

$\frac{(2n-1)!}{n! (n-1)!}$ is odd if and only if $n$ is a power of $2$.

I have been able to prove the if part─

$\frac{(2n-1)!}{n! (n-1)!}$ is odd if $n$ is a power of $2$.

I used those two facts─

1. If $p=2^r$, then highest power of $2$ contained in $p!$ is $p-1$.
2. If $p=2^r-1$, then highest power of $2$ contained in $p!$ is $p-r$.

Now remains the converse─

$\frac{(2n-1)!}{n! (n-1)!}$ is odd only if $n$ is a power of $2$.

I know this maybe (or maybe not) provable by Lucas Theorem or its generalizations.

But I want a proof with more elementary ideas than Lucas theorem. Especially, no Number Theory concepts starting from Congruence and on.

Thanks in advance.

Answer 1

For the converse, assume $$\frac{(2n-1)!}{n! (n-1)!}$$ is odd.

Suppose $n$ is not a power of $2$.

Equivalently, suppose$\;2^k < n < 2^{k+1}\!,\;$for some positive integer $k$.

Our goal is to derive a contradiction.

Claim: ${\large{\binom{2n}{n}}}$ is a multiple of $4$.

Let $x$ be the product of the odd integers from $1$ to $2n-1$ inclusive.

Identically, we have \begin{align*} {\small{\binom{2n}{n}}} &= {\small{\frac{(2n)!}{(n!)^2}}}\\[4pt] &= {\small{\frac{(2n)(2n-1)\cdots(1)}{(n!)^2}}}\\[4pt] &= {\small{\frac{\bigl((2n)(2n-2)\cdots(2)\bigr)\bigl((2n-1)(2n-3)\cdots(1)\bigr)}{(n!)^2}}}\\[4pt] &= {\small{\frac {\bigl((2^n)(n!)\bigr)(x)}{(n!)^2}}}\\[4pt] &= {\small{\frac {(2^n)(x)}{n!}}}\\[4pt] \end{align*} Let $e$ be the greatest nonnegative integer such that $2^e{\,\mid\,}n!$.

To prove ${\large{\binom{2n}{n}}}$ is a multiple of $4$, it suffices to show $e \le n-2$. \begin{align*} \text{Then}\;\;e &= \sum_{i=1}^k \left\lfloor {\small{\frac{n}{2^i}}} \right\rfloor \\[4pt] &\le \sum_{i=1}^k {\small{\frac{n}{2^i}}}\\[4pt] &= n\sum_{i=1}^k {\small{\frac{1}{2^i}}}\\[4pt] &= n\left(1-{\small{\frac{1}{2^k}}}\right)\\[4pt] &< n\left(1-{\small{\frac{1}{n}}}\right)\\[4pt] &= n-1 \end{align*} Therefore $e \le n-2,\;$hence ${\large{\binom{2n}{n}}}$ is a multiple of $4$, as claimed. \begin{align*} \text{Then}\;\;&4{\Large{\mid}}{\small{\binom{2n}{n}}}\\[6pt] \implies\;&4{\Large{\mid}}{\small{\frac{(2n)!}{(n!)^2}}}\\[4pt] \implies\;&4{\Large{\mid}}{\small{\frac{(2n)(2n-1)!}{(n!)^2}}}\\[4pt] \implies\;&2{\Large{\mid}}{\small{\frac{(2n-1)!}{n!(n-1)!}}}\\[4pt] \end{align*} contradiction, which completes the proof.

Answer 2

I have found another solution. I have proved─

If $n$ is not a power of $2$, then $\frac{(2n-1)!}{n! (n-1)!}$ is even.

---

My strategic points are─

1. If $s_{(x,p)}$ is the sum of digits of a non-negative integer $x$ in its $p$-base expansion, then the highest power of $p$ that divides $x!$ is $\dfrac{x-s}{p-1}$, where $p$ is a prime. (This is, in fact, a well-known result)
2. According to $(1)$, $\frac{(2n-1)!}{n!(n-1)!}$ is even $\Leftrightarrow \dfrac{2n-1-s_{(2n-1,2)}}{2-1} > \dfrac{n-s_{(n,2)}}{2-1} + \dfrac{n-1-s_{(n-1,2)}}{2-1} \Leftrightarrow s_{(2n-1,2)}< s_{(n,2)}+ s_{(n-1,2)}$ (Notice, $n+(n-1)=(2n-1)$).
3. But $s_{(x,p)}$ for base-$2$, that is, $s_{(x,2)}$, is simply the numbers of $1$s in the binary expansion of $x$.

   ---

So, I determined that it will suffice to prove the following─

If $n$ is not a power of $2$, then the number of $1$s in the binary expansion of $(2n-1)$ is strictly less than total number of $1$s in the binary expansions of $n$ and $(n-1)$.

Let me show it.

I start by introducing two notation─ by $1_m$, for integer $m \geq 0$, I will mean the $m-$digit binary number with each of its digits is $1$─ and by $+0_m$ as the last term of an expression, I will simply mean, the value of the rest part of the expression has $m$ trailing $0$s.

---

We have, as $n$ is not a power of $2$, $$n = A \times 2^{k+1} \color{lime}{ +a_k2^k+0_k}$$, where $A \neq 0$, $a_k=1$ and integer $k \geq 0$.

Yes, $A \neq 0$ and $a_k=1$ together reflect the fact that

If the positive integer $n$ is not a power of $2$, then the binary expansion of $n$ contains at least two $1$s.

And, yes, $a_k$ is the first $1$ from right in the the binary expansion of $n$.

Then,

$$n-1 = A \times 2^{k+1} \color{lime}{ +0 \times 2^k+ 1_k}$$

As $n$ is not a power of $2$, the binary expansions of $n$ and $(n-1)$ are of same number of digits. And Only in the position(s) starting from the rightmost position upto (including) $k$-th position, $n$ and $(n-1)$ differ in digit.

And $$2n = A \times 2^{k+2} \color{lime}{ +a_k2^{k+1}+0_{k+1}}$$

Next, $$2n-1 = A \times 2^{k+2} \color{lime}{ +0 \times 2^{k+1}+1_{k+1}}$$

Now, we see, total number of $1$s in the green parts in $n$ and $(n-1)$ together equals the number of $1$s in the green part of $(2n-1)$. So, we can ignore the green parts in $n$, $(n-1)$ and $(2n-1)$.

Looking at the not-green parts of $n$, $(n-1)$ and $(2n-1)$, as $A \neq 0$, we can now see what we want to see─

If $n$ is not a power of $2$, then the number of $1$s in the binary expansion of $(2n-1)$ is strictly less than total number of $1$s in the binary expansions of $n$ and $(n-1)$. (Q.E.D.)

---

I am not expert in typing and latex. So, this write-up may contain typos. Please correct me. Thanks!

Answer 3

By Contrapositive

First of all, we split the fraction into two as

$$ \begin{aligned} \frac{(2 n-1) !}{n !(n-1) !} & =\frac{\prod_{k-1}^{n-1}(2 k)}{(n-1) !} \cdot \frac{\prod_{k-1}^n(2 k-1)}{n !} \\ & =\frac{2^{n-1}(n-1) !}{(n-1) !} \cdot \frac{D}{n !} \\ & =\frac{2^{n-1}D}{n !} \end{aligned} $$ $\text { where } D=\prod_{k=1}^n(2 k-1) \text { is odd. }$

Then we are going to prove that if $n$ is not a power of $2$, then $\frac{2^{n-1}(n-1) !}{(n-1) !} $ is odd.

Proof:

If $n$ is not a power of 2, then we can express $n=2^mp$ for some odd integer $p>1$ and integer m. By Legendre's formula, the highest power of $2$ divides $n$ is denoted and found as

$$\displaystyle \nu_p(n !)=\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^i}\right\rfloor\tag*{} $$ by which, we have $$\displaystyle \begin{aligned} \nu_2(n !)&=\sum_{i=1}^{\infty}\left\lfloor\frac{2^mp}{2^i}\right\rfloor \\&=p\left(2^{m-1}+2^{m-2}+\cdots+1\right)+\left\lfloor\frac{p}{2}\right\rfloor+\left\lfloor\frac{p}{2^2}\right\rfloor+\cdots \\&=p(2^m-1) +\left\lfloor\frac{p}{2}\right\rfloor+\left\lfloor\frac{p}{2^2}\right\rfloor+\cdots \\&=p(2^m-1) +\left\lfloor\frac{p-1}{2}\right\rfloor+\left\lfloor\frac{p-1}{2^2}\right\rfloor+\cdots \quad \textrm{ As } p \textrm{ is odd greater than }1. \\&< p\left(2^m-1\right)+(p-1)\left(\frac{1}{2}+\frac{1}{2^2}+\cdots\right)\\&= p\left(2^m-1\right)+p-1\\&=n-1\end{aligned}\tag*{}$$

In other words, $ \nu_2(n !) \le n-2$ and hence $\frac{2^{n-1}D}{n !}$ is even. Now we can conclude that $$\frac{2^{n-1}(n-1) !}{(n-1) !} \textrm{ is odd. } \Rightarrow n \textrm{ is power of }2. $$