# Combinatorics question: Show divisibility

Let $a\geq2$, $b\geq2$ be two prime numbers and k be a natural number with $k\leq min(a,b)$.

How can one show that $z := \binom{a+b}{k} - \binom{a}{k} - \binom{b}{k}$ is divisible by the product $ab$?

-
Try simply proving the given expression is divisible by a (prime). Once you have that (and b is similar/symmetric), what can you conclude? –  hardmath Mar 25 '11 at 14:48

First, you need to suppose that $k>0$, because otherwise $z=-1$. Next, it's easy to see that $p \choose k$ is a multiple of $p$ for $0 < k < p$ because $k!$ in the denominator does not have a $p$ factor. That leaves us with proving that ${{a+b} \choose k} - {b \choose k}$ is a multiple of $a$. Consider the numerator: $(a+b)(a+b-1)\cdots - b(b-1)\cdots$. Note that $(a+b)(a+b-1)\cdots$ is congruent mod $a$ to $b(b-1)\cdots$. Hence the numerator is a multiple of $a$ and so is ${{a+b} \choose k} - {b \choose k}$ because $k<a$. Ah, BTW, you probably need $k < \min(a,b)$.

-
Is the theorem true when a=b? This proof doesn't work when a=b. –  Thomas Andrews Mar 25 '11 at 17:51
Okay, this theorem is true for a=b, but your proof won't work in that case. –  Thomas Andrews Mar 25 '11 at 18:21

HINT $\$ This easily reduces to the following more general result about polynomials.

THEOREM $\:$ Suppose that $\rm\ f(x)\in R[x]\:$ is a polynomial over the ring $\rm\:R\:$ and suppose also $\rm\:f(0) = 0\:.$ Then $\rm\ x\:y\:$ divides $\rm\ f(x+y) - f(x) - f(y)\$ in $\rm\: R[x,y]\:.$

Proof $\$ By linearity it suffices to show that $\rm\: x\:y\:$ divides $\rm\: (x+y)^n - x^n - y^n\$ in $\rm\:R[x,y]\:$ for $\rm\:n > 0\:.\:$ But this is obvious by the Binomial Theorem.$\quad$ QED

-
What ring are you using, integers, or rationals? Because (x choose k) is not an integer polynomial, so the fact that the polynomial xy divides f(x+y)-f(x)-f(y) as polynomials doesn't mean that they divide each other as integers. –  Thomas Andrews Mar 25 '11 at 17:50
@Thomas: As I said, you need to reduce to it. Hint: by the theorem $\rm\ z\ =\ ab\ g(a,b)/k!\ \in \mathbb Z\:,\$ for $\rm\:g \in \mathbb Z[x,y]\:.\$ But, by hypothesis, $\rm\:k!\:$ is coprime to $\rm\:ab\:$ so $\ldots$ –  Bill Dubuque Mar 25 '11 at 18:21

Let $A$ and $B$ be disjoint sets of size $a$ and $b$, and let $S$ be the sets of subsets of $A\cup B$ of size k which contain at least one element of $A$ and one element of $B$.

Then we can find an action of the additive group $\mathbb{Z}_a\oplus\mathbb{Z}_b$ on $S$ which acts by rotating the elements of $A$ and $B$ separately. You can make a pretty easy argument that each of the orbits of this action on $S$ has size $ab$. (This is where you need the upper limit on $k$. When $k\leq a$, the subset cannot include all of $A$, and likewise for $b$ and $B$.) so you can show that the size of $S$ must be a multiple of $ab$. But the size of $S$ is just:

$${{a+b} \choose {k}} - {{a}\choose{k}}- {{b}\choose{k}}$$

when $\operatorname{min}(a,b)\geq k>0$.

Similar results:

If $a\leq k \leq b$ then:

$${{a+b} \choose {k}} - {b \choose {k-a}} - {b \choose k}$$

is divisible by $ab$.

If $a+b > k \geq \operatorname{max}(a,b)$ then:

$${{a+b} \choose {k}} - {b \choose {k-a}} - {a \choose {k-b}}$$

is divisible by $ab$.

-