4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This question has already been changed two or three times and it isn't clear what is the correct one. $\endgroup$
    – DonAntonio
    Feb 8, 2016 at 8:00
  • $\begingroup$ Summation is from k=1 to n-1 and on the right hand side it is up to 2^(n-1) $\endgroup$
    – max
    Feb 8, 2016 at 8:02
  • $\begingroup$ Exactly as I made it the first time I corrected it. $\endgroup$ Feb 8, 2016 at 8:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – David
    Feb 8, 2016 at 8:04

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .