Intuitive (combinatorial) proof of $2^n=\sum_{k=0}^n {n\choose k}$ 
Why should we expect that $$2^n=\sum_{k=0}^n {n\choose k}$$

It is easily seen to be true, by the binomial theorem:  just set $x=y=1$ in $(x+y)^n$.
But what is an intuitive reason why it is true (in terms of subsets)?
 A: Note that


*

*$2^n$ is the overall number of subset you can obtain from n elements

*$\binom{n}{k}$ in the number of subset of $k$ objects you can obtain from $n$ elements, thus summing up for all $k$ you obtain $2^n$

A: In terms of subsets, this is just a way of saying the every set with $n$ elements has $2^n$ subsets.
A: A set of size $n$ has $\binom{n}{k}$ subsets of size $k$, and $2^n$ subsets in total. Since all subsets have size between $0$ and $n$, inclusive, it makes sense that we should have
$$2^n = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n}$$
This intuition can be put on a more formal basis by using a proof technique called bijective proof or double counting.
A: Another answer is to look at the rows of Pascal's triangle and note that the sum of each row is twice the sum of the last row.
A: The total number of subsets of $\{1,2,\dots,n\}$ is $2^n$, since we may build any subset by deciding whether or not to include each element (so we make $1$ of $2$ choices, $n$ times).
Among these subsets are $\binom n0$ subsets of size $0$, $\binom n1$ subsets of size $1$, and so forth.
A: A proof by Induction. 
Let $f(n)$ be the number of subsets of an $n$ element set. This is the RHS of the required identity. We claim that $f(n)=2^n$. 
The only subset of the empty set is the empty set whence $f(0)=1$ and the base case is done. Now suppose that the claim holds for all non-negative integers at most $n$. Let $[n+1]=\{1,\dotsc, n+1\}$ be an $n+1$ element subset. A subset $C$ of $[n+1]$ will either contain $n+1$ or not. If $C$ does not contain $n+1$, there are $f(n)$ choices for $C$. If $C$ contains $n+1$, then $C=\{n+1\}\cup B$ where $B\subset \{1,\dotsc, n\}$. In this case there are also $f(n)$ choices for $C$. Hence
$$
f(n+1)=2f(n)=2\times 2^n=2^{n+1}
$$
by the induction hypothesis as desired.
A: Here is another (sort of inductive) way:
Let  $[n]=\{1, 2, ..., n\}$. Split the set of subsets of $[n]$ into two sets:  the set of subsets that contain $n$ and the set of subsets that do not contain $n$. 
The subsets of $\{1, 2, ..., n\}$ not containing $n$ are exactly the subsets of $[n-1]=\{1, 2, ..., n-1\}$. 
The subsets of $\{1, 2, ..., n\}$ that contain $n$ are also in one-to-one correspondence with the subsets of $\{1, 2, ... , n-1\}$, since each of them can be formed by adding $n$ to a subset of $\{1, 2, ... , n-1\}$. *
So \begin{align}\text{# of subsets of [n]}&=\underbrace{\text{# of subsets of $[n]$ containing $n$}}_{=\text{# of subsets of [n-1]}}+\underbrace{\text{# of subsets of $[n]$ not containing $n$}}_{=\text{# of subsets of [n-1]}}\\
&=2({\text{# of subsets of [n-1]}}).
\end{align}
Now note that you have $1$ subset of the empty set $\{\}$, and hence you have $2 \times 1$ subsets of $\{1\}$, $2 \times (2 \times 1)$ subsets of $\{1, 2\}$, etc.
Edit: Another (maybe less intuitive) way to get the recurrence, using Pascal's identity. 
\begin{align}\sum_{k=0}^n \binom{n}{k}&={\sum_{k=0}^n}\big({\binom{n-1}{k}}+{\binom{n-1}{k-1}}\big)\\&={\sum_{k=0}^n} {\binom{n-1}{k}}+{\sum_{k=0}^n}{\binom{n-1}{k-1}}\\&={\sum_{k=0}^{n-1}}{\binom{n-1}{k}}+{\sum_{k=1}^{n}}{\binom{n-1}{k-1}}\text{ (here, we have discarded the 0 summands)}\\
&={\sum_{k=0}^{n-1}\binom{n-1}{k}}+{\sum_{k=0}^{n-1}}{\binom{n-1}{k}} \text{ (the second sum is reindexed)}
\end{align}
A: Since my favorite answer (counting subsets) has already been given,   i will try an inductive proof...
The following is known as Pascal's Formula: 
$${n\choose k}={n-1 \choose k}+{n-1\choose k-1}$$
It's easy to see this by counting subsets...
For $n=0$: $2^0=1={0 \choose 0}$.
Assume true for n.
n+1:  LHS $$=2^{n+1}$$
RHS $$=\sum_{k=0}^{n+1}{n+1\choose k}=\sum_{k=0}^{n+1} ({n\choose k}+{n\choose k-1})=\sum_{k=0}^{n}{n\choose k}+\sum_{k=1}^{n+1}{n\choose k-1}=2^n+2^n=2^{n+1}$$
I have taken out $n\choose-1$ and $n\choose n+1$ which are usually set to $0$...
