Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
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

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


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.