5
$\begingroup$

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

Please, help me! Thanks.

  • 0
    See [this answer](http://math.stackexchange.com/a/82338/11619) for a follow up to the hint by y zhao. A (somewhat compressed) proof of Lucas' Theorem cited by Arturo is in there.2012-05-22

3 Answers 3

1

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.

4

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.

4

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

  • 0
    @Mario De León Urbina I don't understand your comment. Can you elaborate it?2012-05-23