MCS-177 Homework 2, Spring 2003

Due: February 24, 2003

Do exercise 2.7 on page 38.
Exercise 2.x1: The following procedure is supposed to compute n² + n for any nonnegative integer n. The procedure has a bug in it, and the "proof" of its correctness has a corresponding error. Correct both the procedure and the proof. That is, show what change needs to be made to the procedure so that it computes n² + n for any nonnegative integer n, and show what change needs to be made to the proof so that it correctly shows that your modified version of the procedure indeed computes n² + n for any integer n >= 0. You are to leave the overall recursive form of the procedure intact; it is not fair to have your corrected version just do (+ (* n n) n).
```
(define square-plus
  (lambda (n)
    (if (= n 0)
        0
        (+ n
           (square-plus (- n 1))))))
```
Theorem: For any integer n >= 0, (square-plus n) evaluates to n² + n.
Base case: If n = 0, the answer is given as 0, which is equal to 0² + 0, and so is the correct answer.
Induction hypothesis: Assume that for any integer k with 0 <= k < n, (square-plus k) evaluates to k² + k.
Inductive step: For n > 0, we see by inspection of the code that (square-plus n) adds n to whatever (square-plus (- n 1)) evaluates to. Because n > 0, we have 0 <= n-1 < n, and so we can apply the induction hypothesis, substituting (n-1) for k. This tells us that (square-plus (- n 1)) evaluates to (n-1)²+(n-1). Doing the algebra,

(n-1)²+(n-1) = n² - 2n + 1 + n - 1
= n² - n
This is very nearly our desired answer, with the only difference being that we want +n on the end. This explains why we add n to get the right answer.
Conclusion: Therefore, by induction on n, we conclude that for any integer n >= 0, (square-plus n) evaluates to n² + n.
Exercise 3.x1: Suppose we take a nonnegative integer, such as 314159, and we number the digits from right to left. For example, digit number 2 of 314159 is 5 because the second digit from the right is 5. We would like a procedure, digit-number, so that (digit-number 2 314159) would evaluate to 5. Similarly, (digit-number 6 314159) would evaluate to 3 (the sixth digit from the right). Of course, the integer whose digits we are interested in needn't be 314159; for example, (digit-number 3 1271) would evaluate to 2.
1. Fill in the blanks in the following procedure definition. You may assume both arguments are legal; the position is at least 1, and the integer is not negative.
```
(define digit-number
  (lambda (position integer)
    (if ______________________
        (remainder integer 10)
        (digit-number (- position 1) ____________________________))))
```
2. Does this procedure generate a recursive process or an iterative process? Justify your answer.
Do exercise 3.19 on page 72.

(`n`-1)²+(`n`-1)	= `n`² - 2`n` + 1 + `n` - 1
	= `n`² - `n`