Combinatorial proof for $2^n=1+\sum_{k=0}^{n-1}2^k$

Question

I am looking to find a proof by double counting.

Logically concerning the left hand side I was thinking about the number of all subsets of a n-set.

On the right hand side following the same logic I see that with the same logic this will translate to summing up the number of subsets of all k-sets for k=0 to n-1 and then adding one more set.

This seems a bit counterintuitive as there are a lot of sets that will be counted double.

I looked at the building up of the subsets from k to k+1 and tried finding a recurrence relation.

I noticed that in fact the number of subsets of a n-set is equal to the amount of the subsets in n=0 to n-1 added together plus 1. But I cant see why this is true.

It makes more sense to me that $2^n$ is equal to the sum of all subsets of length $k=0$ to $n-1$ and then adding the set itself so plus 1 and thus having $2^n=1+\sum_{k=0}^{n-1}\binom{n}{k}$.

I am quite sure we could get from those binomial coefficients to the $2^k$ that we want to find. But this would not be a double counting proof anymore.

Maybe I need to look at the problem in another angle?

Answer 1

Let's count the number of subsets of $\{0,1,2,...,n\}$.

On the LHS, it's $2^n$, because each element either is or is not a member of a subset, and making that choice for each element leads to a different subset.

On the RHS, we count the subsets based on their largest element. The empty set is an outlier, so we count that separately. Beyond that, there are $2^0$ subsets whose greatest element is $1$ (just $\{1\}$), $2^1$ subsets whose greatest element is $2$ (both $\{2\}$ and $\{1,2\}$), and generally $2^k$ subsets whose greatest element is $k+1$.

Therefore, $$2^n=1+\sum_{k=0}^{n-1}2^k$$

Answer 2

Hint: count the number of subsets of $\{1,2,...,n\}$. First consider that in your choice for every subset, you can choose whether or not ($2$ choices) to include each of the $n$ elements, which gives you $2^n$. Then consider fixing the size of the subset, say $k$, and for each $k$ see how many subsets you can choose, and then sum up as $k$ runs through $1,2,...,n$.

Answer 3

Let's count all non-empty subsets of $\{1,2,\ldots,n\}$ twice.

We get $2^n - 1$ via the standard argument that we can either include element $i$ in a subset or not (giving is $2^n$ options, by $n$ independent choices) and substracting the empty set from it (the $-1$).

Let (for $k=1,\ldots,n$) the collection $A_k$ be all subsets $A$ of $\{1,2,\ldots,n\}$ with $\max(A) = k$. For different $k$ these sets are disjoint: a non-empty finite set has a unique maximum; it cannot be both $i$ and $j$ where $i \neq j$, and every non-empty set has a maximum in $\{1,\ldots,n\}$ so these form a partition.

And $|A_k|= 2^{k-1}$, because to form a set in $A_k$ we put $k$ (the max) in $A$ and then take any subset of $\{1,\ldots,k-1\}$ (empty for $k=1$, but there are always $2^{k-1}$ subsets of it) and add it to $A$, and all $A \in A_k$ can be made that way, uniquely.

So $$2^n -1 = \sum_{k=1}^n 2^{k-1}= \sum_{k=0}^{n-1}2^k$$

by a reindexing in the last sum. Now pull the 1 to the other side.

Alternatively add the empty set as a singleton in the partition of all subsets of $\{1,\ldots,n\}$ to get the formula directly.

Answer 4

Consider the set of binary sequences that are not the zero sequence $(x_1,\dotsc, x_n)$ of length $n$. There are $2^n-1$ such binary sequences. Now partition this set into sets $A_k$ based on the position $k$ that the first $1$ occurs. Then $|A_k|=2^{n-k}$ for $k=1,\dotsc, n$ from which the result follows.