# Further explanation for steps of an equation that proofs that $\sum^{n}_{k=0}k\cdot \binom{n}{k}=n\cdot2^{n-1}$

So, this is one of the questions in my textbook, which seems to be quite common: $$\sum^{n}_{k=0}k\cdot \binom{n}{k}=n\cdot2^{n-1}$$

The same book provides the following solution: $$\sum_{k=0}^{n}k\cdot \binom{n}{k}= \sum^{n}_{k=0}n\cdot\binom{n-1}{k-1}=n\sum^{n-1}_{k=0}\binom{n-1}{k}=n\cdot2^{n-1}$$

What is unclear to me, is (1) how I get from $$\sum^{n}_{k=0}n\cdot\binom{n-1}{k-1}$$ to$$n\sum^{n-1}_{k=0}\binom{n-1}{k}$$ and (2) from $$n\sum^{n-1}_{k=0}\binom{n-1}{k}$$ to $$n\cdot2^{n-1}$$ respectively.

## 2 Answers

(1) We have $$\sum_{k=0}^nn\cdot{n-1\choose k-1}=n\sum_{k=0}^{n-1}{n-1\choose k}$$ by a substitution $$k'=k-1$$. We can obviously place the $$n$$ at the front, and we then use $${n-1\choose-1}=0$$, so $$k=0$$ can be ignored.

(2) Here we just use the formula $$\sum_{k=0}^n{n\choose k}=2^n$$. There is a very nice combinatorial proof of this. The term $${n\choose k}$$ represents the amount of ways to pick $$k$$ items out of $$n$$. If we sum over all $$0\leq k\leq n$$, we just look at the total amount of ways to pick any set out of $$n$$ items. There are $$2^n$$ ways, since we can choose for each item whether we pick it or not.

There is also a very nice combinatorial proof of the statement you want to prove in the first place. The term $$k\cdot{n\choose k}$$ can be thought of the amount of ways to pick $$k$$ items out of $$n$$ and then choosing one of the $$k$$ items as your favorite. Summing over $$0\leq k\leq n$$, we just look at the total amount of ways to pick any set out of $$n$$ items, and then choosing one of the picked items as your favorite. We can also reverse this: First choose your favorite item, and then pick any set of remaining items out of the $$n-1$$ left over items. This results in $$n\cdot2^{n-1}$$ possibilities.

The second part is very simple. As the $$\sum^{n-1}_{k=0}\binom{n-1}{k}$$ is the size of power set of a set with size of $$n-1$$. Hence, it is equal to $$2^{n-1}$$.

Hint: For the first part, there is a mistake in the range of $$\sum$$. If it would be true, you can show it using a simple change variable ($$u = k - 1$$ and change the range of sigma from ($$1$$ to $$n$$) to ($$0$$ to $$n-1$$)).