SUNY Geneseo Department of Computer Science

Problem Set 4 -- Induction

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Friday, February 2

Purpose

The purpose of this problem set is to build familiarity with induction as a technique for mathematical proof. With this foundation, you will be prepared to go on and examine induction as a technique for proving claims about algorithms.

Background

This exercise is based on material in section 7.1.1 of our text. This material was also discussed in lecture on January 31.

Exercise

Prove the claims in the text's exercise 7.4, parts 1, 3, and 4.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office. Please bring written answers to each of the problems to the meeting.