Oddness of Binomial Coefficients

 There are well known theorems like Lucas' or Kummer's which allow one to figure out exactly which binomial coefficients $\binom{n}{k}$ are odd.

The goal of this (slightly open ended) puzzle is to not use these theorems and still come up with a characterization of the $n,k$ for which $\binom{n}{k}$ is an odd number.

Scroll down for one simple "elementary" way.

.

.

.

.

.

We prove the following:

$\textbf{Claim:}$ Given an $n = \sum 2^{e_i}, e_i \text{ distinct} $ , then we have that $\binom{n}{k}$ is odd iff $k$ is the sum of some subset of the $2^{e_i}$. i.e $k$ is written only using the "set" bits of $n$. The empty set corresponds to $k = 0$.

$\textbf{Proof:}$

Consider polynomials where the coefficients are either $0$ (for even) or $1$ for odd, with the rule that $1 + 1 = 0$.

So we have $1 - 777x$ being equivalent to $1 + x$, because negative of odd is still odd etc.

And $13 + 200x + 999x^2 $ is equivalent to $1 + x^2$ since $200$ becomes $0$ and even times anything is even and so evens act like zero.

[In advanced terms we are working over $GF(2)$]

Now consider $(1 + x)^2 = 1 + 2x + x^2 = 1 + x^2$

Similarly $$(1  + x)^4 = ((1 + x)^2)^2 = (1 + x^2)^2 = 1 + x^4$$

Thus by induction we see that

$$(1 + x)^{2^m} = 1 + x^{2^m}$$

Thus if $n = \sum 2^{e_i}$ (i.e we look at the binary representation of $n$) then

$$(1 + x)^n = \prod (1 + x)^{2^{e_i}} = \prod \left(1 + x^{2^{e_i}}\right)$$

Now

$$\prod \left(1 + x^{2^{e_i}}\right) = \sum x^{m_i}$$

where $m_i$ are exactly the numbers which can be written as the sum of some subset of $2^{e_i}$. Since this gives a binary representation of $m_i$, the representation is unique and the coefficient is $1$.

This proves the above claim.

$\textbf{Additional Remark:}$ This method also works for an arbitrary prime $p$ and we have the following:

$\textbf{Claim:}$ $\binom{n}{k}$ is not divisible by $p$ iff each digit of $k$ in base-$p$ is $\leq$ the corresponding digit in $n$ (in base-$p$).

Note that the characterization we got earlier for $p=2$ is equivalent to this.