Use mathematical induction to prove a statement

Question

Use mathematical induction to prove that:

$$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$

Answer 1

Hint. One may recall that $$ A \cap (B \cup C)=(A \cap B) \cup (A \cap C) $$ This is a key point in the inductive step.

Answer 2

Base case: For $n=1$, this is trivially true since both sides give the same thing.

Assumed true case:

$$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$

Inductive step:

We use distributive rule to break it up first and then use the associativity of union of sets after application of inductive hypothesis.

$$\begin{align}A\cap\left(\bigcup_{i=1}^{n+1}B_i\right)&=\left(A\cap\left(\bigcup_{i=1}^nB_i\right)\right)\cup\left(A\cap B_{n+1}\right)\\ &=\left(\bigcup_{i=1}^n(A\cap B_i)\right)\cup(A\cap B_{n+1})\\&=\bigcup_{i=1}^{n+1}(A\cap B_i)\end{align}$$

Answer 3

Start with the base step: n = 1, $$A \cap \left(\bigcup^1_{i=1} B_i\right)=$$ $$A \cap B_1=$$ $$\bigcup^1_{i=1} \left(A \cap B_i\right)$$ which holds.

Now consider that the inductive hypothesis is true, that is, the proposition holds true for an integer $n = k$,

$$\color{blue}{A \cap \left(\bigcup^k_{i=1} B_i\right)}=\color{green}{\bigcup^k_{i=1} (A \cap B_i)}$$

Then prove the proposition for an integer $n = k + 1$,

$$A \cap \left(\bigcup^{k+1}_{i=1} B_i\right)=$$ $$A \cap \left(\left(\bigcup^{k}_{i=1} B_i\right) \cup B_{k+1}\right)=$$ Let us call the set $\cup^{k}_{i=1} B_i$ as $X$ for a moment, $$A \cap (X \cup B_{k+1})=$$

Applying the distributive rule of sets to A over X and $B_{k+1}$ gives

$$(A \cap X) \cup (A \cap B_{k+1})$$

Substituting the original value of X in the equation yields

$$\left(\color{blue}{A \cap \left(\bigcup^{k}_{i=1} B_i\right)}\right) \cup (A \cap B_{k+1})=$$

Substituting the inductive hypothesis in the equation gives

$$\color{green}{\bigcup^k_{i=1} (A \cap B_i)} \cup (A \cap B_{k+1})=$$ $$\bigcup^{k+1}_{i=1} (A \cap B_i)$$ QED