Nothing against simplependulum's proof, but if we write then we can complete the induction step as was done in the original problem (first few posts of the thread).
Edit: Oh I guess the OP already did that. Well here's how I would write it then.
Induction step: Assume .
We want to show that .
Edit 2: Sorry sorry, I've been illiterate. chiph588@ already posted basically the same thing except for the very last step. But maybe my typesetting will be easier for the OP to follow..
Edit 3 (!): By the way, it's not necessary to use base case . We can use since .