Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 1] SET THEORY 21

INDUCTION

1.50Prove: 2+ 4 + 6 +···+ 2 n=n(n+ 1 )

1.51Prove: 1+ 4 + 7 +···+ 3 n− 2 =n(^3 n 2 −^1 )

1.52Prove: 1^2 + 22 + 32 +···+n^2 =n(n+^1 )( 62 n+^1 )

1.53Prove: 11 · 3 + 31 · 5 + 51 · 7 +···+( 2 n− 1 )(^12 n+ 1 )= 2 nn+ 1

1.54Prove: 11 · 5 + 51 · 9 + 9 ·^113 +···+( 4 n− 3 )(^14 n+ 1 )= 4 nn+ 1

1.55Prove 7n− 2 nis divisible by 5 for alln∈N

1.56Proven^3 − 4 n+6 is divisible by 3 for alln∈N

1.57Use the identity 1+ 2 + 3 +···+n=n(n+ 1 )/2 to prove that

13 + 23 + 33 +···+n^3 =( 1 + 2 + 3 +···+n)^2

Miscellaneous Problems

1.58SupposeN={1, 2, 3, ...} is the universal set, and

A={n|n≤ 6 },B={n| 4 ≤n≤ 9 },C={ 1 , 3 , 5 , 7 , 9 },D={ 2 , 3 , 5 , 7 , 8 }.

Find: (a)A⊕B; (b)B⊕C; (c)A∩(B⊕D); (d)(A∩B)⊕(A∩D).

1.59Prove the following properties of the symmetric difference:

(a) (A⊕B)⊕C=A⊕(B⊕C)(Associative Law).

(b) A⊕B=B⊕A(Commutative Law).

(c) IfA⊕B=A⊕C,thenB=C(CancellationLaw).

(d) A∩(B⊕C)=(A∩B)⊕(A∩C)(Distributive Law).

1.60Considermnonempty distinct setsA 1 ,A 2 ,...,Amin a universal setU. Prove:

(a) There are 2mfundamental products of themsets.

(b) Any two fundamental products are disjoint.

(c) Uis the union of all the fundamental products.

Answers to Supplementary Problems

1.26B=C=E=F,A=D=G=H.

1.27A ={a, e, i, o, u}, B = D ={l, i, t, e},

C={a, b, c, d, e}.

1.28(a)CandE; (b)DandE; (c)A, B, andD;(d) None.

1.29(a)A∩B={ 2 , 5 },A∩C={ 1 , 5 };

(b)A∪B={ 1 , 2 , 5 , 6 , 7 },B∪C={ 1 , 2 , 3 , 5 , 7 , 9 };

(c)AC={3, 4, 7, 8, 9}, CC={2, 4, 6, 8};

(d)A\B={1, 6},A\C={2, 6};

(e)A⊕B={ 1 , 6 , 7 },A⊕C={ 2 , 3 , 6 , 7 , 9 };

(f)(A∪C)\B={ 1 , 3 , 6 , 9 },(B⊕C)\A={ 3 , 9 }.

1.33A∪B=(AC∩BC)C.

1.34 See Fig. 1-10.

1.35 (a)(A∩B∩C)∪(A∩B∩CC)∪(A∩BC∩C)

(b)(AC∩B∩CC)∪(AC∩B∩C)∪(AC∩BC∩C)

(c)(A∩B∩C)∪(A∩B∩CC)∪(A∩BC∩C)

∪(AC∩B∩CC)∪(A∩BC∩CC)

1.36 The three premises yield the Venn diagram in

Fig. 1-11(a). (a) and (b) are valid, but (c) is not valid.

1.37 (a)A=(BC∪A)∩(A∪B)

(b)(A∪B)∩(AC∪B)∩(A∪BC)∩(AC∪BC)=∅

1.39 (a) Infinite; (b) finite; (c) infinite; (d) finite.