I don't know exactly what your problem is, but if you've done the first two parts you should be quite well on your way. Now all you must do is :

1. Show that the expression satisfies the base case.

2. Take the expression, assume it's

**true** for some arbitrary value (call that k), and then by just manipulating the expression (eg. ADDING THE SAME THING TO BOTH SIDES), show that "P(k+1)" is also true. In other words, keep working on it till you see "hey that's one of the forms of P(k+1)"...

OK, so there's your algebra in the terms of your earlier courses. Now what you do is, having convinced yourself by familiar ways that the statement is indeed true, is put that discovery inside the broader inductive principle framework the SG reveals. (ie. Induction in terms of Sets, basically).

It is a bit tricky (or I found it so), so don't get despondent if it goes slowly. It took me hours to get it figured (I hope, anyway). You want to make use of the fact that 2

^{n+1} = 2n(2), for one thing. (I actually don't remember in detail why that helped, this just rings a bell).

That's most of it. Just get LHS (or RHS if you really must) into the form it would be if it were P(k+1) instead of P(k).Then take RHS (or vice versa if you've chosen to go the other way), and rearrange it. To give yourself heart, put all that down on your answer sheet and imagine you'll get most of your marks for this part, anyway. Now take RHS and start to express it in different ways, until it's the RHS of of P(k+1).

If LHS of P(k+1) = RHS of P(k+1) then P(k+1) is

**true**, right?