$$\sum_{i=0}^j {j \choose i}2^{j-i} = 3^j$$

My approach: I know the binomial way to do this is to think of the RHS as $(1+2)^j$ and then expand using binomial like so: $$(1+2)^j = \sum_{i=0}^j {j \choose i} \cdot 2^{j-i} \cdot 1^i$$ $$ = (1+2)^j = \sum_{i=0}^j {j \choose i} \cdot 2^{j-i}$$

But I am not sure how to do the combinatorial proof.

  • $\begingroup$ What do you mean by 'the combinatorial proof'? $\endgroup$ – caverac Dec 21 '18 at 10:36
  • $\begingroup$ @caverac In a combinatorial proof, you count the same set of objects in two different ways to show that the expressions are equal. For instance, to prove the identity $k\binom{n}{k} = n\binom{n - 1}{k - 1}$, you would count committees of size $k$ with a chairperson that can be selected from a group with $n$ people. The left side counts the number of ways of selecting a group of $k$ people, then choosing a chairperson from among the group. The right side counts the number of ways of selecting a chairperson, then selecting the other $k - 1$ members of the committee from the remaining people. $\endgroup$ – N. F. Taussig Dec 21 '18 at 10:46
  • $\begingroup$ @N.F.Taussig Thanks for the explanation, I didn't realize the OP was looking for a proof different to the one he sketched, which is completely valid $\endgroup$ – caverac Dec 21 '18 at 12:20

A combinatorical proof could go as follows:

  • The number of digit sequences of length $j$ formed with $3$ digits $\{1,2,3\}$ is: $\color{blue}{3^j}$.
  • Now, fix one digit. For example $1$. It can occur $\color{blue}{i=0,..,j}$ times in a digit sequence.
  • The number of ways to place $i$ times the digit $1$ is: $\color{blue}{\binom{j}{i}}$
  • You can fill the remaining $j-i$ places with any of the two other digits: $\color{blue}{2^{j-i}}$ All together: $$\boxed{\color{blue}{\sum_{i=0}^j \binom{j}{i}2^{j-i} = 3^j}}$$
  • $\begingroup$ I like your use of colour! :) $\endgroup$ – Shaun Dec 21 '18 at 11:27

The problem - how many $j$-length vectors can be composed of the digits $\{0,1,2\}$?

RHS - straight forward.

LHS - first, pick the $i$-indexes in the vector where 0 appears - $j \choose i$, then choose between $\{1,2\}$ for the $j-i$ remaining indexes - $2^{j-i}$ options of doing so. Summing over all $i$'s gives all the required vectors.


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.