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$?
 A: 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)$.
A: 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
A: 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$.
