You are ordering a sandwich for lunch. If the sandwich shop boasts that they have different toppings for their sandwiches, and you can choose up to five for no extra cost, how many combinations of toppings can you get on your sandwich without having to pay more

Say you have 2 toppings: cheese and lettuce. You can either have just cheese, just lettuce, both, or neither. That's 4 combinations. If you add a third topping, say alfalfa sprouts, you can choose to have alfalfa sprouts on the sandwich or not which is two possible choices, and for each of those two choices you still have the 4 other combinations, so you get 2 × 4 = 8 combinations with three toppings. If you keep going like this, you notice that each time you add a topping you multiply the number of combinations by 2. So, with N different toppings you have 2 × 2 × ... × 2 (i.e. 2 multiplied by itself N times) combinations. This is 2

2

N

. When N = 8, you get 28

2

8

, which is indeed 256.