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

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?

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

• Thanks for this clear solution, this makes sense. – Piri Sep 30 '19 at 22:22

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

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.

• Thanks for this solution, its the same as the one from Matthew Daly just a bit more formal. – Piri Sep 30 '19 at 22:24
• @Piri You're welcome. I've always had to write combinatorial proofs this way (partitioning formally etc.). It's good training. – Henno Brandsma Sep 30 '19 at 22:30

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.