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

Both sides count the number of games in a single-elimination tournament with $2^n$ teams. The left side counts the number of games by round, and the right side is obtained by noting that all teams but the winner lose one game each.

How many strings of $0$s and $1$s of length $n$ are there which have at least one $1$?

• There are $2^n$ strings total, except we want to omit the string of all $0$'s, so $2^n-1$.

• Consider the location of the rightmost $1$, at spot $k$, for some $k\in \{1,2,\dots,n\}$. Given the rightmost $1$ is at spot $k$, the first $k-1$ spaces can be chosen in $2^{k-1}$ ways, while the rest of the string is then forced (since there are only $0$'s to the right of the rightmost $1$). Summing over $k$, the number of strings is $\sum_{k=1}^n2^{k-1}=\sum_{k=0}^{n-1}2^{k}$.

Equating the two answers, you get $2^n-1=\sum_{k=0}^{n-1}2^k$.

Don't get too caught up with trying to come up with a "story" involving pizza or children or candy or committees; this can obscure the simplicity of the solution.