Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
2  
Once the question is precisely formulated, the answer is clear, and probably does not require proof. But one can write a formal proof. It amounts to showing that $x+(y+1)=(x+y)+1$ and $x(y+1)=xy+y$, which are respectively part of the definition of sum and product. –  André Nicolas Oct 30 '12 at 17:14

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.