Explanation Proof: We know that the formula is true for n = 2 , i . e . | A 1 ∪ A 2 | = | A 1 | + | A 2 | − | A 1 ∩ A 2 | . Suppose it is true for ( n − 1 ) sets, which means: | ∪ i = 1 n − 1 A i | = ∑ k = 1 n − 1 ∑ i ≤ i 1 < i 2 < ... i k ≤ n − 1 ( − 1 ) k + 1 | ∩ j = 1 k A i j | Let us consider now the case for n sets. Suppose B n = ∪ i = 1 n − 1 A i , then | ∪ i = 1 n A i | = | B n ∪ A n | = | B n | + | A n | − | B n ∩ A n | Whereas | B n ∩ A n | = | ( A 1 ∪ A 2 ∪ .... ∪ A n − 1 ) ∩ A n | = ∪ i = 1 n − 1 ( A i ∩ A n ) , the last step follows from set relations. Using the assumption for union of ( n − 1 ) sets, we get | B n ∩ A n | = ∑ k = 1 n − 1 ∑ i ≤ i 1 < i 2 <

8th Edition

ISBN: 9781260521337

Author: ROSEN

Publisher: MCG

See similar textbooks

Videos

Question

Chapter 8.5, Problem 24E

To determine

To prove:

The principle of inclusion-exclusion using mathematical induction.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 8.5, Problem 23E

Chapter 8.5, Problem 25E

Students have asked these similar questions

please work out more details give the solution.

Problem #5 Suppose you flip a two sided fair coin ("heads" or "tails") 8 total times. a). How many ways result in 6 tails and 2 heads? b). How many ways result in 2 tails and 6 heads? c). Compare your answers to part (a) and (b) and explain in a few sentences why the comparison makes sense.

Burger Dome sells hamburgers, cheeseburgers, french fries, soft drinks, and milk shakes, as well as a limited number of specialty items and dessert selections. Although Burger Dome would like to serve each customer immediately, at times more customers arrive than can be handled by the Burger Dome food service staff. Thus, customers wait in line to place and receive their orders. Burger Dome analyzed data on customer arrivals and concluded that the arrival rate is 30 customers per hour. Burger Dome also studied the order-filling process and found that a single employee can process an average of 44 customer orders per hour. Burger Dome is concerned that the methods currently used to serve customers are resulting in excessive waiting times and a possible loss of sales. Management wants to conduct a waiting line study to help determine the best approach to reduce waiting times and improve service. Suppose Burger Dome establishes two servers but arranges the restaurant layout so that an…

Chapter 8 Solutions

DISCRETE MATHEMATICS+ITS APPL. (LL)-W/A

Ch. 8.1 - Use mathematical induction to verify the formula...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - A vending machine dispensing books of stamps...Ch. 8.1 - A country uses as currency coins with values of 1...Ch. 8.1 - How many was are there to pay a bill of 17 pesos...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

To prove: The principle of inclusion-exclusion using mathematical induction.

Solution Summary: The author explains the principle of inclusion-exclusion using mathematical induction.

Videos

To prove: The principle of inclusion-exclusion using mathematical induction.

Want to see the full answer?

Chapter 8 Solutions

To prove:

The principle of inclusion-exclusion using mathematical induction.