if , then .
This is true but how to prove it?
now what?
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 .
. QED.
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 .