From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Call the statement and the general term

Step 1: Show that the statement holds for the basis case

Since , the basis case is true.

Step 2: Assume that holds.

Step 3: Show that on the assumption that the summation is true for k, it follows that it is true for k + 1.

It's easier to factor than expand. Notice the common factor of (k + 1)(k + 2)(k + 3).

This should be equal to the formula when k = k + 1:

Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that S_n holds for all natural n.

Back to Chapter 1.