0
$\begingroup$

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.2012-10-30

1 Answers 1