Q. 1.12 - A First Course in Probability

Question

Consider the following combinatorial identity:

$\sum _{k=1}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)=n·2^{n-1}$

(a) Present a combinatorial argument for this identity by considering a set of $n$ people and determining, in two ways,

the number of possible selections of a committee of any size and a chairperson for the committee.

Hint:

(i) How many possible selections are there of a committee of size $k$ and its chairperson?

(ii) How many possible selections are there of a chairperson and the other committee members?

(b) Verify the following identity for $n = 1, 2, 3, 4, 5$:

$\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1)$

For a combinatorial proof of the preceding, consider a set of n people and argue that both sides of the identity represent

the number of different selections of a committee, its chairperson, and its secretary (possibly the same as the chairperson).

Hint:

(i) How many different selections result in the committee containing exactly $k$ people?

(ii) How many different selections are there in which the chairperson and the secretary are the same?

(answer: $n{2}^{n-1}$.)

(iii) How many different selections result in the chairperson and the secretary being different?

(c) Now argue that

$\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^3=2^{n-3}{n}^2(n+3)$

Step-by-Step Solution

Answer

(a) The number of possible selections of a committee of any size and a chairperson for the committee is $\sum _{k=1}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)=n·2^{n-1}$

(b) It is proved that $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1)$

(c) It is proved that $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^3=2^{n-3}{n}^2(n+3)$

Part (a) Step 1. Find the total number of ways for selecting a committee of any size and a chairperson for the committee.

Total number of persons $=n$

No. of persons to be selected for committee $=k$

$k$ persons can be selected out of $n$ in ${}^{n}C_k$ ways $=\left(\begin{array}{c}n\\ k\end{array}\right)$

Out of these $k$ members, $1$ chair person can be selected in ${}^{k}C_1$ ways $=k$

So, the total number of ways for selecting a committee of any size and a chairperson for the committee is $=k\left(\begin{array}{c}n\\ k\end{array}\right)$

Now if we select the chairperson first from the group of $n$ people, then it can be done in ${}^n{C}_1$ ways $=\left(\begin{array}{c}n\\ 1\end{array}\right)\text{ ways}=n \text{ways}$

The remaining $n-1$ persons can be either selected or not selected for the committee.

So, two possible states are there for each person in the group of $\left(n-1\right)$ persons. So, it can be done in $2^{n-1}$ ways.

Therefore, the total no. of ways is $n·2^{n-1}$ ways.

So, $\sum _{k=1}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)=n·2^{n-1}$.

Part (b) Step 1. Verify the given identity.

The given identity is $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1)$

For $n=1, k=1$

$$\begin{gathered} \sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1) \\ \Rightarrow \left(\begin{array}{c}1\\ 1\end{array}\right)1^2=2^{1-2}\times 1(1+1) \\ \Rightarrow 1\times 1=\frac{1}{2}\times 2 \\ \Rightarrow 1=1 \end{gathered}$$

For $n=2, k=1,2$

$$\begin{gathered} \sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1) \\ \Rightarrow \left(\begin{array}{c}2\\ 1\end{array}\right)1^2+\left(\begin{array}{c}2\\ 2\end{array}\right)2^2=2^{2-2}\times 2(2+1) \\ \Rightarrow 2+4=1\times 6 \\ \Rightarrow 6=6 \end{gathered}$$

For $n=3, k=1,2,3$

$$\begin{gathered} \sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1) \\ \Rightarrow \left(\begin{array}{c}3\\ 1\end{array}\right)1^2+\left(\begin{array}{c}3\\ 2\end{array}\right)2^2+\left(\begin{array}{c}3\\ 3\end{array}\right)3^2=2^{3-2}\times 3(3+1) \\ \Rightarrow 3+12+9=2\times 3\times 4 \\ \Rightarrow 24=24 \end{gathered}$$

For $n=4, k=1,2,3,4$

$$\begin{gathered} \sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1) \\ \Rightarrow \left(\begin{array}{c}4\\ 1\end{array}\right)1^2+\left(\begin{array}{c}4\\ 2\end{array}\right)2^2+\left(\begin{array}{c}4\\ 3\end{array}\right)3^2\left(\begin{array}{c}4\\ 4\end{array}\right)4^2=2^{4-2}\times 4(4+1) \\ \Rightarrow 4+24+36+16=4\times 4\times 5 \\ \Rightarrow 80=80 \end{gathered}$$

For $n=5, k=1,2,3,4,5$

$$\begin{gathered} \sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1) \\ \Rightarrow \left(\begin{array}{c}5\\ 1\end{array}\right)1^2+\left(\begin{array}{c}5\\ 2\end{array}\right)2^2+\left(\begin{array}{c}5\\ 3\end{array}\right)3^2+\left(\begin{array}{c}5\\ 4\end{array}\right)4^2+\left(\begin{array}{c}5\\ 5\end{array}\right)5^2=2^{5-2}\times 5(5+1) \\ \Rightarrow 5+40+90+80+25=8\times 5\times 6 \\ \Rightarrow 240=240 \end{gathered}$$

For combinatorial proof, first consider selecting $k$ members from $n$ people and then selecting chairperson and secretary (both of them can be same),.

So, for any $k$, the number of ways in which it can be done is  $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2$............ (3)

If chairperson and secretary are the same person, then number of ways is  $n{2}^{n-1}$ ................ (4)

If they are different then chairperson can be selected in $\left(\begin{array}{c}n\\ 1\end{array}\right)=n \text{ways}$ and then the secretary can be selected in $\left(\begin{array}{c}n-1\\ 1\end{array}\right)=n-1 \text{ways}$

The left $n-2$ members can be selected or not selected in the committee, so number of ways of doing so is  $n\left(n-1\right)2^{n-2}$......... (5)

But (3) = (4) + (5)

$\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=n{2}^{n-1}+n\left(n-1\right)2^{n-2}$

Hence, it is proved that $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1)$

Part (c) Step1. Prove the given equation.

The given equation is $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^3=2^{n-3}{n}^2(n+3)$

Consider the case in which the chairperson, secretary and head are to be selected in the committee. All the three posts can be given to same person or two persons can have these three designations or all the three designations can be given to three different people.

All the three posts can be given to same person in $n{2}^{n-1} \text{ways}$....... (1)

Two persons can have these three designations in ${}^{3}C_2 \text{ways}$  $=3\text{ ways}$

First person can be selected in ${}^{n}C_1=n \text{ways}$

Second person can be selected in ${}^{n-1}C_1=\left(n-1\right) \text{ways}$

and the remaining $(n-2)$ persons can either be selected or not selected that is $2^{n-2} \text{ways}$

So, total number of ways are $3n(n-1)2^{n-1}$............... (2)

All the three designations can be given to three different people in $n(n-1)(n-2)2^{n-3} \text{ways}$ ................. (3)

Selecting k members out of n people and then selecting chairperson, secretary and head (all of them can be same) can be done in $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^3 \text{ways}$ .............. (4)

(4) will be equal to (1) + (2) + (3)

Therefore, it is proved that $\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^3=2^{n-3}{n}^2(n+3)$