7
$\begingroup$

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

  • 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?2011-03-25

3 Answers 3

5

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. Ah, BTW, you probably need $k < \min(a,b)$.

  • 0
    Okay, this theorem is true for a=b, but your proof won't work in that case.2011-03-25
4

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

  • 0
    @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$2011-03-25
2

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