My textbook, Statistical Inference, Second Edition, by Casella and Berger, provides the following theorem (the Fundamental Theorem of Counting) and accompanying proof:

Theorem 1.2.14 If a job consists of $k$ separate tasks, the $i$th of which can be done in $n_i$ ways, $i = 1, \dots, k$, then the entire job can be done in $n_1 \times n_2 \times \dots \times n_k$ ways.

Proof: It suffices to prove the theorem for $k = 2$ (see Exercise 1.15). The proof is just a matter of careful counting. The first task can be done in $n_1$ ways, and for each of these ways we have $n_2$ choices for the second task. Thus, we can do the job in

$$\underbrace{(1 \times n_2) + (1 \times n_2) + \dots + (1 \times n_2) = n_1 \times n_2}_\text{$n_1$ terms}$$

ways, establishing the theorem for $k = 2$. $\tag*{$\square$}$

Am I correct in thinking that this is not a valid (general) proof of the theorem? It is only a proof for $k = 2$, which, as I understand it, and contrary to what the author says, is not sufficient to prove the theorem.

I would appreciate it if people would please take the time to clarify this.

  • $\begingroup$ This proof is valid, and you can simply treat completing task #$1$,..., task #$k-1$ as one single task altogether. $\endgroup$ – Clement Yung Dec 26 '19 at 13:20
  • 2
    $\begingroup$ What does exercise 1.15 say? $\endgroup$ – Angina Seng Dec 26 '19 at 13:21
  • $\begingroup$ @LordSharktheUnknown I haven't checked (exercises are at the end of the chapter). EDIT: "Finish the proof of Theorem 1.2.14. Use the result established for $k = 2$ as the basis of an induction argument." Haha, okay, that clarifies things. Thanks for that. $\endgroup$ – The Pointer Dec 26 '19 at 13:21

Since the number of tasks is finite, then it is a valid proof. If you have 3 tasks $a,b,c$ then you can see $\{a,b\}$ for example as one task and $c$ as a "second" task. So what you proved for $k=2$ will still work for $3$ and so on ...

It is similar to the idea of induction

  • 1
    $\begingroup$ To make the proof precise one does use induction. $\endgroup$ – Berci Dec 26 '19 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.