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.

I'm not exactly sure how to do this using mathematical induction. Thanks for the help.

I'm trying to prove that the product rule is valid for some number of tasks $m$, such that $m$ is greater than two using induction and the product rule for two tasks as a given.

The product rule for a two-tasks procedure states that, there are $n_1n_2$ ways to do a procedure, when 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

share|improve this question
3  
I can think of several possible variants, so you need to state exactly the product rule that you’re trying to prove. –  Brian M. Scott Feb 22 '13 at 12:30
    
what is the product rule for $m$ tasks? –  Emanuele Paolini Feb 22 '13 at 12:30
add comment

2 Answers

up vote 4 down vote accepted

Let $P(m)$ be the following statement:

If there are $n_k$ ways to perform task $T_k$ for $k=1,\dots,m$, then there are $n_1n_2\dots n_m$ ways to perform all $m$ tasks.

$P(1)$ is obvious, you’re given that $P(2)$ is true, and you’re to prove that $P(m)$ is true for all positive integers $m$. This is a natural setting for a proof by induction, and you’ve been handed the basis step for free. Thus, all you have to do is prove the induction step: if $P(m)$ is true, then so is $P(m+1)$. In words, if the product rule holds for $m$ tasks, then it holds for $m+1$ tasks. So assume that $P(m)$ is true for some $m\ge 2$; we’ll try to prove $P(m+1)$.

To that end suppose that we have $m+1$ tasks, and that task $T_k$ can be performed in $n_k$ ways, where $k=1,\dots,m+1$. We’d like to show that the entire set of $m+1$ tasks can be performed in $n_1n_2\dots n_mn_{m+1}$ ways.

HINT: Think of the combination of tasks $T_1$ through $T_m$ as a single very large task; call that task $T$. To complete tasks $T_1$ through $T_{m+1}$ you must complete the two tasks $T$ and $T_{m+1}$. You’re assuming that the product rule is true for $m$ tasks, so how many ways are there to perform task $T$? How many ways are there to perform the pair of tasks $T$ and $T_{m+1}$?

share|improve this answer
add comment

Hint: Suppose you know that for a $(k-1)$-task procedure, there are $n_1 n_2 \cdots n_{k-1}$ ways to do the procedure. And that there are $n_k$ ways to do a $k$-th task. Then what does the product for two-task procedures tell you for the number of ways to do the two-task procedure: (1) perform the $(k-1)$-task procedure; (2) then perform the $k$-th task.

share|improve this answer
add comment

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.