Maths Olympiad Prep

Library / /19 of 120

, 2012

Combinatorics Difficulty 4.7 AIME Prove it Saudi Arabia

Show that
n=010062012!(n!(1006n)!)2 \sum_{n=0}^{1006} \frac{2012!}{(n!(1006-n)!)^2}
is a perfect square.

Solution

Note that
n=010062012!(n!(1006n)!)2=2012!(1006!)2n=01006(1006!n!(1006n)!)2=(2012!1006!)n=01006(1006!n!)2. \sum_{n=0}^{1006} \frac{2012!}{(n!(1006-n)!)^2} = \frac{2012!}{(1006!)^2} \sum_{n=0}^{1006} \left( \frac{1006!}{n!(1006-n)!} \right)^2 = \left( \frac{2012!}{1006!} \right) \sum_{n=0}^{1006} \left( \frac{1006!}{n!} \right)^2.
Since (1006n)=(10061006n)\binom{1006}{n} = \binom{1006}{1006-n}, we have
n=01006((1006n))2=n=01006(1006n)(10061006n)=(20121006), \sum_{n=0}^{1006} \left(\binom{1006}{n}\right)^2 = \sum_{n=0}^{1006} \binom{1006}{n} \binom{1006}{1006-n} = \binom{2012}{1006},
by the Vandermonde identity. Therefore,
n=010062012!(n!(1006n)!)2=((20121006))2 \sum_{n=0}^{1006} \frac{2012!}{(n!(1006-n)!)^2} = \left(\binom{2012}{1006}\right)^2
which is a perfect square.

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.