Need help in proving combinatorial identity involving unions, intersections and complements over sets using induction

Question

The identity is the following: $$\left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C = \bigcup_{i=1}^n (A_i^C\cap B_i^C)$$

I must use induction to prove it.

1. Base. Ok, I think I got how to prove base case:

n = 1 $$(A \cup B)^c = (A^c\cap B^c)$$ if x ∈ A U B => x ⊄ (A U B)'

if x ∈ A => x ⊄ A'

if x ∈ A => x ⊄ B'

if x ⊄ A' and x ⊄ B' => x ⊄ (A' Intersection B')

Seems it works.

2. IH

Here I am confused. As I know for induction you need to assume true for n and prove for n+1.

So, I should have the following

$$\left(\bigcap_{i=1}^{n+1} (A_i\cup B_i)\right)^C = \left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C \cap (A_{n+1}\cup B_{n+1})^c$$

And... where should I go now? I am totally confused how to proceed further. I would be thankful for any help.

Answer 1

Since Hagen von Eitzen already gave a hint to solve it by induction, I'll give a direct way, which might be instructive anyway. You want to prove that $$\left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C = \bigcup_{i=1}^n (A_i^C\cap B_i^C)$$

Notice that:

$$x \in \left(\bigcap_{i=1}^n (A_i\cup B_i)\right)^C \iff x \not\in \bigcap_{i=1}^n (A_i\cup B_i) \iff \exists \ i \ : x \not\in A_i \cup B_i \iff \\ \iff \exists \ i \ : x \in A_i^C \cap B_i^C \iff x \in \bigcup_{i=1}^n (A_i^C\cap B_i^C) \qquad \square$$

Answer 2

Use that $\bigcap_{i=1}^{n+1} X_i = X_{n+1}\cap \bigcap_{i=1}^{n} X_i$ and $\bigcup_{i=1}^{n+1} X_i = X_{n+1}\cup \bigcup_{i=1}^{n} X_i$. Then the case $n+1$ follows readily from $n$ and $2$.