Let's do a “pizza proof” again. We need to find a question about pizza toppings which has \(2^n\) as the answer. How about this: If a pizza joint offers \(n\) toppings, how many pizzas can you build using any number of toppings from no toppings to all toppings, using each topping at most once?
On one hand, the answer is \(2^n\text{.}\) For each topping you can say “yes” or “no,” so you have two choices for each topping.
On the other hand, divide the possible pizzas into disjoint groups: the pizzas with no toppings, the pizzas with one topping, the pizzas with two toppings, etc. If we want no toppings, there is only one pizza like that (the empty pizza, if you will) but it would be better to think of that number as \({n \choose 0}\) since we choose 0 of the \(n\) toppings. How many pizzas have 1 topping? We need to choose 1 of the \(n\) toppings, so \({n \choose 1}\text{.}\) We have:
Pizzas with 0 toppings: \({n \choose 0}\)
Pizzas with 1 topping: \({n \choose 1}\)
Pizzas with 2 toppings: \({n \choose 2}\)
\(\displaystyle \vdots\)
Pizzas with \(n\) toppings: \({n \choose n}\text{.}\)
The total number of possible pizzas will be the sum of these, which is exactly the left-hand side of the identity we are trying to prove.
Again, we could have proved the identity using subsets, bit strings, or lattice paths (although the lattice path argument is a little tricky).