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

The basis case is when

and using in the formula you get:

Since these are equal, the basis case is true.

Now, I will show that on the assumption that the summation is true for n, it follows that it is true for

Which should be equal to the formula when :

Back to Chapter 1.