Maths Olympiad Prep

Track / Stage 4 / 127 of 340 #867 of 2444

Problem 867

AMC 12 late, AIME early
Combinatorics Difficulty 4.7 Prove it Saudi Arabian Mathematical Competitions · Saudi Arabia · 2012

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

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Note that
∑n=010062012!(n!(1006−n)!)2=2012!(1006!)2∑n=01006(1006!n!(1006−n)!)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)=(10061006−n)\binom{1006}{n} = \binom{1006}{1006-n}, we have
∑n=01006((1006n))2=∑n=01006(1006n)(10061006−n)=(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!(1006−n)!)2=((20121006))2 \sum_{n=0}^{1006} \frac{2012!}{(n!(1006-n)!)^2} = \left(\binom{2012}{1006}\right)^2
which is a perfect square.

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