1.13

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.