Problem: Prove combinatorically that $ \sum_{k=1}^{n} k^2 = n{n+1 \choose 2} – {n+1 \choose 3 } $.
My thoughts: I rewrote the equation to be proved as $ \sum_{k=1}^{n} k^2 = {n \choose 1 }{n+1 \choose 2} – { n \choose 0 }{n+1 \choose 3 } $
Then I was thinking to myself that $ k^2 $ on the left side could represent the number of length-2 strings over alphabet of size $ k$.
And the right hand side could be interpreted as: Let $ A $ represent the set of $ 2n+1 $ people composed of two sets: $ B $ the set of $ n+1 $ boys and $ C $ the set of $ n $ girls. $ {n \choose 1 }{n+1 \choose 2} $ could be thought as the set of all possible ways to create a commission made from $ 2 $ boys and $ 1 $ girl ( and similarly for $ { n \choose 0 }{n+1 \choose 3 } $ ).
However, thinking of $ A $ as made from sets $ B ,C $ of boys and girls doesn't seem to make sense of the difference in the right side between the binomials. Also, thinking of the left hand side as a way of choosing number of length-2 strings over alphabet of size $ k$ doesn't make me see how the left-side correlates to the right-hand side. Can you please help me on how to prove the equation?
Best Answer
The boy is numbered from $1$ to $n$, the girls from $1$ to $n+1$. We count the number of triples $(leftgirl,boy,rightgirl)$ with $boy$ less than both $girl$s. For example $(2,1,3)$ or $(6,5,6)$.
The boy has a girl's photo in each hand, possibly the same one, and the girls both have a higher number than the boy. Boy $1$ has $n$ choices for each photo, but boy $n$ only has one choice for each photo. That is the sum of $k^2$.
The boy and the left-hand girl can be any pair of numbers, with the girl the higher number. That is $n+1\choose 2$. The right-hand girl can be any number not equal to the boy. That is $n$.
But now remove those with the right-hand girl less than the boy. That is $n+1\choose3$.