I'm having trouble combinatorially proving: $$2 \cdot 3^0 + 2 \cdot 3^1 + 2 \cdot 3^2 + \cdots 2 \cdot 3^{n-1} = 3^n-1$$
I understand that the right hand side can be expressed as the number of possible n-length strings from an alphabet {a,b,c}, minus some specific string, such as "abc".
I see also that the left hand side is a finite geometric series where a = 2 and r = 3 and that I can algebraically prove its sum to be $3^n - 1$.
But how can I prove this combinatorially? How can I show the geometric series to be an answer to the same n-length string problem as the right side, if that is the correct interpretation for the proof?
$3^n-1$ is the number of strings of length $n$ with characters $\{a,b,c\}$ that isn't $\underbrace{aa\ldots a}_n$.
If the first character is $b,c$, the remainder of the characters can be whatever, so there are $2\cdot3^{n-1}$ strings of this form.
If the first character is $a$, then the number of strings of length $n$ with characters from $\{a,b,c\}$ not including $\underbrace{aa\ldots a}_n$ is the same as the number of strings of length $n-1$ with the same properties, of which there are $3^{n-1}-1$.
So, combinatorially, you can see that $3^n-1=2\cdot3^{n-1}+3^{n-1}-1$, which is the desired relation.