Computer Science 280: Homework 5

Don't forget: put your name on all pages, put the grade sheet on the front, then staple all the pages together.

Homework 5:

2/26/03 (due 3/12/03) Read 3.1-3.3. All this material will be covered on the prelim.

Section   Number     Points    Comments
3.1 	  2	     5
3.2 	  13 (a)     3         You do *not* need to list cycles which are reverses or
                               cyclic shifts of cycles you already listed.
	  14(a),(c)  5
	  18(a)      4 	       Hint: do a proof by contradiction.
	  22 	     5
3.3 	  2(b) 	     4
	  3(b) 	     2
	  4(b),(c)   4
	  9          8

[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 U {2n+1}. (U stands for "union" here.)

Let O = U On.

(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 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.)