Calculate:

1. $\sum_{k=0}^{n}\binom{n}{k}$
2. $\sum_{k=0}^{n} k\binom{n}{k}$
Idea: double counting and index change.

1. $\sum_{k=0}^{n}\binom{n}{k}$ corresponds to the number of possible choices of any number of elements from $n$ elements and thus equals $2^{n}$. This can also be proven by induction using the property $\binom{n}{p}=\binom{n-1}{p-1}+\binom{n-1}{p}$, or with the binomial theorem for $(1+1)^{n}$.
2. Let's consider what $\sum_{k=0}^{n} k\binom{n}{k}$ means. We choose a number $k$ between 0 and $n$. We choose $k$ elements from the $n$ elements, and then we choose 1 element from the $k$ chosen elements. However, we could just as well choose 1 element from the $n$ elements and $k-1$ elements from the remaining $n-1$ elements. Therefore, by setting $\binom{n}{-1}=0$:

$$
\begin{aligned}
\sum_{k=0}^{n} k\binom{n}{k} & =\sum_{k=0}^{n} n\binom{n-1}{k-1} \\
& =n \sum_{k=0}^{n-1}\binom{n-1}{k} \\
& =n 2^{n-1}
\end{aligned}
$$

We can also derive this result using the binomial theorem by studying the derivative of $(1+x)^{n}$ at 1.