Discrete Mathematics for Computer Science

The Principle of Inclusion-Exclusion 37 The number of elements in the union of two finite sets is the sum of the number of eleme ...

38 CHAPTER 1 Sets, Proof Templates, and Induction The decomposition of two sets into disjoint subsets is fairly obvious. For thr ...

The Principle of Inclusion-Exclusion 39 L E U 2499 899 101 C Figure 1.15 Counting liberals and children. The Principle of Inclus ...

40 CHAPTER 1 Sets, Proof Templates, and Induction and I D 2 n D 3 n D 5 1 = I D301 = 1,000,000 Now, by the Principle of Inclusio ...

The Principle of Inclusion-Exclusion 41 left to be given to G 3 .There is one way to return this hat to G 3 .Therefore, IH, n/H2 ...

42 CHAPTER 1 Sets, Proof Templates, and Induction rn Exercises In a class of 35 students who are either biology majors or have ...

Exercises 43 How many fast food outlets are there near campus? At the beginning of the semester, an instructor of a music appre ...

44 CHAPTER 1 Sets, Proof Templates, and Induction The language department wanted to know how many of the 2000 students at the u ...

Mathematical Induction 45 Find the number of integers between 1 and 1000, including 1 and 1000, that are not divisible by any o ...

46 CHAPTER 1 Sets, Proof Templates, and Induction Selection Sort Steps Initial order (^2 1 4 3 5) Step One 2 1 4 3 5 Identify sm ...

Mathematical Induction 47 It is not obvious that this formula is true for all n. It is true for n = 0, 1, 2, 3, and 4, but as ye ...

48 CHAPTER 1 Sets, Proof Templates, and Induction Since we have proved that the formula is true for n = 0 and is true for n + 1 ...

Mathematical Induction 49 In the proof of Theorem 1, T was defined to be the set of all natural numbers for which the formula n ...

50 CHAPTER 1 Sets, Proof Templates, and Induction The examples that follow show the power of this proof method. Some of the ineq ...

Mathematical Induction 51 (Base step) Show that 4 e T. Since 4! = 24 and 42 = 16, we have 4! > 42, so 4 E T. (Inductive step) ...

52 CHAPTER 1 Sets, Proof Templates, and Induction The Fibonacci numbers were defined by Leonardo of Pisa, filius (son of) Bonacc ...

Mathematical Induction 53 (Inductive step) Let n > no. Show that if n E T, then n + 1 e T. Since n > 1, n + 1 > Assume ...

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 [ ...

Mathematical Induction 55 does not look like a geometric series, it is easy to transform this finite geometric series into a mor ...

56 CHAPTER 1 Sets, Proof Templates, and Induction Corollary 1 gives a formula for finding the sum of a finite geometric series. ...