Professor X gives the following homework problem from Mathematics For Computer Science (note: this is not from a course at CUHK, as the link might suggest):
Prove the following probabilistic inequality, referred to as the Union Bound. Let $A_1,A_2,...A_n,...$ be events. Then $$Pr\left[\bigcup\limits_{n\in N} A_n\right] \leq \sum\limits_{n \in N}Pr[A_n].$$ Hint: Replace the $A_n$'s by pairwise disjoint events and use the Sum Rule.
However, Professor X instructs his students to follow a different hint instead of the one given in the original problem. He writes:
Better hint: use induction; no need for the Sum Rule.
I don't see how induction works here. I presume he means that, for the induction, one should use a proposition something like the following,
$$P(k): Pr\left[\bigcup\limits_{n=1}^{k} A_n\right] \leq \sum\limits_{n=1}^{k} Pr[A_n]$$
then argue that $P(1)$ holds as a base case, and that $P(k)\rightarrow P(k+1)$, which implies that $P(n)$ holds for any $n\in N$ by the principle of mathematical induction.
This argument would be insufficient, however. We are not trying to prove that $P(n)$ holds for any $n \in N$. Rather, we are trying to establish $P(\infty)$:
$$Pr\left[\bigcup\limits_{n=1}^{\infty} A_n \right] \leq \sum\limits_{n=1}^{\infty}Pr[A_n].$$ Since induction cannot establish $P(\infty)$, induction is insufficient to prove the result.
Do others agree? Have I correctly interpreted the notation of the original problem as equivalent to $P(\infty)$? Is there some other inductive hypothesis that would make induction a valid approach for this?
Note: transfinite induction is not available in this course -- not that I'm sure it would help anyway.
I disagree with the comments and agree with your claim that proof by induction is insufficient here (and in fact I have penalized students in the past for attempting to argue this way). As Greg Martin points out, induction allows you to deduce $$ Pr\left[\bigcup_{n=1}^kA_n\right]\le\sum_{n=1}^kPr[A_n]\le\sum_{n=1}^\infty Pr[A_n]. $$ To deduce the result from here, we need to know that $Pr\left[\bigcup_{n=1}^kA_n\right]\to Pr\left[\bigcup_{n\in\mathbb N}A_n\right]$ as $k\to\infty$. But this is not immediate, and the typical way to prove this is to use the original hint, i.e. replace the $A_n$'s with pairwise disjoint events and use countable additivity. Therefore you have gained nothing by using induction.