Maths Olympiad Prep

Library / /17 of 22

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:
Find a formula for the sum of the squares of the numbers in the nnth row of Pascal's triangle (i.e. the numbers (n0),(n1),,(nn)\left(\begin{array}{l}n \\ 0\end{array}\right),\left(\begin{array}{l}n \\ 1\end{array}\right), \ldots,\left(\begin{array}{l}n \\ n\end{array}\right) ).

Solution

Solution:
We claim that the sum of the squares of the numbers in row nn is
(n0)2+(n1)2++(nn)2=(2nn) \left(\begin{array}{l} n \\ 0 \end{array}\right)^2+\left(\begin{array}{c} n \\ 1 \end{array}\right)^2+\cdots+\left(\begin{array}{l} n \\ n \end{array}\right)^2=\left(\begin{array}{c} 2 n \\ n \end{array}\right)
the middle number in row 2n2 n of Pascal's triangle. To prove this, we can think of the right side as the number of ways to form a committee of nn people chosen from some 2n2 n people. For the left side, suppose the 2n2 n people are nn men and nn women. If there are kk women on the committee, then there must be nkn-k men, so there are (nk)\left(\begin{array}{l}n \\ k\end{array}\right) ways to choose the women and (nnk)\left(\begin{array}{c}n \\ n-k\end{array}\right) ways to choose the men, giving (nk)(nnk)=(nk)2\left(\begin{array}{c}n \\ k\end{array}\right)\left(\begin{array}{c}n \\ n-k\end{array}\right)=\left(\begin{array}{l}n \\ k\end{array}\right)^2 possible committees with kk women. Adding over the possible values of kk from 0 to nn gives the sum on the left. Since each side counts the same thing in a different way, the two sides must be equal.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.