Vrftsjtryk

I was given this formular, and am now tasked to use double counting to prove it:

$sum_{k=1}^{n} k binom{n}{k} = n cdot 2^{n-1}$

Quite frankly, I have no clue on how to work this out. Of course, you could start out by looking at the numbers this produces:

n     result

1     1

2     4

3     12

4     32

5     80

6     192

7     448

8     1024

9     2304

10    5120

As far as I've understood double counting, there's two ways you can use it.

The first way is to imagine a matrix where you either put a tick into a field, or you leave it empty. Then counting the ticks in the rows and the columns individually must lead to the same result. Unfortunately, I see no way to apply this concept to this particular task.

The second way is to look for an intuitional problem that can be solved by either of the two ways shown in the equation. Again, I fail to come up with anything that makes sense; especially with the fact, that the sum in the left term makes everything even more complicated.

Do you have any ideas on how to solve this problem?

One nice way of counting that is to think of it like this, suppose you want to choose a subset of a population of size $n$, and from this set select a leader. There are basically 2 ways of doing so, you can first choose the set of people and then choose a leader among it, if your subset is of size $k$, there are $k$ ways of choosing the leader and there are ${nchoose k}$ ways of choosing a subset of size $k$. Hence you get $sum_{k=0}^n k {nchoose k}$.

The other-way of choosing that is to select a leader from the population ($n$ ways of doing it) and then choosing the rest of the subset among the rest of the population (there $n-1$ remaining people to choose from), which accounts for $2^{n-1}$ possibilities when you fix the leader.

In conclusion
$$sum_{k=0}^n k {nchoose k}=n 2^{n-1}$$

$sum_{k=0}^{n}kbinom{n}{k}=sum_{k=0}^{n}left(n-kright)binom{n}{k}$
so that $$sum_{k=0}^{n}kbinom{n}{k}=frac{1}{2}left[sum_{k=0}^{n}kbinom{n}{k}+sum_{k=0}^{n}left(n-kright)binom{n}{k}right]=frac{1}{2}nsum_{k=0}^{n}binom{n}{k}=frac{1}{2}n2^{n}=n2^{n-1}$$