
What does 3^n count?
I am asked to prove, combinatorially:
$\displaystyle 2 \cdot 3^0+2 \cdot 3^1+2 \cdot 3^2+\ldots+ 2 \cdot 3^{n1}=3^n1$
Are they kidding about this? It took me less than half a minute to prove it by factoring out the 2 and using the geometric series.
The book has an example which says:
$\displaystyle 2^0+2^1+2^2+\ldots+ 2^{n1}=2^n1$
RHS is the number of nonempty subsets of an $\displaystyle n$element set.
LHS is the number of subsets of $\displaystyle n$element subset whose largest element is $\displaystyle 1 \le j \le n$, summed up.
So here's the best I could come up with: $\displaystyle 3^n$ is the number of $\displaystyle n$digit words you can create from $\displaystyle 3$ elements with replacement, minus $\displaystyle 1$. Let's call it all $\displaystyle n$digit words, not all zeros, from $\displaystyle 3$ elements.
But I can't do the LHS. So far, I figure that, since the $\displaystyle n$ on the RHS stands for word length, I feel like the exponent on LHS might represent the length, too. But 2 times 3^0=2 is not exactly the number of ways ways a onedigit word can be created given three choices (that would be three).
Any help?
Thanks.

So, we are counting words made of {0, 1, 2}. Then $\displaystyle 2\cdot 3^{j1}$ is the number of words that have 1 or 2 in the position $\displaystyle j$ and 0 in the positions $\displaystyle j+1,\dots,n$ (positions are counted from 1).