Story proof for $\sum_{k=0}^n {n \choose k} = 2^n$ I found a solution online that uses the Binomial Theorem. Is it possible to prove this without using that theorem? 
 A: Consider choosing a subset of a set of length $n$. One way is to determine for every item if it will make it or not, giving $2^n$ ways.
The other, choose the size first.
A: This may depend on what definitions you're using.  If $\dbinom n k$ is defined as the number of size-$k$ subsets of a size-$n$ set, and if you know that $2^n$ is the total number of subsets of a size-$n$ set, then the identity just says for every possible size of subsets, if you add up the number of subsets of that size, you get the total number of subsets.
A: Using the generation rule from Pascal's triangle:
\begin{align}
S_n 
&= \sum_{k=0}^n \binom{n}{k} \\
&= 2 + \sum_{k=1}^{n-1} \binom{n}{k} \\
&= 2 + \sum_{k=1}^{n-1} \left( \binom{n-1}{k-1} + \binom{n-1}{k} \right) \\
&= 2 + \sum_{k=0}^{n-2} \binom{n-1}{k} + \sum_{k=1}^{n-1} \binom{n-1}{k} \\
&= \sum_{k=0}^{n-1} \binom{n-1}{k} + \sum_{k=0}^{n-1} \binom{n-1}{k} \\
&= 2 S_{n-1}
\end{align}
Further $S_0 = 1$. 
This is a homogeneous linear recurrence relation with constant coefficients:
\begin{align}
S_0 &= 1 \\
S_n &= 2 S_{n-1}
\end{align}
It has the characteristic polynomial
$$
p(t) = t - 2
$$
with root $t = 2$ and general solution
$$
S_n = k \, 2^n
$$
The initial condition gives $k = 1$. This results in
$$
S_n = 2^n
$$
A: HINT: 

In how many ways can you choose $k$ things from $n$ things where $0
 \le k \le n$ ?

The L.H.S. will come out to be obvious from this argument while for the R.H.S., we have the argument: For each of the $n$ things, you have $2$ choices; you select it or you don't.
A: Without words:
$$\begin{matrix}&1&+&4&+&6&+&4&+&1&+\\
&&&1&+&4&+&6&+&4&+&1\\
=&1&+&5&+&10&+&10&+&5&+&1\\
\end{matrix}$$
$$16+16=32$$

$$0000\\
1000,0100,0010,0001\\
1100,1010,1001,0110,0101,0011\\
1110,1101,1011,0111\\
1111$$
$$0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111$$
