(+ (* 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.
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) ____________________________))))