How to prove with double counting technique that $1+2+\dots+2^n=2^{n+1} -1$?

Question

How to prove with double counting technique that $1+2+\dots+2^n=2^{n+1} -1$?

I can see, for example, that the right-hand side of the equation counts the cardinality of the powerset of a set with n+1 elements (excluding the empty set): could this be a good idea? Because I don't seem to be able to make the left-hand side fit this idea...

Answer 1

If you want the right-hand side to be the number of nonempty subsets of $\{1,\ldots,n+1\}$, then you can think of each $2^k$ on the left-hand side as the number of subsets of $\{1,\ldots,n+1\}$ whose largest element is $k+1$.

Answer 2

Another way to prove this would be to do so purely algebraically. As polynomials,

$$(x-1)(1+x+\dots+x^n) = x^{n+1} - 1.$$

You can see this by distributing the $(1+x+\dots+x^n)$ on the left-hand side, and noting the massive cancellation that results. Now just plug in $2$ for $x$.

Answer 3

One can choose a bitstring of length $n+1$ in $2^{n+1}$ ways. Excluding the bitstring $0\cdots 0$, this gives $2^{n+1}-1$ bitstrings. One can partition this bitstrings into those that have nonzero $k$-th entry and zero entries to the right of this. There are $2^{k-1}$ choices of this for $k=1,\ldots,n+1$; and this gives the desired formula.