COMP 2711 Ex 8

1

$$\sum _{k=1}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}$$

We can interpret the identity as the number of ways to form a committee of any non-zero sizes that has 1 chairman, from a group of $n$ people.

In a smaller case, suppose $n=3$, i.e. there are 3 people, the LHS can be interpreted as follows:

1. Choose a committee of size $k=1,2,3$
2. From each of the k-sized committee, choose 1 chairman from $k$ possible choices

And the RHS as follows:

1. Choose 1 chairman from $n=3$ possible choices
2. From the remaining $n-1=2$ people, choose from all the possible subsets, i.e. $2^{n-1}=4$

In general, the LHS can be interpreted as follows:

1. Choose a subset of size $k=1,2,\dots ,n$
2. From each of the k-sized subset, choose 1 element from $k$ possible choices

And the RHS as follows:

1. From $n$ possible choices, choose 1 element
2. From the remaining $n-1$ choices, choose from all the possible subsets, i.e. $2^{n-1}$

We can see that the LHS and RHS are identical, both referring to the number of possible ways to choose a subset of any non-zero sizes and choose 1 specific element inside the subset.