Kenneth Rosen Edition 7 Exercise 6.4 Question 38 (Page No. 422)

Question

Give a combinatorial proof that if n is a positive integer then $\displaystyle\sum_{k = 0}^{n} k^{2} \binom{n} {k} = 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} + n2^{n−1}.]$

Answer 1

As the question is asking for combinatorial proof.

Let's FIND OUT  the STORY  which relates to it.

 

in the LHS side, for every k we are making a subset of k elements and among those k elements we are two elements not necessarily different ones, they can be done in  k*k ways which are k$^2$.

 

The STORY is:- let's form a committee of k boys from n boys and out of those k boys pick two of them as class leader and school representative( not necessarily different).
 

 

LEFT SIDE:- Let us GO with the cases part.

 

( choose 0 boys and 0 ways two select two boys) + (choose 1 boy and only one way to select two boys ) +...+ ( select n boys and n$^2$ ways to select two boys)

(0 * nC0 ) + (1$^2$ * nC1) + (2$^2$ * nC2) +.…….…..+(n$^2$ * nCn) = ∑ ( k 0 to n )  k$^2$ nCk

 

so the left part of the given one is satisfying the requiment.

Now Lets prove the furthermore statement:-

 

n(n-1)*2^(n-2)  + n*2^(n-1) = n$^2$ * 2^(n^-2) – n* 2^(n-2) + n*2^(n-1)

                                    = n$^2$ * 2^(n^-2)   – n * 2^(n-2) + n * 2^(n-2)  + n * 2^(n-2)   [ 2^n-1 = 2^n-2  + 2^n-2 ]

                                    = n$^2$ * 2^(n^-2) + n * 2^(n-2)

                                    = 2^n-2 [ n$^2$ + n ]

                                      = 2^(n-2)  * n( n+1)

                                      = n( n+1) * 2^(n-2) which is same as RHS.

 

now let's change the rhs part to n(n-1)*2^(n-2)  + n*2^(n-1).

 

Let's verify the RIGHT SIDE PART:-

case 1: let's choose different boys for roles and then generate all the possible sets which include these two boys , that is 2^n-2 subsets are possible.

case 2:- for both roles choose the same boy and generate all the subsets which include this boy that is 2^n-1 subsets.

RHS is nothing but case 2 + case 1

which same are LHS.

so LHS and RHS are equal.

 

THE SAME thing  we can ask in this way also

QUES) let's assume there is set A which has n distinct elements ,

the set C = { ( x, y, R ) | R⊆A , x, y ⋲ R ) and NOTE x,y not necessarily different.

then what is the cardinality of Set C?