Prove for all

Proof: i) Show P(1) holds.

LHS =

RHS =

LHS RHS, thus, P(1) holds.

ii) Assume P(k) holds for some

That is, assume .

To show: P(k + 1):

Then

Not sure what to do next. In my next step, I said . But I'm not sure if this is the right path to take.