Question

Give a combinatorial proof that if n is a positive integer then\(\sum\limits_{k = 0}^n {{k^2}\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)} = n(n + 1){2^{n - 2}}\). (Hint: Show that both sides count the ways to select a subset of a set of n elements together with two not necessarily distinct elements from this subset. Furthermore, express the right-hand side as \(n(n + 1){2^{n - 2}} + n{2^{n - 1}}\).)

Short answer

\(\sum\limits_{k = 0}^r {{k^2}\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)} = n({2^{n - 1}}) + n(n - 1){2^{n - 2}} = n(n + 1){2^{n - 2}}\)

Step-by-step solution

Step 1: Considerations

The number of ways in which we can select a k subset from the set S of n elements is \(\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)\) and for each of these ways we can select two elements of the k-subset with repetition allowed in \({k^2}\) different ways. This can be done for any \(0 \le k \le n\).

Step 2: Further simplification

On the other hand, we can first select the two elements (repition allowed) and then complete the subset. We need to break the method into two separate cases when the two elements are identical and distinct.

For the first case the two elements can be chosen in n ways as both are same, and the rest of the subset can be decided in \({2^{n - 1}}\) ways by the product rule, as each of the other elements have exactly two options:

Either be includes or not in the subset

Next, when the two elements are distinct, they can be decided in \({2^{n - 2}}\) different ways. Thus equating the number of different ways in both the methods one obtains

\(\sum\limits_{k = 0}^r {{k^2}\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)} = n({2^{n - 1}}) + n(n - 1){2^{n - 2}} = n(n + 1){2^{n - 2}}\)

Note : in the second case of the second method, when two distinct elements are chosen, it is not \(\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right)\) because we are not selecting a two element subset of S.