MCS-177 Homework 2, Fall 2005

Due: September 21, 2005

Do exercise 2.17 on pages 43-44.
Exercise 2.y1: 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 2.y2: Prove by induction on n that the presents-on-day procedure given to you on page 44 has the following property. For any integer n that is greater than or equal to 1, (presents-on-day n) computes (n²+n)/2. Be sure you are looking at the presents-on-day procedure you were given, not the presents-through-day you wrote yourself. Also, if you are following the pattern of other proofs, be sure to keep in mind that here the smallest legal value of n is 1, not 0 as in some of the other proofs.
Exercise 3.x1: Suppose we want to find the leftmost digit of a nonnegative integer. For example, the leftmost digit of 314159 is 3. Let's write a procedure, leftmost-digit, so that (leftmost-digit 314159) would evaluate to 3.
1. Fill in the blanks in the following procedure definition. You may assume the argument is legal, an integer that is not negative.
```
(define leftmost-digit
  (lambda (integer)
    (if (< integer 10)
        ______________________
        (leftmost-digit ____________________________))))
```
2. Does this procedure generate a recursive process or an iterative process? Justify your answer.
3. Does the round-down procedure from homework 1 generate a recursive process or an iterative process? Justify your answer.

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