counting proof for $\sum_{k=0}^{n-1} 2^{k} = 2^n - 1$ I was hoping someone could help me come up with a combinatorial proof, one with an easy to understand 'story' for $\sum_{k=0}^{n-1} 2^{k} = 2^n - 1$. For instance I understand that $2^n$ is the number of possibilities when creating subsets of size $n$. For example, if you're given a choice of any topping on a pizza, and you can only have said topping once (decide to include or exclude) then you have $2^n$ choices. But I'm not sure how the $-1 $ would be incorporated, or why the LHS would be $1+2+4+8+...+2^{n-1}$
 A: 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.
A: 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.
A: Imagine you are not allowed to have a pizza with no toppings.
Then if you have $m$ possible toppings you are allowed to have $2^m -1$ toppings. (For any type of topping you can or can not include it.  That is $2^m$ choices. But that includes excluding every topping and having a pizza with no toppings.  That's not allowed so you are allowed $2^m -1$ types of pizzas.)
Now what if you choice was $0$ toppings how many pizzas can you have?  Well, zero.
And if you had one topping how many?  Well, $1$.
Okay, now let's say I gave you a new topping.  How many more new types of pizzas could you add to the number you could already make?
Well, every new type will have the new topping.  And of the $m$ old toppings I can either include it or not.  So that is $2^m$ new types.
So if I get a second topping I can make $2^1$ new pizzas and now make $1+2$ types of pizzas.
And if I get a third topping I can make $2^2$ new pizzas and now make $1+ 2 + 4$ types of pizzas.
....
And if I get an $m$th toppin I can make $2^{m-1}$ new types of pizzas and now can make $1+2+4+ .... + 2^{m-1}$.
SO by those two different calculations I figure if I have $m$ toppings I can have $2^m-1$ different types or $1  + 2+ 4+ ..... + 2^{m-1}$ different types.
