CS212 Exercises

I've put these exercises together so that you could get practice with doing induction yourself.  Try and do each of them, and when you think you've got a good proof, see a member of the course staff in office hours or consulting to check your answer.

For each proof, you should follow this format and fill in the details:
Look at the Induction Examples page to see some well constructed proofs.

The following function definitions will be useful:
NOTE: These are not necessarily implemented as part of the Scheme language.

(define (power x y)
  (if (zero? y)
      1
      (* x (power x (- y 1)))))

(define (copy l)
  (if (empty? l)
      empty
      (cons (head l) (copy (tail l)))))

(define (compose f g)
  (lambda (x) (f (g x))))

(define (reverse l)
  (if (empty? l)
      empty
      (append (reverse (tail l)) (list (head l)))))

(define (append x y)
  (if (empty? x)
      y
      (cons (head x) (append (tail x) y))))

(define (revapp x y)
  (if (empty? x)
      y
      (revapp (tail x) (cons (head x) y))))

(define (length l)
  (if (empty? l)
      0
      (+ (length (tail l)) 1)))

(define (map f l)
  (if (empty? l)
      empty
      (cons (f (head l)) (map f (tail l)))))

(define (member? x l)
  (cond ((empty? l) #f)
        ((equal? x (head l)) #t)
        (else (member? x (tail l)))))

This first section asks you to write definitions for inductively defined sets:

Inductively define the set of positive odd integers.

Inductively define the set of well-formed formulas in predicate calculus.
See Problem Set 3 to review details about well-formed formulae.

Inductively define the set of positive integers not divisible by 5.

Challenge problem: Inductively define the set of strings.

Prove the following with induction. Clearly state the set you're inducting over, and clearly state what type of induction you are using. When applicable, use structural induction in preference to mathematical induction.

1 + nh (1 + h)ⁿ for all non-negative values of n. h is greater than -1.  This is called Bernoulli's inequality.

Use mathematical induction to show that n²-1 is divisible by 8 whenever n is an odd positive integer.

Which amounts of money can be formed using just dimes and quarters? Prove your answer using a form of mathematical induction (either weak or strong).

n! < nⁿ whenever n is a positive integer greater than 1

(power x y) = x^y

(map f (map g x)) = (map (compose f g) x)

(reverse (reverse x)) = x

(append x y) = (revapp (revapp x empty) y)
Challenge: Why would we want to use the later expression instead of (append x y)? What is the running time of both expressions?

(append x empty) = x

(+ (length x) (length y)) = (length (append x y))

(append (map f x) (map f y)) = (map f (append x y))

(reverse x) = (revapp x empty)

(length (filter p x)) (length x)

© 1999 Cornell University Computer Science