# What does 3^n count?

• Feb 6th 2011, 04:44 PM
MSUMathStdnt
What does 3^n count?
I am asked to prove, combinatorially:

$2 \cdot 3^0+2 \cdot 3^1+2 \cdot 3^2+\ldots+ 2 \cdot 3^{n-1}=3^n-1$

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:
$2^0+2^1+2^2+\ldots+ 2^{n-1}=2^n-1$

RHS is the number of non-empty subsets of an $n$-element set.
LHS is the number of subsets of $n$-element subset whose largest element is $1 \le j \le n$, summed up.

So here's the best I could come up with: $3^n$ is the number of $n$-digit words you can create from $3$ elements with replacement, minus $1$. Let's call it all $n$-digit words, not all zeros, from $3$ elements.

But I can't do the LHS. So far, I figure that, since the $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 one-digit word can be created given three choices (that would be three).

Any help?
Thanks.
• Feb 7th 2011, 02:59 AM
emakarov
So, we are counting words made of {0, 1, 2}. Then $2\cdot 3^{j-1}$ is the number of words that have 1 or 2 in the position $j$ and 0 in the positions $j+1,\dots,n$ (positions are counted from 1).