Counting arguments question about sums of binomial coefficients

Question

Use counting arguments to prove these identities: I don't know how to type this: it is two numbers in brackets the first on top of the other, but there is no fraction line. Here is an image of both of the identities.

$${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n$$ $$ {n \choose 1} + 2 {n \choose 2} + 3 {n \choose 3} + \cdots + n{n\choose n} = n 2^{n-1}$$

Answer 1

(as per my comment): $\binom{m}{n}$ has the meaning that it is the number of unique groups of $m$ you can choose from $n$ distinct items. If you sum up all possible groups then you get the total sum of the different ways you can choose items from the group of $n$. If you place each item side-by-side, you can mark it with a $0$ or a $1$ meaning it is selected or it isn't. There are $2^n$ possible ways to assign $0$'s and $1$'s and thus $2^n$ possible ways of picking items. The sum of all of the different groups should add to this total.

For the second equation, it might help to understand it as a weighted sum (part of an average). The sum:

$$ \sum_0^n k\binom{n}{k} $$

Makes up part of the computation for the expected size of a group if you randomly select items from the total. This expected value is half of the size of the total. Thus:

$$ \frac{\sum_0^n k\binom{n}{k}}{\sum_0^n \binom{n}{k}} = \frac{n}{2} $$

With the result that $\sum_0^n\binom{n}{k} = 2^n$, this gives:

$$ \sum_0^n k\binom{n}{k} = \frac{n}{2}2^n = n2^{n - 1} $$

Answer 2

The first equation can be interpreted combinatorically as: The number of subsets of a set with $n$ elements (i.e. $2^n$) is equal to the sum of the numbers of $k$-element subsets of the set (i.e. $\binom{n}{k}$). This statement is somewhat trivial: If you count all subsets of size $k$ and do this for every $k\in\{0,\dots,n\}$, then you are counting all subsets (each exactly once). If you want a more technical proof, apply the binomial theorem which gives us

$$2^n = (1+1)^n = \sum_{k=0}^{n}\binom{n}{k}1^n1^{k-n} = \sum_{k=0}^{n}\binom{n}{k}.$$

For the second equation, we may use the binomial theorem again:

$$n2^{n-1} = n(1+1)^{n-1} = n\sum_{k=0}^{n-1}\binom{n-1}{k}1^{n-1}1^{k-n+1} = \sum_{k=0}^{n-1}n\binom{n-1}{k} = \sum_{k=0}^{n-1}(n-k)\binom{n}{k} = \sum_{k=0}^{n-1}(n-k)\binom{n}{n-k} = \sum_{k=1}^{n}k\binom{n}{k}.$$

Note that we have used $n\binom{n-1}{k} = n\frac{(n-1)!}{k!(n-k-1)!} = \frac{n!}{(n-k-1)!k!} = (n-k)\frac{n!}{(n-k)!k!} = (n-k)\binom{n}{k}$, as well as $\binom{n}{k}=\binom{n}{n-k}$. The last step of the equation follows from turning around the order of summation.