CSI  210  -  Discrete  Structures  -  Fall  2009




-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=--=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=--=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=--=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-



         Assignment 7;  OPTIONAL ASSIGNMENT

(We will not collect and formally grade this assignment. There will
be an answer key posted right around the end of Thanksgiving weekend.
You should study and do these problems as part of your preparation
for Exam II.)


READ  Sections 1, 2 and 3 of Chapter 4, Sections 1, 2 and 3 of
      Chapter 5, and Section 5 of Chap. 7.



1)  Consider the following: P(n) is the statement

    1^3 + 2^3 + 3^3 + ... + n^3  =  (n(n+1)/2)^2   for positive integer n.

         n
i.e.,   SUM (i^3)  =  (n(n+1)/2)^2   for positive integer n.
        i=1

a)  What is the statement P(1)?

b)  Show that P(1) is true, completing the basis step for an inductive
    proof that the statement holds for all positive integers.

c)  What is the inductive hypothesis?

d)  What do you need to prove in the inductive step?

e)  Complete the inductive step.  (just a LOT of algebra)



2)  Prove that for all positive integers n,

     n
    SUM (i!)(i)  =  (n+1)! - 1
    i=1                                (algebra again)


3)  Show that every positive integer n can be written as a sum of
    distinct powers of 2. (E.g., 21 = 2^0 + 2^2 + 2^4)
  (HINT: consider proof by cases in the ind. step where n is even or odd)


4)  Consider the following recursive definition of a simple language
    of arithmetic expressions involving binary operators. The vocabulary
    consists of variablesl x1, x2, x3, ..., the operators + and -, and
    left and right parentheses (, ).

    I.  A single variable xi is an expression.
    II. If E1 and E2 are expressions, then so are (E1 + E2) and (E1 - E2).

Prove by induction on n, that for n>0, any expression containing n
variable occurrences has exactly n-1 operators.


5)  How many strings are there of 4 lowercase letters that have the
    letter x in them?


6)  How many subsets of a set with 100 elements have more than 1
    element in them?


7)  Show that in a small class of 9 students, either there are at
    least 3 male students or at least 7 female students.


8)  You are facing a discrete mathematics exam (aaugh!) of 42 true or
    false questions. It turns out that for 17 questions the answer 
    is true (but you don't know which ones). How many different
    answer keys might exist for this exam?



-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=--=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=--=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=--=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-