Odd Binomial Coefficients?

Question

By Newton's Formula: $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}\,b^k $$

Prove that$\dbinom{n}{k}$ is odd for every $k=0,\dots, n$ if and only if $n=2^r-1$.

I have already shown that if $n$ is of the form $2^r-1$, having used the property $$\binom{n-1}{k} = \binom{n}{k}-\binom{n}{k-1}+ \binom{n}{k-2} - \cdots \pm \binom{n}{0}.$$ But I have not been able to demonstrate "$\Rightarrow$".

Please, help me! Thanks.

Answer 1

We will prove that $p$ does not divide $\dbinom{n}{k}$ for any $k \in \{0,1,2,\ldots,n\}$ iff $ n = p^m-1$.

Write $n$ in base $p$ as $$n = \sum_{i=0}^{l} n_i p^i$$ The highest power of $p$ that divides $n!$ is $$\left \lfloor \frac{n}{p} \right \rfloor + \left \lfloor \frac{n}{p^2} \right \rfloor + \cdots + \left \lfloor \frac{n}{p^l} \right \rfloor = \sum_{i=1}^{l} n_i p^{i-1} + \sum_{i=2}^{l} n_i p^{i-2} + \cdots + \sum_{i=l}^{l} n_i p^{i-l}\\ = \sum_{i=1}^{l} n_i \left( p^{i-1} + p^{i-2} + \cdots + 1\right) = \sum_{i=0}^{l} n_i \left( p^i - 1 \right) = n - \sum_{i=0}^{l} n_i$$

The power of $p$ that divides the binomial coefficient $\dbinom{n}{k}$ is nothing but $$(n - \sum_{i=0}^{l} n_i) - (k - \sum_{i=0}^{l} k_i) - (n -k - \sum_{i=0}^{l} (n-k)_i) = \sum_{i=0}^{l} k_i + \sum_{i=0}^{l} (n-k)_i - \sum_{i=0}^{l} n_i$$

Hence, $p \not \vert \dbinom{n}{k}$ if and only if $$\sum_{i=0}^{l} k_i + \sum_{i=0}^{l} (n-k)_i - \sum_{i=0}^{l} n_i = 0$$ i.e. $$\sum_{i=0}^{l} n_i = \sum_{i=0}^{l} k_i + \sum_{i=0}^{l} (n-k)_i$$ This means that $n = p^m - 1$ for some $m$.

Answer 2

This follows easily from Kummer's Theorem, that the highest power of a prime $p$ that divides $\binom{n}{m}$ is equal to the number of "carries" when adding $n-m$ and $m$ in base $p$. In particular, $\binom{n}{m}$ is odd if and only if there are no carries when adding in base $2$. If the binary expression for $n$ has any $0$s, then selecting $m$ to have a $1$ at precisely the first $0$ and $0$s elsewhere gives a value with $\binom{n}{m}$ even. So the expression for $n$ must consist entirely of $1$s, i.e., $n$ must be of the form $n^r-1$ for some $r$. (Note that this argument shows that the same conclusion holds if "odd" and $2$ are replaced by "prime to $p$" and $p$".)

The result also follows from the Lucas' Theorem, which describes the remainder of $\binom{n}{m}$ when divided by a prime $p$.

See also this previous question.

Answer 3

Since $\binom{n}{k} = \binom{n}{k-1}\times \frac{n+1-k}{k}$, inductively we must have that the highest power of 2 dividing $n+1-k$ is the same as the highest power of 2 dividing $k$, for all $1\leq k \leq n$.

Write $n+1$ in binary as $n+1 = \sum_j b_j 2^j$, and suppose that $b_k$ is the first non-zero bit. Then $n+1 - 2^k$ has a binary representation with all bits zero up to $k+1$, and thus is divisible by $2^{k+1}$. However, $2^k$ is not divisible by $2^{k+1}$. This contradicts the first paragraph unless $2^k > n$, and since $2^k \leq n+1$ we must have $2^k = n+1$. QED