Another way to write this is as follows:

Prove that

To prove this by induction, see if it works for the base case of

, thus base case holds.

The next step is to ASSUME the rule holds for k. Take it for granted that:

Now, using this result, try to prove that the rule also holds for k+1.

Here's a tip: