Modeling a power as sum of combination

[johnhaddad]

Homework Statement

I am trying to come up with a logical explanation (using an example from real life modeled in Combination and/or Permutation) to show that 3^n = summation (from i=0 to n) of (n choose i)*(2^i). In other words, I am trying to pose a combinatorial/selection/combination question that then can be modeled as both sides of the equation.

Homework Equations

Combinations and Permutations.

The Attempt at a Solution

My trial is that 3^n could be modeled as having 3 boxes and we are placing n items in it (eg. balls). So, if we pick n=5, it is as selecting 3 balls to put in box one, then returning them, then selecting 3 balls to put in box 2, then returning..etc while the order of selection is "don't care". However, I still can't show how that translates into the right side of the equation. Any help or pointers?

 

[mighty2000]

I believe I have a logical explanation for the equation 3^n = summation (from i=0 to n) of (n choose i)*(2^i). Let us consider a real-life example of a pizza restaurant that offers 3 different toppings: pepperoni, mushrooms, and onions. The restaurant offers a special deal where customers can choose any combination of toppings for their pizza, with a limit of n toppings.

Now, let's say a group of friends wants to order a pizza with exactly 5 toppings. We can model this situation using combinations, where we have 3 choices for each topping and we need to choose 5 toppings in total. This can be represented as 5C5 or (5 choose 5), which equals 1. This means there is only 1 way to choose 5 toppings from a selection of 3.

However, if we look at the right side of the equation, we can see that it is a summation of (n choose i)*(2^i), where n is the total number of toppings and i represents the number of toppings from a specific topping group. In our pizza example, n=5 and we can have i=0, 1, 2, 3, 4, or 5.

Now, let's break down the right side of the equation. When i=0, we have (5 choose 0)*(2^0) = 1*1 = 1, which represents the number of ways to choose 0 toppings from a selection of 3. This makes sense, as we can simply choose no toppings at all.

When i=1, we have (5 choose 1)*(2^1) = 5*2 = 10, which represents the number of ways to choose 1 topping from a selection of 3. This makes sense, as we can choose any one of the 3 toppings and then add an extra topping of our choice.

Similarly, when i=2, we have (5 choose 2)*(2^2) = 10*4 = 40, which represents the number of ways to choose 2 toppings from a selection of 3. This makes sense, as we can choose any two of the 3 toppings and then add an extra topping of our choice.

Continuing this pattern, we can see that the summation on the right side of the equation represents all the possible combinations