Prove $1+2+2^2+\dots+2^{n-1}=2^n-1$

Question

Prove the following equation by counting the non-empty subsets of $\{1,2,\ldots,n\}$ in $2$ different ways:

$1+2+2^2+2^3\ldots+2^{n-1}=2^n-1$.

Let $A=\{1,2\ldots,n\}$. I know from theory that it has $2^n-1$ non-empty subsets, which is the right-hand side of the equation but, how do count the left one?

I've proven it using induction but how can i get to the first part of the equation by counting subsets differently?

Answer 1

For the LHS we need to sum

• $n$ subset with $1$ elements
• $\binom{n}{2}$ subset with 2 elements
• $\binom{n}{3}$ subset with 3 elements
• etc.

that is by binomial theorem $\sum_{k=0}^{n} \binom{n}{k}a^kb^{n-k}=(a+b)^n$

$$\sum_{k=1}^{n} \binom{n}{k} =\sum_{k=0}^{n} \binom{n}{k} -\binom{n}{0}=(1+1)^n-1=2^n-1$$

By direct check note that

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

Note that

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

Answer 2

The right-hand side counts non-empty subsets of the set $\{1, 2, 3, \ldots, n\}$.

The left-hand side counts non-empty subsets of the set $\{1, 2, 3, \ldots, n\}$ whose largest element is $k$, $1 \leq k \leq n$. The number of such subsets is $2^{k - 1}$ since such a subset is determined by choosing which of the $k - 1$ elements smaller than $k$ are in the subset.