Problem
COM-B1-M04-P022 Square of Subset Size
#22
★★★★☆ Level 4 of 5
Prove combinatorially that \(\sum_{k=0}^n k^2C(n,k)=n(n+1)2^{n-2}\).
Count triples \((S,x,y)\), where \(x,y\in S\), and \(x,y\) may be equal.
By size \(S=k\), there are \(k^2\) ways to choose the ordered pair \((x,y)\), giving the left side. Count by \((x,y)\). If \(x=y\), choose this element in \(n\) ways and choose the rest of \(S\) freely: \(2^{n-1}\). If \(x e y\), choose the ordered pair in \(n(n-1)\) ways and the remaining \(n-2\) elements freely: \(2^{n-2}\). Total: \(n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}\).
Strong identity problem for the first level.