
What does 3^n count?
I am asked to prove, combinatorially:
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:
RHS is the number of nonempty subsets of an element set.
LHS is the number of subsets of element subset whose largest element is , summed up.
So here's the best I could come up with: is the number of digit words you can create from elements with replacement, minus . Let's call it all digit words, not all zeros, from elements.
But I can't do the LHS. So far, I figure that, since the 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 is the number of words that have 1 or 2 in the position and 0 in the positions (positions are counted from 1).