# Odd Binomial Coefficients?

By Newton's Formula: $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k$$ Proof that every $\dbinom{n}{k}$ is odd 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$".

-
@Mario: You are using $k$ twice. I think it would be better if you change it to $n = 2^m - 1$. –  user17762 May 22 '12 at 3:59
Consider polynomial $(x+1)^n$ on $\mathbb{Z}_{2}[x]$. –  y zhao May 22 '12 at 4:20
See this answer for a follow up to the hint by y zhao. A (somewhat compressed) proof of Lucas' Theorem cited by Arturo is in there. –  Jyrki Lahtonen May 22 '12 at 4:57

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

-
@ArturoMagidin aah, yes. Will update it. –  user17762 May 22 '12 at 4:23
The equation $$\sum_{i=0}^{l} n_i = \sum_{i=0}^{l} k_i + \sum_{i=0}^{l} (n-k)_i$$ is what Arturo says as no carry. –  user17762 May 22 '12 at 4:27
@ArturoMagidin You do not need to delete the comments in future. –  user17762 May 22 '12 at 4:29
Marvis: I have a question, $$\sum_{i=1}^l \left \lfloor{\frac{n}{p^i}} \right \rfloor.$$ The right side, with subindexation with the $\sum$. –  Mario De León Urbina May 23 '12 at 1:20
@Mario De León Urbina I don't understand your comment. Can you elaborate it? –  user17762 May 23 '12 at 1:50

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