CSC/MAT 208 (Spring 2024)

Homework 2 (Due on Monday 02/19)

Problem 1: Power Hour

Consider the following Racket definition

(define pow
  (lambda (x y)
    (if (zero? y)
        1
        (* x (pow x (- y 1))))))

Prove the following claim using mathematical induction. You may take the shortcut of evaluating a recursive function call directly to the branch that it selects in a single step.

Claim: For all natural numbers x, y, and z, (* (pow x y) (pow x z))(pow x (+ y z)).

In your proof, you can assume that the following lemma about pow holds:

Lemma: For all natural numbers x and y, (* x (pow x y))(pow x (+ y 1)).

In your proof, make sure to be explicit where you invoke both this lemma and your induction hypothesis.

Problem 2: Down By More Than One

Consider the following recursive Racket definitions:

(define even?
  (lambda (n)
    (cond [(zero? n) #t]
          [(= n 1)   #f]
          [else      (even? (- n 2))])))

(define iterate
  (lambda (f x n)
    (if (zero? n)
        x
        (iterate f (f x) (- n 1)))))

For this problem, you may take the shortcut of evaluating a recursive function call directly to the branch that it selects in a single step.

  1. First prove the following auxiliary claim about even:

    Lemma: For any natural number n, if (even? n) and n is not zero then (<= 2 n).

  2. Consider the following claim about iterate:

    For all natural numbers n and booleans b, if (even? n) then (iterate not b n)b.

    In a sentence or two, describe at a high-level why this claim is correct.

  3. Formally prove this claim, using the auxiliary claim from part (a).