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

Question

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

Firstly, I'm trying to figure out what both sides count.
The left hand side counts the number of $\{0,1,2\}$ strings minus the number of $\{0,1\}$ strings. However, I feel this isn't an intuitive way of looking at it and there is probably a better way of counting the left hand side that can make the equality easier to understand.

Answer 1

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

Answer 2

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.

Answer 3

Suppose we are counting number of $\{0,1,2\}$ strings of length $n$ that has $2$ in it.

LHS: $\text{[Number of all such strings]} - \text{[Number of strings consist of only $0,1$]}$ .

RHS: first put $2$ to the first digit and then for the rest of the $n-1$ digits, we can put anything with $3^{n-1}$. Then, put $2$ to the second digit. Now, we counted the case where there is a $2$ in the first digit so put $0$ or $1$ to first digit with $2 $ options and we can put anything to $n-2$ digits after $2$ with $3^{n-2}$. Therefore, we have $2\cdot3^{n-2}$ options. Continuing like that, in the end put $2$ to the last digit and we can put $0$ or $1$ to first $n-1$ digits with $2^{n-1}$. Then in total, we have $\sum_{n=0}^{n-1}2^i3^{n-1-i}$ strings that have $2$ in it.