Math Induction proof union and intersections

Question

I'm totally new to Math Induction. I have a question on using Math Induction proof with union and intersections.

Here's the initial problem: Prove that, for if C, D1, D2, …, Dn are n + 1 sets, that

$$C\bigcap(\bigcup_{i=1}^nD_i)=\bigcup_{i=1}^n(C \bigcap D_i)$$

Basis step.

Prove P(1).

$$P(1):C \bigcap D_i = C \bigcap D_i$$

Induction step

Write out P(k) by replacing “n” with “k” in the original equation.

$$P(k): C\bigcap(\bigcup_{i=1}^kD_i)=\bigcup_{i=1}^k(C \bigcap D_i)$$

Proof

Using the assumption that P(k) is true, add k+1 on the left-hand side and replace “k” with “k+1” to the right-hand side.

$$P(k+1): C\bigcap(\bigcup_{i=1}^{k+1}D_i)=C \bigcap((\bigcup_{i=1}^kD_i)\bigcup D_{k+1})$$

RHS (associative properties - change the grouping )

$$=C \bigcap(\bigcup_{i=1}^kD_i)\bigcup D_{k+1})$$

Question: are we just replacing the k with k+1? if so why? or am I totally off?

RHS of P(k+1)

$$=C \bigcap(\bigcup_{i=1}^{k+1}D_i)$$

Answer 1

We want to prove that: $$ C \cap \left( \bigcup_{i=1}^{n} D_i \right) = \bigcup_{i=1}^{n} (C \cap D_i) $$

The first step is to prove that it holds for some value of $n$. It is obvious that the equality is verified for $n=1$, so we can proceed. We assume that the equality holds for some $n$, and we prove that this implies that the equation holds for $n+1$. Pay attention to this step: we are proving that, if the equality holds for $n$, then it also holds for $n+1$. Since we know that $n=1$ is true, this will lead us to conclude that $n=2$ holds. But then, $n=3$ holds, and so on. This is how proof by induction works. So we suppose that the equality is verified for some $n$, and we want to prove that this implies: $$ C \cap \left( \bigcup_{i=1}^{n+1} D_i \right) = \bigcup_{i=1}^{n+1} (C \cap D_i) $$ Note that the LHS can be rewritten as: $$ C \cap \left(\left( \bigcup_{i=1}^{n} D_i \right)\cup D_{n+1}\right) $$ By the distributive law, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. Thus, we obtain: $$ C \cap \left(\left( \bigcup_{i=1}^{n} D_i \right) \cup D_{n+1}\right) = \left(C \cap \left( \bigcup_{i=1}^{n} D_i \right)\right) \cup (C \cap D_{n+1}) $$ But, using the inductive assumption, this is the same as: $$ \left( \bigcup_{i=1}^{n} (C \cap D_i) \right) \, \cup \, (C \cap D_{n+1}) $$ which is equal to $$ \bigcup_{i=1}^{n+1} (C \cap D_i) $$ as we wanted to prove. Thus, the proof by induction is complete.