Computer Science 280: Homework 3

Section   Number       Points    Comments
2.4       6              4       Use the definition of divisibility!
          12(a),(b)      2
          14             5       Don't just give the answer.  Prove it!  Hint: Think in 
                                 terms of prime factors.  (There's a reason that the 
                                 problem is in this chapter ...)
          16             3
          20             5
          28(a),(b)      2
          30(a),(b)      2
2.5       22(c),(d)      6

Extra problems: 

1. [5 points] Do problem 0.2, 33 in DAM3 (DAM2: 0.4, 24), then prove (by induction) that
your formula for f(n) in part (b) is correct.


2. [8 points] Let S be the smallest set such that has the following two properties: 

 S1. 1  is in S, and
 S2. if x is in S then x+2 is in  S.

Define On as inductively as follows:

 O1 = {1}
 O(n+1) = On ∪ {2n+1}.  

Let O = ∪ On (note that ∪ is a union symbol, in case it doesn't come our right on your browser). 

 (a)  Prove that by induction that On = {1,3, ..., 2n-1}.
Note that it follows that O is the set of odd numbers.

 (b)  Prove that O = S.  (Recall that this means you have to prove 
that S is a subset of; O and O is a subset of S.  To show 
that S is a subset of O, use the fact that S  is the smallest 
set satisfying S1 and S2.  To show that O is a subset of S, prove by 
induction that On is a subset of S.)


3. [5 points] Define a function h inductively as follows.

 h(1) = h(2) = 1
 h(n) = h(n-1)^2 + h(n-2) if n > 2.  

The function h grows quickly after the first few values.  

(a) Compute h(5).
(b) Prove that for all n > 1 that the greatest common divisor of h(n) and
h(n-1) is 1 (i.e., h(n) and h(n-1) are relatively prime).  (Hint:
induction is a good approach here).