# 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 \$\displaystyle n=2\$ we need to show \$\displaystyle (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 \$\displaystyle (A_1\cap ... \cap A_n) \cup B = (A_1 \cup B)\cap ... \cap (A_n \cup B)\$.

Then if we have \$\displaystyle (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 \$\displaystyle n=2\$):
\$\displaystyle [(A_1\cap ... \cap A_n) \cup B] \cap (A_{n+1} \cup B)\$
Now apply inductive step:
\$\displaystyle (A_1\cup B)\cap ... \cap (A_{n+1} \cup B)\$
And that completes induction.