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: