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

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

-
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

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}$?

-

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.

-