$\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─





*

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

*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.
 A: 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.
A: 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─


*

*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)

*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)$).

*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!
