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

Any help?

Thanks.