Welcome to Playing.with.Code!

will be uploaded soon!

1.3.4 Induction and Recursion

Steven S. Skiena

Failure to find a counter example to a given algorithm does not mean "it is obvious" that the algorithm is correct. A proof or demonstration of correctness is needed. Often mathematical induction is the method of choice.

When I first learned about style mathematical induction it seemed like complete magic. You proved a formula for some basic case like 1 or 2, then assumed it was true all the way to n-1 before proving it was true for general n using the assumption. That was a proof? Ridiculous!.

When I first learned the programming technique of recursion it also seemed like complete magic. The program tested whether the input argument was some basic like 1 or 2. If not, you solved the bigger case by breaking it into pieces and calling the subprogram itself to solve these pieces. The initial or boundary condition terminates the recusion. Once you understand either recursion or induction, you should be able to see why the other one also works.

I've heard it said that a computer scientist is a mathematician who only knows how to prove things by induction. This is partially true because the computer scientists are lousy at proving things, but primarily because so many of the algorithms we study are either recursive or incremental.

Consider the correctness of insertion sort, which we introduced at the beginning of this chapter. The reason it is correct can be shown inductively:

One must be suspicious of inductive proofs, however, because very subtle reasoning errors can creep in. The first are boundary errors. For example, our insertion sort corectness proof above boldly stated that there was a unique place to insert x between two elements, when our basis case was a single-element array. Greater care is needed to properly deal with the special cases of inserting the minimum or maximum elements.

The second and more common class of inductive proof errors concerns cavallier extension claims. Adding one extra item to a given problem instance might cause the entire optimal solution to change. This was the case in our scheduling problem. The optimal schedule after inserting a new segment may contain none of the segments of any particular.....