Combinatorial Proof for the equation $\sum_{i=0}^j {j \choose i} 2^{j-i} = 3^j$

Question

$$\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.

Answer 1

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}}$$

Answer 2

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.