Why is ${2n \choose n}/2 $ odd if and only if $n=2^k$?

Question

If we consider the numbers ${2n \choose n}/2 $ for $n$ small:

[ 1, 1 ][ 2, 3 ][ 3, 10 ][ 4, 35 ][ 5, 126 ][ 6, 462 ][ 7, 1716 ][ 8, 6435 ] [ 9, 24310 ][ 10, 92378 ][ 11, 352716 ][ 12, 1352078 ][ 13, 5200300 ] [ 14, 20058300 ][ 15, 77558760 ][ 16, 300540195 ]

we observe that ${2n \choose n}/2 $ is odd if and only if $n$ is a power of $2$.

We can easily check with a computer that it is true for $n \le 2^{10}$, so that we can expect it is true in general.

Question: What's the proof?

Answer 1

[I'd love to see a combinatorial argument.]

More generally, if $d$ is the largest integer such that $2^d$ divides $\binom{2n}{n}$, then $d$ is the number of non-zero binary digits of $n$.

There is a general formula for the highest power of a prime $p$ that divides $m!$:

$$\sum_{k=1}^{\infty}\left\lfloor\frac{m}{p^k}\right\rfloor$$

So the number of powers of $2$ that divide $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ is:

$$\sum_{k=1}^{\infty} \left(\left\lfloor\frac{n}{2^{k-1}}\right\rfloor -2\left\lfloor\frac{n}{2^k}\right\rfloor\right)$$

Every term here is positive because $\lfloor 2x\rfloor - 2\lfloor x\rfloor\geq 0$.

When $2^{k-1}\leq n<2^k$, we get a term of $1$ in this sum.

When $n=2^{k-1}$ this is the only non-zero term in this sum.

Now, if $\frac{n}{2^{k-1}}$ is an integer and odd, then the $k$th term is again $1$. The only way for the sum to be $1$ is if these two terms are the same.

What you can actually show is that the $k$th term in this sum is the $(k-1)$th binary digit of $n$.

---

There ought to be some combinatorial argument. We can see that $\binom{2n}{n}$ is divisible by $2$ combinatorially by using the complement function on the $n$-subsets of $\{1,2,\dots,2n\}$. Is there another action of order $2$ we can find which commutes with this one if $n$ is not a power of $2$?

Answer 2

Let we define the $2$-adic height as $$\nu_2(n)=\max\{h\in\mathbb{N}: 2^h\mid n\}.\tag{1}$$ Legendre's theorem gives $$ \nu_2(n!)=\sum_{k\geq 1}\left\lfloor\frac{n}{2^k}\right\rfloor \tag{2} $$ hence it follows that: $$ \nu_2\binom{2n}{n}=\nu_2\left(\frac{(2n)!}{n!^2}\right)=\sum_{k\geq 1}\left(\left\lfloor\frac{2n}{2^k}\right\rfloor-2\left\lfloor\frac{n}{2^k}\right\rfloor\right)=\sum_{k\geq 1}f_k(n). \tag{3}$$ We may notice that $f_1(n)$ equals $1$ if $n$ is odd and $0$ otherwise.
In general, $f_k(n)$ depends on the structure of the binary representation of $n$.
From that, it is not difficult to prove the given conjecture - since it gives that $\nu_2\binom{2n}{n}$ equals one iff there is a single $1$ in the binary representation of $n$.

Answer 3

We can start with $\nu_2(2^k!)=2^k-1$. This immediately gives the result for $n=2^k$ because $\nu_2(\binom{2n}{n})=\nu_2(2n!)-2\nu_2(n!)$.

Then we observe that $n$ can be written as $n=\sum\limits_{i=0} 2^i$, and then $\nu_2(n!)=\sum\limits_{i\in I} \nu_2(2^i!)$.

The result follows trivially.

Answer 4

By Kummer's theorem, the number of prime factors $p$ in a binomial coefficient $\binom {a+b}a=\binom {a+b}b$ is the number of carries arising when adding $a+b$ represented as numbers in base$~p$. Taking $p=2$ and $a=b=n$, it is easy to see that you get one carry (and so one factor$~2$) for every bit '$1$' in the binary representation of $n$; you get one carry precisely when the representation has a single bit '$1$', which is when $n$ is a power of $2$.