# Thread: What does 3^n count?

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

RHS is the number of non-empty 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 one-digit word can be created given three choices (that would be three).

Any help?
Thanks.

2. So, we are counting words made of {0, 1, 2}. Then $\displaystyle 2\cdot 3^{j-1}$ 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).