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.