1
$\begingroup$

Good afternoon. I'm looking for a proof, or a counterexample that, given $n,k,N\in\mathbb{Z}$, with $n>k>0$, $N\ge2$,

$$(N+1)|\binom{nN}{kN}$$

Just using the definition,

$$\binom{nN}{kN}=\frac{(nN)!}{[(n-k)N]!(kN)!}$$

without loss of generality, we can assume that $n-k>k$ and can rewrite as

$$\frac{(nN)(nN-1)(nN-2)...[(n-k)N+1][(n-k)N]!}{(kN)(kN-1)(kN-2)...2\cdot 1\cdot[(n-k)N]!}$$ which will cancel the $[(n-k)N]!$'s from the numerator and denominators. Here's where I'm getting some intuition, but can't finish the thought process. Both the numerator and denominator have $kN$ consecutive integers, but the denominator strictly is the product of the first $kN$ integers, and so there must be integers in the numerator which are factorable and can cancel with those in the denominator. But this intuition certainly does nothing to narrow the search for a factor of $N+1$ being left over in the numerator. I'm not sure where to go from here.

EDIT: As I'm pondering, I remember that the product of three consecutive numbers is definitely divisible by 6 (and a proof could be shown by multiplying $(3k-1)3k(3k+1)$ to get $27k^3-3k=3(9k^3-k)$ and since there must be at least 1 multiple of 2 there, it is divisible by 6) and this argument can be extended to arbitrary consecutive terms to get divisibility by a factorial. But what I can't figure out is how to show that the remaining integer has a factor of $(N+1)$, which seems to be the case when I look at some very small values of these binomial coefficients. Of course I know that verification even up to 1,000,000 values is not a sufficient proof, but if feels correct when I do the calculation.

$\endgroup$
3
$\begingroup$

$n=4, k=3, N=2$ gives $\binom{nN}{kN} = \binom{8}{6} = 28$ is not a multiple of 3.


However, there's a sense in which you're not too far off a theorem. A 2010 arXiv paper by Zhi-Wen Sun (1005.1054) claims to prove (I haven't verified the proof) that $$(ln+1)\mid k\binom{kn+ln}{kn}$$ so setting $l=1$ we get $$(n+1)\mid k\binom{(k+1)n}{kn}$$ and we can expand $$\binom{nN}{kN} = \frac{(nN)^\underline{(n-k-1)N}}{((n-k)N)^\underline{(n-k-1)N}}\binom{(k+1)N}{kN}$$ so that counterexamples require $$k \not\mid \frac{(nN)^\underline{(n-k-1)N}}{((n-k)N)^\underline{(n-k-1)N}}$$

Or to put it another way, the variant $$(N+1) \mid k\binom{nN}{kN}$$ follows from Sun's theorem.

$\endgroup$
  • $\begingroup$ Note: Sun's theorem follows from the straightforward computation $k\dbinom{kn+ln}{kn}/\left(ln+1\right) = k\dbinom{kn+ln}{kn} - l\dbinom{kn+ln}{kn-1}$. $\endgroup$ – darij grinberg Aug 11 '18 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.