Maths Olympiad Prep

Library / South-Afrika /20 of 64

South-Afrika, 2011

Combinatorics Difficulty 4.7 AIME Prove it South Africa

Show that for every natural number nn the product
(4−21)(4−22)(4−23)…(4−2n) \left(4 - \frac{2}{1}\right) \left(4 - \frac{2}{2}\right) \left(4 - \frac{2}{3}\right) \dots \left(4 - \frac{2}{n}\right)
is an integer.

Solution

(4−21)(4−22)…(4−2n)=∏k=1n(4k−2k)=∏k=1n2(2k−1k)=∏k=1n(2k−1k⋅2kk)=(2n)!(n!)2=(2nn), \begin{align*} \left(4 - \frac{2}{1}\right) \left(4 - \frac{2}{2}\right) \dots \left(4 - \frac{2}{n}\right) &= \prod_{k=1}^{n} \left(\frac{4k-2}{k}\right) \\ &= \prod_{k=1}^{n} 2 \left(\frac{2k-1}{k}\right) \\ &= \prod_{k=1}^{n} \left(\frac{2k-1}{k} \cdot \frac{2k}{k}\right) \\ &= \frac{(2n)!}{(n!)^2} = \binom{2n}{n}, \end{align*}
which is an integer for each nn.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.