# 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.

• This question has already been changed two or three times and it isn't clear what is the correct one. Commented Feb 8, 2016 at 8:00
• Summation is from k=1 to n-1 and on the right hand side it is up to 2^(n-1)
– max
Commented Feb 8, 2016 at 8:02
• Exactly as I made it the first time I corrected it. Commented Feb 8, 2016 at 8:03
• Both sides are equal to $2^n - 2$. The LHS because the sum represents the number of subsets of a set $A$ with cardinality $n$, except for the whole set $A$ and the empty set. The RHS is $2^n - 2$ for algebraic reasons, though a combinatorial argument is probably possible. Commented Feb 8, 2016 at 8:04

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.

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$$

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.

• This is a mathematical proof. I am asking about the combinatorial proof.
– max
Commented Feb 8, 2016 at 8:05
• Combinatorial proofs are, in particular, mathematical. I would describe the proof here as algebraic (and therefore it doesn't fit to the question). Commented Feb 8, 2016 at 9:46

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$ .