21
$\begingroup$

Using the following equation:

$$\sum_{k=0}^n {n \choose k}3^k=4^n$$

I need to prove that both sides of the equation solve the same combinatorial problem.

It's easy to see that the right side of the equation is counting number of ways to divide $n$ different balls into $4$ buckets.

Is it correct to say that the left side of the equation solve the same problem the following way (?):

Since $\sum\limits_{k=0}^n {n \choose k} 3^k= \sum\limits_{k=0}^n {n \choose n-k}3^k$, we can change the equation to:

$$\sum_{k=0}^n {n \choose n-k}3^k=4^n$$

And from the new equation, it is easier to see that each binomial coefficient chooses number of balls to put in the first bucket, and $3^k$ divides the rest $k$ balls between the rest 3 buckets without limitation.

$\endgroup$
7
  • 1
    $\begingroup$ I assume you don't want this: $\sum_{k=1}^n {n \choose k}3^k= \sum_{k=1}^n {n \choose k} 1^{n-k} 3^k=(1+3)^n = 4^n$... $\endgroup$
    – lhf
    Sep 23, 2011 at 11:33
  • 1
    $\begingroup$ Thanks @lhf, but no, i'm just looking for Combinatorical explanation. $\endgroup$
    – MichaelS
    Sep 23, 2011 at 11:35
  • 3
    $\begingroup$ @MichaelS: Your combinatorial argument is simple and correct. $\endgroup$ Sep 23, 2011 at 11:49
  • 1
    $\begingroup$ @ChristianBlatter, Thanks! Happy to see i got it right.. $\endgroup$
    – MichaelS
    Sep 23, 2011 at 12:13
  • 2
    $\begingroup$ Everything is fine. For myself, I prefer to count the words of length $n$ over the alphabet $\{1,2,3,4\}$. Same analysis. $\endgroup$ Sep 23, 2011 at 14:24

2 Answers 2

18
$\begingroup$

Yes, I agree with your interpretation of the left side, and also lhf's comment can be seen in the same way:

  1. $4^n$ the ways of divide $n$ balls in $4$ boxes
  2. $(3+1)^n$ the same as above
  3. $ \sum_{k=0}^n {n \choose k} 1^{n-k} 3^k$ for every $k$, the ways to choose $k$ balls among the $n$ balls you have, times the ways to put $n-k$ balls in a box, times the ways to put the remaining $k$ balls in the remaining $3$ boxes
  4. $\sum_{k=0}^n {n \choose k}3^k$ as above, using $1^{n-k}=1$
$\endgroup$
4
  • $\begingroup$ Thanks! Happy to see i got it right :) $\endgroup$
    – MichaelS
    Sep 23, 2011 at 12:12
  • 2
    $\begingroup$ The result you are trying to prove is not correct and the interpretation you give is flawed. $\endgroup$ Sep 23, 2011 at 12:13
  • $\begingroup$ Emanuele, I've wrote in the question k=1 instead of k=0, please edit your answer, so the proof won't be wrong. I've already edited the question to k=0. $\endgroup$
    – MichaelS
    Sep 23, 2011 at 12:19
  • $\begingroup$ Sorry. I just copied lhf's identity because too lazy, didn't note that typos. I assume @Dilip was referring to that. $\endgroup$ Sep 23, 2011 at 12:22
1
$\begingroup$

The RHS looks like the formula for the number of base-4 strings. So we can also interpret the LHS similarly to the balls counting as counting all possible base-3 strings that can be placed in the $n$ length string and filling the rest with the remaining digit.

For example

$$XXX012201XX021XX$$ where $\binom n k$ chooses where $0,1,2$ go and $3^k$ counts every possible string.

You should be careful when specifying buckets since they are distinct, which is clear from the ordering of a string.

$\endgroup$

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.