# Binomial division

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

-
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
@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

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.

-
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
@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
@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\:.$

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