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

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.

• You want to prove something number theoretic, but without number theory concepts, do I get that right? – Professor Vector Feb 7 '18 at 11:26
• @ProfessorVector Without not all of Number Theory concepts. I am ready to accept Divisibility Results as tools, anything preceding congruence in traditional pedagogy of Number Theory. – Muhammad Rasel Parvej Feb 7 '18 at 11:33

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.

• You could replace your second $\leq$ with $<$, as $n$ is not a power of $2$. Although I am happier with my solution I have just posted, your one is a commendable one too. – Muhammad Rasel Parvej Feb 8 '18 at 14:11
• @Muhammad Rasel Parvej: I just finished checking your solution -- it's nice (+1), although I like my solution just as much! – quasi Feb 8 '18 at 14:36

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!