Discrete Mathematics for Computer Science

86 CHAPTER 1 Sets, Proof Templates, and Induction

2. A survey of reading habits was proposed for the city of Lewisburg. Let U be the sample

set of adults in Lewisburg, F the set of females in the sample, B the set of readers who

have finished five or more books in the past year (called regular book readers), and P

the set of readers who read some of every issue of a periodical during the past year

(called the regular periodical readers). Use set notation to identify the following sets

of readers:

(a) Females who regularly read books or periodicals

(b) The men who read both books and periodicals regularly

(c) Adults who regularly read either books or periodicals, but not both

(d) The women who do not read either books or periodicals regularly

(e) The men who read books but not periodicals regularly

Now, describe in words the following sets:

(f) FnP

(g) F nBnP

(h) F n B n P

(i) FnBnP

0) Fn(PUB)-Fn(PnB)

3. For sets A and B, prove that A U (B - A) = A U B.

4. For sets A and B, prove that A n B = 0 ý* A C B.

5. Prove by induction that 3 + 11 + .. + (8n - 5) = 4n2 - n for n E N and n > 1.


6. Prove by induction that 2n + 1 < 3n - 1 for n E N and n > 3.


7. Prove that for every n E N that n^3 + n is even.


8. Prove by induction that 73 1 ( 8 n+2 + 9 2n+1) for every n e N.


9. Prove that b, = 5 • 2' + 1 is a closed form for the recursive relation ao = 6, al =
   11, and an = 3an--I-- 2an-2 for n > 2.


10. Let S C N and 3 e S. Also, assume that if x E S, then x + 3 e S. Prove that

13-n : n E NJ c S.

11. The country of Xabob uses currency consisting of coins with values of 3 zabots and
    5 zabots. If you cannot combine some number of these coins to pay a bill, the item is
    free. For what number of zabots are items free? Prove your answer.


12. Challenge: The name Strong Form of Mathematical Induction suggests that that form
    really is a logically different assertion than the Principle of Mathematical Induction.
    In fact, however, this is not so. It is not too difficult to prove one form from the other.
    (a) Assuming the Strong Form of Mathematical Induction, prove the Principle of
    Mathematical Induction. You need to do the following: Assume the hypothesis of
    the first form of the Principle of Mathematical Induction, and using just the Strong
    Form of Mathematical Induction, prove the conclusion of the (first form of the)

Principle of Mathematical Induction. So, assume T C N, some no E T,

and for every n > no, if n E T, then n + 1 e T. Then, using the Strong

Form of Mathematical Induction but not the (first form of the) Principle

of Mathematical Induction, prove that T = N. (For a statement of the first

form of the Principle of Mathematical Induction, see Section 1.7.1) (Hint: Let

T, = T U {0, 1 .... no - 1}. Prove, using the Strong Form of Mathematical In-