# Basics of Counting: Induction Proof (Product Rule)

• Nov 6th 2012, 04:26 PM
inflames098
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 n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 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 n1* n2 * ...*nm * nm+1,

How do I prove this further in words or math computation? Thanks for any help.
• Nov 6th 2012, 05:46 PM
HallsofIvy
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 n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 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 $n_1$ ways and the second task can be done in $n_2$ ways, there are $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 n1* n2 * ...*nm * nm+1, [/quote]
Okay, assuming P(m) is "there are [tex]n_1[tex] ways to do task 1, $n_2$ ways to do task 2, ..., $n_m$ to do task m, then there are $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 $n_1n_2\cdot\cdot\cdot n_m$ ways to do task A. If there are then $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?