# Fundamental Theorem of Counting: invalid proof?

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.

• This proof is valid, and you can simply treat completing task #$1$,..., task #$k-1$ as one single task altogether. – Clement Yung Dec 26 '19 at 13:20
• What does exercise 1.15 say? – Angina Seng Dec 26 '19 at 13:21
• @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. – 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 ...