Odd Binomial Coefficients?

Solution 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$.

Solution 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.

Solution 3:

Combinatorial Proof

Let $n\in\mathbb{N}\cup \{0\}$. First, it is obvious that, if $\dbinom{n}{k}$ is odd for all $k=0,1,2,\ldots,n$, then $n$ is odd. Suppose now that $n=2m-1$ for some integer $m$. The involution $\tau$ on $[n]:=\{1,2,\ldots,n\}$ is defined by $$\tau(j)=n+1-j$$ for all $j=1,2,\ldots,n$. Then, $\tau_k$ is also an involution on $\dbinom{[n]}{k}=\big\{X\subseteq[n]\,\big|\,|X|=k\big\}$, where $$\tau_k(X):=\big\{\tau(x)\,|\,x\in X\big\}$$ for all $X\in\dbinom{[n]}{k}$. Note that $$\binom{n}{k}\equiv \text{Fix}\left(\tau_k\right)\pmod{2}\,,$$ where $\text{Fix}(f)$ is the number of fixed points of $f:[n]\to[n]$. It is evident that $$\text{Fix}\left(\tau_k\right)=\binom{m-1}{\left\lfloor k/2\right\rfloor}$$ for all $k=0,1,2,\ldots,n$. The claim follows by induction.

There may be a similar combinatorial proof if $2$ is replaced by an odd prime natural number $p$. I would love to see it.