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.

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|improve this question
2  
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
add comment

3 Answers 3

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|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
add comment

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|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
add comment

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|improve this answer
add comment

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.