Homework 1

CS 280 - Spring 2002

Due: Friday, Feb 1

To simplify the process of distributing papers for grading, each homework will consist of 3 parts.  Each part must be turned in separately.  In other words, each of parts A, B, and C will be placed in separate piles when homework is handed in on Friday.

Normally, graded homework is handed back in a self-service stack.  In other words, your homework grade is not private. If you prefer more privacy, clearly mark HOLD at the top of the first page of each piece (A, B, and C) of your homework; I will hold these papers for pick-up during my office hours.

Part A

  1. Problem 6, page 209 in the text. (recursive definitions)
     
  2. We use n straight lines to divide the plane into regions.  Use induction to prove that the regions can be colored using just two colors in such a way that any two adjacent regions regions have different colors.  Regions are considered to be adjacent if they share a side.

Part B

  1. Suppose we have n straight lines in the plane no two of which are parallel and no three of which intersect in a single point.  Use induction to show that the number of regions is 1 + n(n+1)/2. 
     
  2. Prove (by induction) or disprove the following statement: n2+n+41 is prime for all natural numbers n.  A number is prime if its only (positive) divisors are itself and 1. Note that to disprove a statement you only need to find a single counterexample.

Part C

  1. Use induction to show that the absolute value of the sum of n numbers is less than or equal to the sum of the absolute values of the n numbers.
     
  2. Problem 48, page 201 in the text. (find the flaw)