Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.13


We will prove this by strong induction.

Suppose is arbitrary integer greater than zero. Suppose theorem is correct for all integers and . We have the following possible cases:

  • Case : We have . Clearly theorem is correct for .

  • Case : For , we have . Clearly theorem is correct for .

  • Case : Since theorem is correct for all where , we have:
    .
    .
    Now consider :
    .
    .
    .
    We know that and :
    Thus we get: .
    .
    .

    Thus theorem is correct for .

Thus for all the cases we can conclude that theorem is correct for all .