Combinatorial Proof of $3^n - 2^n = \sum_{i=0}^{n-1}2^i3^{n-1-i}$

The LHS counts the number of length-$n$ strings in $\{0,1,2\}$ that contains at least one $2$.

So consider the first position where a $2$ appears. Before that point, it must be a $\{0,1\}$-string, and after that point it can be any $\{0,1,2\}$-string, giving the RHS.


As you note, the left side counts the number of $n$-digit strings over the alphabet $\{0,1,2\}$ minus the number of $n$-digit strings over the alphabet $\{0,1\}$. Therefore the left side counts the number of $n$-digit strings over $\{0,1,2\}$ that contain at least one $2$.

Denote as $S$ the set of $n$-digit strings over $\{0,1,2\}$ that contain at least one $2$, whose cardinality we want to count. Partition $S$ into sets $S_0$ through $S_{n-1}$, where $S_i$ is the number of $n$-digit strings over $\{0,1,2\}$ that contain at least one $2$, and where the first $2$ is in the $i+1$-st position. It’s easy to see that $S=\bigcup_{i=0}^{n-1}S_i$. (The first $2$ must be in one of the positions $1$ through $n$, and the sets $S_i$ partition $S$, as no string can have its first $2$ in more than one position.

The strings in $S_i$ must begin with $i$ digits from $\{0,1\}$ ($2^i$ possibilities), must have the digit $2$ in the $i+1$st position ($1$ possibility), and must end with $n-i-1$ digits from $\{0,1,2\}$ ($3^{n-i-1}$ possibilities). By the multiplication and addition principles of counting, the cardinality of $S_i$ is $\sum_{i=0}^{n-1}2^i3^{n-1-i}$.