How do I prove the sum/product rule in combinatorics? I think I should use induction but how do I start?
What should be the base case and the … erm induction step?
Sum rule:
suppose that an operation can be broken down into two tasks $A$ and $B$
if there are $N_a$ ways to do task $A$ and $N_b$ ways to do task $B$, the number of ways to do the operation is $N_a + N_b$
for product rule its the same only that its $N_aN_b$
Best Answer
I assume all sets are finite, though the argument below can be extended to deal with the infinite case.
$\bullet$ The sume rule essentially states that $|A \cup B| = |A| + |B| - |A \cap B|$. How do you show that if $A \cap B = \emptyset$, then $|A \cup B| = |A| + |B|$?
This is accomplished by simply noticing that if $A = \{x_1, \dots , x_n\}$ and $B = \{y_1, \dots , y_m\}$, then $A \cup B = \{x_1, \dots , x_n, y_1, \dots , y_m\}$. Note also that $x_i \neq y_j$ for any pair $(i,j)$. Hence, $A \cup B$ is a set with $n + m$ distinct elements, and so $|A \cup B| = n + m = |A| + |B|$.
What if $A \cap B \neq \emptyset$? Then, write $A \cup B = (A^c \cap B) \cup (A \cap B) \cap (B^c \cap A)$ which is a union of disjoint sets and apply the above argument to these disjoint sets.
$\bullet$ The product rule essentially states that $|A \times B| = |A| |B|$. This follows essentially as before. Write out $A \times B$, and find the cardinality of the set.
Once you establish the sum-rule and product-rule for two sets, use induction for the general case.