# Mathematical Induction question

#### William

##### New member
A question I'm working on and my math book doesn't clarify the answer well enough for me to follow. I'm having some issues at getting the math symbols to work correctly so bare with me!

Prove by mathematical induction that if A1, A2, ...., An and B are any n + 1 sets, then: Base step = n = 1 so P(1): A1 ∩ B = A1 ∩ B
Induction Step: LHS of P(k+1):

Substitute (k+1) for all N. Working LHS: (where {k U i = 1}Ai is the union from 1 to n of Ak)
=(({k U i = 1}Ai​) U Ak+1) ∩ B; then distribute:
=(({k U i = 1}(Ai​ ∩ B) U ( Ak+1 ∩ B)

then this is where I get stuck. I feel there is about one or two more steps but I can't seem to grasp it. Any suggestions?

#### Plato

##### Well-known member
MHB Math Helper
Prove by mathematical induction that if A1, A2, ...., An and B are any n + 1 sets, then:
View attachment 37
$\bigcup\limits_{k = 1}^{N + 1} {\left( {A_k \cap B} \right)} = \bigcup\limits_{k = 1}^N {\left( {A_k \cap B} \right)} \cup \left( {A_{N + 1} \cap B} \right)$
$= \left[ {\left( {\bigcup\limits_{k = 1}^{N } { {A_k }} } \right) \cap B} \right] \cup \left( {A_{N+1 } \cap B} \right)$
$= \left[ {\left( {\bigcup\limits_{k = 1}^{N } { {A_k } } } \right) \cup A_{N+1 } } \right] \cap B$.

Can you finish?

Last edited:

#### William

##### New member
Wouldn't it just be:

= {k+1 U i = 1 Ai U Ak+1) ∩ B
= {k+1 U i = 1} (Ai ∩ B)

#### Plato

##### Well-known member
MHB Math Helper
Wouldn't it just be:
= {k+1 U i = 1 Ai U Ak+1) ∩ B
= {k+1 U i = 1} (Ai ∩ B)
Do you see that $\left( {\bigcup\limits_{k = 1}^N {A_k } } \right) \cup A_{N + 1} = \bigcup\limits_{k = 1}^{N + 1} {A_k } ~?$

I started with $P(N)$ being true.
Then looked at the expansion of $P(N+1)$.

• William

#### William

##### New member
Yes, I sort of see how they are equal. It's still not crystal clear to me yet though.

#### Plato

##### Well-known member
MHB Math Helper
Yes, I sort of see how they are equal. It's still not crystal clear to me yet though.
Can you see that $\sum\limits_{k = 1}^{n + 1} {a_k } = a_1 + a_2 + \cdots + a_{n + 1} = \left( {a_1 + a_2 + \cdots + a_n } \right) + a_{n + 1} ~?$

If so $\sum\limits_{k = 1}^{n + 1} {a_k } =\sum\limits_{k = 1}^{n} {a_k }+ a_{n + 1}$

Yes, I see that.

#### Plato

##### Well-known member
MHB Math Helper
Yes, I see that.
Then what are you missing in understanding the induction proof?