Use a combinatorial argument to prove that : $3^n = $$\sum_{k=0}^n{n \choose k}2^k. $

I've seen the mathematical proof of this using the Pascal's identity; and I am trying to come up with a combinatorial proof/analogy to mimic a real world situation.

As far as LHS is concerned, I have come up with this analogy:

Assume your job is to give out free candies.

On the first day, you give candies to three kids. Next day each of them brings two of their friends. On day $n$, you give out $3^n$ candies.

Can someone provide a good analogy for the RHS such that LHS = RHS is evident?


HINT: You’ll have a hard time making it work with the story that you’ve chosen. Try this instead. You have $n$ candies, all of different flavors, and you want to know in how many different ways you can distribute them to three children, Vanessa, Sunny, and Melissa. Clearly the answer is $3^n$. Now suppose that you decide to split $k$ of the $n$ candies between Vanessa and Sunny and give the rest to Melissa; in how many different ways can you do that?

  • $\begingroup$ So $2^k$ would represent the number of possible functions from k to Vanessa and Sunny, whereas the rest automatically goes to Melissa? $\endgroup$ – Corp. and Ltd. Nov 20 '16 at 1:22
  • $\begingroup$ @Corp.andLtd.: You’ve got it. $\endgroup$ – Brian M. Scott Nov 20 '16 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.