Basics of Counting: Induction Proof (Product Rule)

The question:

***Use mathematical induction to prove the product rule for m tasks from the product rule for two tasks.***

**The Product Rule for counting states:** **The Product Rule: Suppose that a procedure can be broken down into a sequence of two tasks. If there are n**_{1} ways to do the first task and for each of these ways of doing the first task, there are n_{2} ways to do the second task, then there are n_{1}n_{2} ways to do the procedure.

Base Case: I choose P(m) = 4, which is the product rule for two tasks.

Induction: I am using P(m) and consider P(m+1). My inductive hypothesis (guessing here) can be **n**_{1}* **n**_{2} * ...*n_{m} * n_{m+1, }How do I prove this further in words or math computation? Thanks for any help.

Re: Basics of Counting: Induction Proof (Product Rule)

Quote:

Originally Posted by

**inflames098** The question:

***Use mathematical induction to prove the product rule for m tasks from the product rule for two tasks.***

**The Product Rule for counting states:** **The Product Rule: Suppose that a procedure can be broken down into a sequence of two tasks. If there are n**_{1} ways to do the first task and for each of these ways of doing the first task, there are n_{2} ways to do the second task, then there are n_{1}n_{2} ways to do the procedure.

Base Case: I choose P(m) = 4, which is the product rule for two tasks.

Where in the world did "4" come from? Your base case is two tasks: the first task can be done in $\displaystyle n_1$ ways and the second task can be done in $\displaystyle n_2$ ways, there are $\displaystyle n_1n_2$ ways in which both tasks can be done.

Induction: I am using P(m) and consider P(m+1). My inductive hypothesis (guessing here) can be **n**_{1}* **n**_{2} * ...*n_{m} * n_{m+1, [/quote]
Okay, assuming P(m) is "there are [tex]n_1[tex] ways to do task 1, $\displaystyle n_2$ ways to do task 2, ..., $\displaystyle n_m$ to do task m, then there are $\displaystyle n_1n_2\cdot\cdot\cdot n_m$ ways to do all m tasks. } Quote:

How do I prove this further in words or math computation? Thanks for any help.

Let "task A" be "do all m tasks". The induction hypothesis, above, says there are $\displaystyle n_1n_2\cdot\cdot\cdot n_m$ ways to do task A. If there are then $\displaystyle n_1$ ways to do task m+1, what does the basis "counting principle" say about the number of ways to do task A and task m+1?