Do exercise 2.17 on pages 43-44.
Exercise 2.y1:
The following procedure is supposed to compute n^{2} + 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^{2} + 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^{2} + 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^{2} + n.
Base case: If n = 0, the answer is given as 0, which is equal to 0^{2} + 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^{2} + 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) | = n^{2} - 2n + 1 + n - 1 |
= n^{2} - n |
Conclusion: Therefore, by induction on n, we conclude that
for any integer n >= 0, (square-plus
n)
evaluates to n^{2} + 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^{2}+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.
(define leftmost-digit (lambda (integer) (if (< integer 10) ______________________ (leftmost-digit ____________________________))))
round-down
procedure from homework 1 generate a recursive
process or an iterative process? Justify your answer.