# Prove sum/product rule

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$

-

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

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9391761422157288, "perplexity_flag": "head"}