Intuitive (combinatorial) proof of $2^n=\sum_{k=0}^n {n\choose k}$

Question

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)?

Answer 1

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.

Answer 2

In terms of subsets, this is just a way of saying the every set with $n$ elements has $2^n$ subsets.

Answer 3

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$

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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}

Answer 8

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