Ytukyg

I am trying to use mathematical induction to prove the multiplication rule:

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

In attempting to prove this, I used the advice from Brian M. Scott's answer in this thread.

Proof

Let $P(m)$ represent the above statement.

$P(1)$ is obviously true, since, if there are $n_1$ ways to perform task $T_1$, then there are $n_1$ ways to perform the single task.

$P(2)$ is assumed to be true by the statement.

Now assume that $P(m)$ is true for some $m ge 2$.

To prove that $P(m + 1)$ is true, we start with the two tasks $T$ and $T_k$, where $T$ represents all tasks $T_1, T_2, dots , T_m$, and $k = m + 1$. Using the induction hypothesis, we have that there are $n_1 n_2 dots n_m$ ways to perform task $T$. And since there are $n_k$ ways to perform task $T_k$, where $k = m + 1$, and since $P(2) = n_1 n_2$ ways to perform two tasks, we can conclude that there are $(n_1 n_2 dots n_m)(n_k) = n_1 n_2 dots n_m n_{m + 1}$ ways to perform $m + 1$ tasks (task $T$ and $T_k$, $k = m + 1$, together).

I would greatly appreciate it if people could please take the time to review my proof for correctness.

I think this proof is correct, but I feel like sometimes you are using the same variable in multiple different ways. Therefore, I would try to reword your last paragraph into something more natural, like this:

Assume $P(m)$ for some $m geq 2$. Now, for the purpose of proving $P(m+1)$, suppose there are a set of tasks $T_i$ such that there are $n_i$ ways to complete each task $T_i$ for $1 leq i leq m+1$. In particular, this means $T_{m+1}$ can be completed in $m+1$ ways. Now, let the task $T$ be the combination of tasks $T_1, T_2, ... T_m$. By $P(m)$, it is known that $T$ can be completed in $n_1n_2...n_m$ ways.

We can now consider the set of all $m+1$ tasks to be the combination of the two tasks $T$ and $T_{m+1}$. By $P(2)$, we know that the number of ways to complete two tasks is the product of the number ways one can complete each task separately. Thus, the number of ways to complete task $T$, then task $T_{m+1}$ is the product of the number of ways to complete task $T$, which is $n_1n_2...n_m$, and the number of ways to complete task $T_{m+1}$, which is $n_{m+1}$. This means that the set of all $m+1$ tasks can be completed in $n_1n_2...n_mn_{m+1}$ ways, which proves $P(m+1)$.

Notice how I wrote out $P(2)$ in words instead of as an equation. This meant I didn't have to reuse the variables $n_1, n_2$, which made the proof less ambiguous. Also, instead of using $k$, I just used $m+1$, which cuts down on the number of variables, making the proof easier to follow.