1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

(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.

$\endgroup$
0
$\begingroup$

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$)).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.