# MCS-177 Homework 2, Spring 2005

## Due: February 21, 2005

• Do exercise 2.17 on pages 43-44.

• Exercise 2.y1: 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 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 (n2+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. Also, answer the same question for the `round-down` procedure from homework 1.