Maths Olympiad Prep

Library / /13 of 13

Number theory Difficulty 7.1 National olympiad, round 2 Prove it South Africa

Let kk and mm be integers with 1<k<m1 < k < m. For a positive integer ii, let LiL_i be the least common multiple of 1,2,,i1, 2, \dots, i. Prove that kk is a divisor of Li[(mi)(mki)]L_i \cdot \left[\binom{m}{i} - \binom{m-k}{i}\right] for all i1i \ge 1. [Here, (ni)=n!i!(ni)!\binom{n}{i} = \frac{n!}{i!(n-i)!} denotes a binomial coefficient. Note that (ni)=0\binom{n}{i} = 0 if n<in < i.]

Solution

We prove the statement by induction on mm. When m=km = k, we have
Li[(ki)(0i)]=Li(ki)=Lik!i!(ki)!=kLii(k1)!(i1)!(ki)!=kLii(k1i1). L_i \left[ \binom{k}{i} - \binom{0}{i} \right] = L_i \binom{k}{i} = L_i \cdot \frac{k!}{i!(k-i)!} = k \cdot \frac{L_i}{i} \cdot \frac{(k-1)!}{(i-1)!(k-i)!} = k \cdot \frac{L_i}{i} \cdot \binom{k-1}{i-1}.
Since Lii\frac{L_i}{i} is an integer (by definition of LiL_i), and (k1i1)\binom{k-1}{i-1} is a binomial coefficient and thus also an integer, we see that kk is indeed a divisor.

For the induction step, assume that the statement holds for a specific value of mm. We use the recursion (m+1i)=(mi)+(mi1)\binom{m+1}{i} = \binom{m}{i} + \binom{m}{i-1} to show that it holds for m+1m+1 as well:
Li[(m+1i)(m+1ki)]=Li[(mi)(mki)]+Li[(mi1)(mki1)]=Li[(mi)(mki)]+LiLi1Li1[(mi1)(mki1)]. \begin{aligned} L_i \left[ \binom{m+1}{i} - \binom{m+1-k}{i} \right] &= L_i \left[ \binom{m}{i} - \binom{m-k}{i} \right] + L_i \left[ \binom{m}{i-1} - \binom{m-k}{i-1} \right] \\ &= L_i \left[ \binom{m}{i} - \binom{m-k}{i} \right] + \frac{L_i}{L_{i-1}} \cdot L_{i-1} \left[ \binom{m}{i-1} - \binom{m-k}{i-1} \right]. \end{aligned}
Note that kk divides both Li[(mi)(mki)]L_i[\binom{m}{i} - \binom{m-k}{i}] and Li1[(mi1)(mki1)]L_{i-1}[\binom{m}{i-1} - \binom{m-k}{i-1}] by the induction hypothesis (if i=1i=1, the latter term is simply zero), and Li1L_{i-1} (the least common multiple of 1,2,,i11, 2, \dots, i-1) divides LiL_i (the least common multiple of 1,2,,i1, 2, \dots, i, or equivalently the least common multiple of Li1L_{i-1} and ii). It follows that kk is also a divisor of Li[(m+1i)(m+1ki)]L_i[\binom{m+1}{i} - \binom{m+1-k}{i}], which completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.