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

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

• What do you mean by 'the combinatorial proof'? – caverac Dec 21 '18 at 10:36
• @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. – N. F. Taussig Dec 21 '18 at 10:46
• @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 – 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}}$$
• I like your use of colour! :) – 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.