Double Counting (Different Perspectives)

Consider each element of $X$

A fixed element belongs to exactly half of all subsets of $X$

Since $X$ has

subsets, each element belongs to

subsets

There are $n$ elements, so the total sum of the sizes of all subsets is

Therefore,

We count the same thing in two ways

If the committee has $k$ students, we can choose it in

ways

Then choose its leader in

ways

So the total number of ways is

Now count another way

Choose the leader first

There are

choices

Each of the other $n-1$ students can either be in the committee or not

So there are

choices

Therefore,

First choose the committee

Then choose the first special member in

ways

Then choose the second special member in

ways

So the total is

Now count another way

Choose the two special students first

There are

ways

Then choose the remaining $k-2$ committee members from the other $n-2$ students

Therefore,

Count the total number of times people participate in handshakes

Counting by people gives

But every handshake involves exactly two people

So counting by handshakes gives

Therefore,