I apologise if this has been posted before, but I've been poring over this problem for days now and just can't seem to get it.
I'm looking for a combinatorial proof for:
$2^n - 1 = 2^0 + 2^1 + 2^2 + 2^3 +...+ 2^{n-1}$
Thank you very much for the help!
On
Tools
Binomial Theorem
For $\displaystyle k \in \Bbb{Z_{\geq 0}} ~: ~2^k = (1 + 1)^k = \sum_{r=0}^k \binom{k}{r}$.
Hockey Stick Identity
For $\displaystyle k \in \Bbb{Z_{\geq 0}}, ~r \in \{0,1,\cdots, k\}, ~: ~\sum_{i=r}^k \binom{i}{r} = \binom{k+1}{r+1}$.
Using the Binomial Theorem:
$\displaystyle \sum_{k=0}^{n-1} 2^k = \sum_{k=0}^{n-1} \left[\sum_{r=0}^k \binom{k}{r}\right]$.
The above double summation may be represented by the following two dimensional table, where each inner summation is represented by a specific row.
\begin{array}{l l l l l l } \binom{0}{0} \\ \binom{1}{0} & \binom{1}{1} \\ \binom{2}{0} & \binom{2}{1} & \binom{2}{2} \\ \binom{3}{0} & \binom{3}{1} & \binom{3}{2} & \binom{3}{3} \\ \cdots \\ \binom{n-1}{0} & \binom{n-1}{1} & \binom{n-1}{2} & \binom{n-1}{3} & \cdots \binom{n-1}{n-1}\\ \end{array}
The above table may be alternatively expressed as a double summation, where each inner summation is represented by a specific column.
$\displaystyle \sum_{r=0}^{n-1} \left[\sum_{i=r}^{n-1}\binom{i}{r}\right]$.
Using the Hockey Stick Identity, this equals :
$$\sum_{r=0}^{n-1} \binom{n}{r+1} = \sum_{r=1}^n \binom{n}{r}.\tag1 $$
Re-applying the Binomial Theorem against the RHS of (1) above, it may be re-expressed as
$\displaystyle \left[\sum_{r=0}^n \binom{n}{r}\right] - \binom{n}{0} = 2^n - \binom{n}{0} = 2^n - 1.$
We count the non-empty subsets of $\{1,2,3,\dots,n\}$. There are $2^n-1$ of them.
There are $2^0$ subsets with biggest element $1$, $2^1$ with biggest element $2$, $2^2$ with biggest element $3$, and so on up to $2^{n-1}$ with biggest element $n$. Add up.