Prove combinatorically that $\sum_{i=1}^{n}2^{i-1}3^{n-i}=3^n-2^n$.

Question

Prove combinatorically that $$\sum_{i=1}^{n}2^{i-1}3^{n-i}=3^n-2^n\,.$$

For the right expression I was thinking about the problem "amount of $n$-long ternary vectors with at least one '$2$'", but I can't seem to solve it with the left side so idk.

Looking for a hint.

Answer 1

Consider all the ternary strings with $n$ terms (i.e., a sequence $(a_1,a_2,\ldots,a_n)$ with $a_k\in\{0,1,2\}$ for all $k=1,2,\ldots,n$). There are $3^n$ of them. However, $2^n$ of them are made up by $0$ and $1$. Therefore, $3^n-2^n$ is the number of ternary strings of length $n$ such that $2$ appears as an entry. Now, prove that $2^{i-1}3^{n-i}$ is the number of ternary strings of length $n$ such that the first position of $2$ in the string is the $i$-th entry (i.e., $a_i=2$ but $a_1,a_2,\ldots,a_{i-1}\in\{0,1\}$).

The same idea can be used to show that $$(y-x)\,\sum_{i=1}^n\,x^{i-1}\,y^{n-i}=y^n-x^n\tag{*}$$ for all positive integers $x$ and $y$ such that $x<y$. This in turn proves that the equality (*) is in fact a polynomial identity.

Answer 2

As in the question, the right side is the number of ternary strings of length $n$ that include at least one $3$. Each element of the left side sum corresponds to the number of ternary strings of length $n$ with the first $3$ in position $i$. So for $n=3$ we have $9+6+4=3^3-2^3$. There are $9$ strings of length $3$ with the first $3$ in the first location, $6$ with the first $3$ in the second location, and $4$ with the first $3$ in the third.