For pairwise disjoint sets $A_1,A_2,…,A_n$ how can I prove that: $|A_1 \cup A_2 \cup … \cup A_n|=|A_1|+|A_2|+…+|A_n|$ using induction and the 2-set addition rule?
2-set addition rule: $|A_i \cup A_j|=|A_i| + |A_j|$ if $A_i$ and $A_j$ are disjoint.
I think I should suppose the proposition holds for $P(k)$ for $k\ge 2$, that is:
$$|A_1 \cup A_2 \cup … \cup A_k|=|A_1|+|A_2|+…+|A_k|$$
Our base case is $P(2)$:
$$P(2)=|A_1 \cup A_2|=|A_1|+|A_2|$$
By the 2-set addition principle ($A_1$ and $A_2$ are disjoint).
Now
$$P(k+1) = |A_1 \cup A_2 \cup … \cup A_k \cup A_{k+1}|$$
And $A_{k+1}$ is disjoint with $(A_1 \cup A_2 \cup … \cup A_k)$ since $A_{k+1} \cap (A_1 \cup A_2 \cup … \cup A_k) = (A_{k+1} \cap A_1) \cup (A_{k+1} \cap A_2) \cup…\cup (A_{k+1} \cap A_k) = \emptyset$
So by the 2-set addition rule:
$$|A_1 \cup A_2 \cup … \cup A_k| + |A_{k+1}|=|A_1|+|A_2|+…+|A_k|+|A_{k+1}|$$
Which is what the proposition would conclude for $P(k+1)$ so the original proposition must be true.
My question: is there anything wrong with this proof attempt?
Best Answer
Base case: For $n = 2$, $|A_1∪A_2| = |A_1| + |A_2|$.
Inductive hypothesis: Assume that the statement holds true for some integer $k$, that is $$|A_1∪A_2∪\cdots∪A_k| = |A_1| + |A_2| + \cdots + |A_k|$$
Inductive step: To prove that the statement holds true for $k+1$, we need to prove that $$|A_1∪A_2∪\cdots∪A_{k+1}| = |A_1| + |A_2| + \cdots + |A_k| + |A_{k+1}|$$
By the definition of union, we have $$|A_1∪A_2∪\cdots∪A_{k+1}| = |(A_1∪A_2∪\cdots∪A_k) ∪ A_{k+1}|$$
By the inductive hypothesis we know that $$|A_1∪A_2∪\cdots∪A_k| = |A_1| + |A_2| + \cdots + |A_k|$$
So by the definition of union, $$|(A_1∪A_2∪\cdots ∪A_k) ∪ A_{k+1}| = |A_1| + |A_2| + \cdots + |A_k| + |A_{k+1}|$$
Conclusion: Since the statement holds true for $n = 2$ and for any $k$, it holds true for all positive integers $n$.