(+ (* 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.
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.
(define digit-number (lambda (position integer) (if ______________________ (remainder integer 10) (digit-number (- position 1) ____________________________))))