CombinatoricsDifficulty 5.3AIME, harderProve itUnited States
Problem: Find a formula for the sum of the squares of the numbers in the nth row of Pascal's triangle (i.e. the numbers (n0),(n1),…,(nn) ).
Solution
Solution: We claim that the sum of the squares of the numbers in row n is (n0)2+(n1)2+⋯+(nn)2=(2nn) the middle number in row 2n of Pascal's triangle. To prove this, we can think of the right side as the number of ways to form a committee of n people chosen from some 2n people. For the left side, suppose the 2n people are n men and n women. If there are k women on the committee, then there must be n−k men, so there are (nk) ways to choose the women and (nn−k) ways to choose the men, giving (nk)(nn−k)=(nk)2 possible committees with k women. Adding over the possible values of k from 0 to n 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.