Combinatorial proof of summation of $\sum_{k = 1}^{n-1} {n \choose k}= 2^1 + 2^2 + 2^3 +\ldots+ 2^{n-1}$ I am looking for a combinatorial proof for it. I know how to prove it mathematically. Expanding $(1+x)^n$ and replacing $x$ with $1$ will give me the result but I am not able to explain it combinatorially.
Note: This is not a homework question. I am just curious.
 A: As usual $[n]=\{1,\ldots,n\}$. $\sum_{k=1}^{n-1}\binom{n}k$ is clearly the number of non-empty, proper subsets of $[n]$, since $\binom{n}k$ is the number of subsets of size $k$. Now let $A_k$ be the number of subsets of $[n]$ with maximum element $k$; clearly $|A_k|=2^{k-1}$, since the rest of $A_k$ can be any subset of $[k-1]$. Thus, 
$$\left|\bigcup_{k=1}^nA_k\right|=\sum_{k=1}^n2^{k-1}=1+\sum_{k=1}^{n-1}2^k\;.\tag{1}$$
On the other hand, $\bigcup_{k=1}^nA_k$ is clearly the set of non-empty subsets of $[n]$, so $(1)$ counts all of the non-empty, proper subsets of $[n]$ plus the set $[n]$ itself. Subtracting $1$ for the set $[n]$ leaves the desired result: both $\sum_{k=1}^{n-1}\binom{n}k$ and $\sum_{k=1}^{n-1}2^k$ count the non-empty, proper subsets of $[n]$, and they must therefore be equal.
A: Consider the set of $n$ bits integers.
One one side, group them by the number of ones. The sizes of the groups are $\dbinom nm$.
$$0000\|0001\ 0010\ 0100\ 1000\|0011\ 0101\ 1001\ 1100\ 1010\ 1100\|1110\ 1101\ 1011\ 0111\|1111$$
On the other side, group them by prefix made of $n-m-1$ zeroes followed by a single one (except for the first group). The sizes of the groups are $1$ and $2^m$.
$$\color{blue}{0000}\|\color{green}{0001}\| 
\color{green}{001}0\ \color{green}{001}1\|
\color{green}{01}00\ \color{green}{01}01\ \color{green}{01}10\ \color{green}{01}11\|
\color{green}{1}000\ \color{green}{1}001\ \color{green}{1}010\ \color{green}{1}011\ 
\color{green}{1}100\ \color{green}{1}101\ \color{green}{1}110\ \color{green}{1}111$$
A: First on the right side observe that $2^1+\dots+2^{n-1}=2^n-2$. 
Now, on the left side you are expanding $(1+1)^n$ and removing the first and last terms namely ${n\choose 0}$ and ${n\choose n}$. Both of these terms are equal to $1$ which makes the left side $2^n-2$ which is equal to the right side.
A: A variation of Brian M. Scott's answer. 
You are given a set A of n elements. Now we interested in all possible subsets of it and in the total number of subsets.  
First observe: An arbitrary element $ x \in A $ either is in a subset or is not in one. (Law of the excluded middle) and thus gives in total $2^n$ possible subsets. 
But this also has to be the same as: $\sum\limits_{i=0}^n A_i$ with $A_i $ denoting the number of sets with exactly $i$ elements, which is of course: $A_i = \binom{n}{i}$, which gives you the desired equality $\sum\limits_{i=0}^n \binom{n}{i}= 2^n $ . 
