Discrete Mathematics for Computer Science

54 CHAPTER 1 Sets, Proof Templates, and Induction

Each of these is also a subset of X U (b). Now, create n more subsets of X U [b):

S, U {b}, S 2 U 1b} ... , Sn U (b}

Obviously, each Si U {b} is also a subset of X U {b}. Now, we have a list of 2n subsets of

X U {b}:

S1, S2,..., Sn, S 1 U {b), S2 U {b},..., Sn U (b}

Show that (i) no subset of X U (b} appears twice in this list and (ii) every subset of X U {b}

appears in this list.

Once these two assertions have been proven, it will follow that these 2n subsets are all

the subsets of X U {b), so X U {b} has 2n subsets. We prove (ii) and leave the proof of (i)

as Exercise 32 in Section 1.9 for the reader.

To prove (ii), follow Template 1.1 (Element Membership in a Set). Let S be an ar-

bitrary subset of X U {b}. If b 0 S, then S C X, so S is one of the Si's. If b e S, let

S' = S - 1b}. Then, S' C X, so S' is some Si, and then S is Si U (b} (for the same i). In

either case, S is on the list. U

Proof of Theorem 2. Let T = {n c N : for every finite set X with n elements, P'(X) has

2" subsets}. We will prove by induction that T = N.

(Base step) Let no = 0. The only set with zero elements is 0. The only subset of 0 is 0,

so P(0) has I = 20 elements. Therefore, (^0) E T.
(Inductive step) Let n > 0. Show that if n E T, then n + 1 E T. Using the hypothesis
that every set with n elements has 2' subsets, prove that every set with n ± 1 elements
has 2n"+ subsets. Let X be an arbitrary set with n + 1 elements. Pick one element y E X,
and let Z = X - (y}. Then, Z has n elements, so by the hypothesis, Z has 2' subsets. By

Lemma 1, X = Z U [y} has 2.2" = 2n+1 subsets. Therefore, n + 1 E T.

By the Principle of Mathematical Induction, T = N. U

1.75 Application: Geometric Series

A finite geometric series, or just a geometric series, is the sum of terms of the form a. r

where a, r E R - (0), r : 1, and 0 < i < n. For example,

n

Sari =a +a.r +a.r2 +.+.a

rn

i=0

is a geometric series. As another example, let a = 5, r = -3, and n = 5, giving

5 + 5. (-3) + 5. (-3)2 + 5. (-3)3 + 5. (-3)4 5.(-3)5

as a geometric series. Although

20

L 3. 2'

i=5