Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@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
2  
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
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
@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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.