# 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 n2 + 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 n2 + 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 n2 + 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 n2 + n.

Base case: If n = 0, the answer is given as 0, which is equal to 02 + 0, and so is the correct answer.

Induction hypothesis: Assume that for any integer k with 0 <= k < n, `(square-plus `k`)` evaluates to k2 + 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)2+(n-1). Doing the algebra,  (n-1)2+(n-1) = n2 - 2n + 1 + n - 1 = n2 - 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 n2 + 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.