Modeling a power as sum of combination

[johnhaddad]

Hello all,

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).

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?

Thanks!

 

[jvicens]

First, let's define what combination and permutation mean in this context. Combination refers to the number of ways we can choose a group of r objects from a larger set of n objects, where the order does not matter. Permutation, on the other hand, refers to the number of ways we can arrange a group of r objects from a larger set of n objects, where the order does matter.

To understand the equation 3^n = summation (from i=0 to n) of (n choose i)*(2^i), let's break it down step by step. The left side of the equation, 3^n, represents the number of ways we can arrange n items in 3 boxes, where the order does matter. This is similar to the concept of permutation, where we are arranging objects in a specific order.

Now, let's look at the right side of the equation. The summation symbol (∑) means we are adding up all the terms from i=0 to n. The term (n choose i) represents the number of ways we can choose i items from a set of n items, where the order does not matter. This is similar to the concept of combination. The term (2^i) represents the number of ways we can arrange i items in 2 boxes, where the order does matter.

So, in simpler terms, the right side of the equation is saying that we are adding up the number of ways we can choose a certain number of items (n choose i) and then arranging them in 2 boxes (2^i). This is equivalent to the left side of the equation, where we are arranging n items in 3 boxes.

To use your example of placing balls in boxes, if we have 5 balls and 3 boxes, we can choose 0 balls to put in box 1, and then arrange the remaining 5 balls in 2 boxes. This would be represented as (5 choose 0)*(2^0) = 1*1 = 1. Similarly, we can choose 1 ball to put in box 1, and then arrange the remaining 4 balls in 2 boxes. This would be represented as (5 choose 1)*(2^1) = 5*2 = 10. If we continue this process for all possible combinations, and add them up, we will get 3^5, which is the left side of