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.

Looks very easy, but I can't make it:

$s \geq 2$ and $w \geq 2$ are prime numbers. $k$ is a natural number and $k \leq \min \{s,w \}$

Show that $\binom{s+w}{k}-\binom{w}{k} - \binom{s}{k}$ can be divided by $sw$.

share|improve this question
3  
Interesting question! However, I think we need to require that $k\leq s,w$; the only convention I'm aware of is $\binom{n}{k}=0$ when $k>n$, and it is easy to construct counterexamples to the claim in this scenario (for example $k=s+w$). –  Zev Chonoles Jul 17 '11 at 16:47
2  
@Spore234 A small note: When you say $s,w$ are primes, there is no need to also mention they are $\geq 2$, since all primes are $\geq 2$. –  Eric Naslund Jul 17 '11 at 17:08

2 Answers 2

up vote 5 down vote accepted

As Zev mentions, we do need some bounds on $k$. We have your statement for $0\leq k\leq \min(s,w)$. Here I will prove it for $1\leq k\leq \min(s-1,w-1)$. (The other cases are not much different) The goal is to look at your expression modulo $s$ and modulo $w$ and show it is $0$ in both cases.

Proof: Expanding the binomials we have $$\frac{(s+w)(s+w-1)\cdots(s+w-k+1)}{k!}-\frac{s(s-1)\cdots (s-k+1)}{k!}-\frac{w(w-1)\cdots(w-k+1)}{k!}.$$ Then since $s,w$ are primes, $k!$ is invertible, so that modulo $s$ this is

$$\equiv \frac{(w)(w-1)\cdots(w-k+1)}{k!}-\frac{w(w-1)\cdots(w-k+1)}{k!}\equiv 0\pmod{s}.$$

Similarly for $w$. Hence the original expression is divisible by both $s$ and $w$.

Elaboration: Because $1\leq k<s$, $k!$ will be relatively prime to $s$ so that dividing by $k!$ makes "sense." Then we can write $\frac{1}{k!}\equiv a \pmod{s}$ for some integer $a$. Using this, the term $$\frac{s(s-1)\cdots (s-k+1)}{k!}\equiv as(s-1)\cdots (s-k+1),$$ and must be divisible by $s$. The fraction $$\frac{(s+w)(s+w-1)\cdots(s+w-k+1)}{k!}\equiv a(s+w)(s+w-1)\cdots(s+w-k+1)$$ $$\equiv a(w)(w-1)\cdots(w-k+1)\pmod{s}$$ since each $s$ is equivalent to zero.

share|improve this answer
    
thanks. It is becoming more clear, but can you elaborate the second step a bit. Expanding the binomials is clear, I've been this far myself. We did this in a statistics class, I'm not really a number theorist. –  spore234 Jul 17 '11 at 17:51
1  
@spore234: I put an extra note in. Tell me if there is anything else. –  Eric Naslund Jul 17 '11 at 18:09
    
thanks for elaborating, but I still don't understand this step: $a(s+w)(s+w-1)\cdots(s+w-k+1) \equiv a(w)(w-1)\cdots(w-k+1)\pmod{s}$ –  spore234 Jul 18 '11 at 18:09
1  
@spore234: Ok. When we work $\pmod{s}$ we are looking at the remainder after division by $s$, so adding in an integer multiple of $s$ doesn't change anything. Lets do two variables. We have that $(a+s)(b)=ab+sb\equiv ab \pmod {s}$. In the same way, $(a+s)(b+s)(c+s)\equiv (a)(b)(c)\pmod{s}$, and this generalizes to any number of variables as above. Here is another way to look at it: We are just trying to show that above quantity is divisible by $s$. Well, if we split up $(s+w)$ the term with the $s$ is already divisible by $s$ so we don't have to worry about it. –  Eric Naslund Jul 18 '11 at 18:21

HINT $\ $ Scale by $\rm\:k!\:$ then use $\rm\ f(0) = 0\ \Rightarrow\ x\:y\ |\ f(x+y) - f(x) - f(y)\:$ for $\rm\:f(x)\in \mathbb Z[x]\:.$

Your problem is the special case is $\rm\ f(x) = x\ (x-1)\:\cdots\:(x-k+1)\:,\ \ x = s,\ y = w\:.$

share|improve this answer
    
Nice structural argument, which has the additional advantage of working when $s=w$. –  André Nicolas Jul 17 '11 at 21:17

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.