Do exercise 2.17 on pages 43-44.
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,
) 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,
evaluates to k2 + k.
Inductive step: For n > 0, we see by inspection of the code that
) 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|
Conclusion: Therefore, by induction on n, we conclude that
for any integer n >= 0,
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
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.
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
(define leftmost-digit (lambda (integer) (if (< integer 10) ______________________ (leftmost-digit ____________________________))))
round-downprocedure from homework 1 generate a recursive process or an iterative process? Justify your answer.