Problem
Prove that for any positive integer k,
(k2)!⋅j=0∏k−1(j+k)!j!
is an integer.
Solution
We show the exponent of any given prime p is nonnegative in the expression. Recall that the exponent of p in n! is equal to ∑i≥1⌊n/pi⌋. In light of this, it suffices to show that for any prime power q, we have
⌊qk2⌋+j=0∑k−1⌊qj⌋≥j=0∑k−1⌊qj+k⌋
Since both sides are integers, we show
⌊qk2⌋+j=0∑k−1⌊qj⌋>−1+j=0∑k−1⌊qj+k⌋.
If we denote by x the fractional part of x, then ⌊x⌋=x− {x} so it's equivalent to
{qk2}+j=0∑k−1{qj}<1+j=0∑k−1{qj+k}.
However, the sum of remainders when 0,1,…,k−1 are taken modulo q is easily seen to be less than the sum of remainders when k,k+1,…,2k−1 are taken modulo q.
So
j=0∑k−1{qj}≤j=0∑k−1{qj+k}
follows, and we are done upon noting {k2/q} <1.
The problems on this page are the property of the MAA's American Mathematics Competitions