2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You want to prove something number theoretic, but without number theory concepts, do I get that right? $\endgroup$ – Professor Vector Feb 7 '18 at 11:26
  • 1
    $\begingroup$ @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. $\endgroup$ – Muhammad Rasel Parvej Feb 7 '18 at 11:33
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Muhammad Rasel Parvej Feb 8 '18 at 14:11
  • $\begingroup$ @Muhammad Rasel Parvej: I just finished checking your solution -- it's nice (+1), although I like my solution just as much! $\endgroup$ – quasi Feb 8 '18 at 14:36
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.