# Need help proving!! Mathematical Induction

• Oct 14th 2008, 12:39 PM
Saint22
Need help proving!! Mathematical Induction
Hey I'm struggling in Discrete Math, could anyone help me solve this proof?

Prove that A1, A2, . . . ., An and B are sets, then (A1 ∩ A2 ∩ . . . ∩An) U B = (A1 U B) ∩ (A2 U B) ∩ . . . ∩(An U B).

This comes from the Induction and Recursion chapter of Mathematical Induction.
• Oct 15th 2008, 06:38 PM
ThePerfectHacker
Quote:

Originally Posted by Saint22
Hey I'm struggling in Discrete Math, could anyone help me solve this proof?

Prove that A1, A2, . . . ., An and B are sets, then (A1 ∩ A2 ∩ . . . ∩An) U B = (A1 U B) ∩ (A2 U B) ∩ . . . ∩(An U B).

This comes from the Induction and Recursion chapter of Mathematical Induction.

Prove it by induction for $n=2$ we need to show $(A_1\cap A_2) \cup B = (A_1 \cup B) \cap (A_2\cup B)$.
This case is proven individually.

If it is for $(A_1\cap ... \cap A_n) \cup B = (A_1 \cup B)\cap ... \cap (A_n \cup B)$.

Then if we have $(A_1\cap ... \cap A_n \cap A_{n+1})\cup B = [(A_1\cap ... \cap A_n) \cap A_{n+1}] \cup B$
And this gives, (as in the case $n=2$):
$[(A_1\cap ... \cap A_n) \cup B] \cap (A_{n+1} \cup B)$
Now apply inductive step:
$(A_1\cup B)\cap ... \cap (A_{n+1} \cup B)$
And that completes induction.