# Induction implies P(n) for any n in Z, not P(\infty) - an example

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 believe you're right that induction by itself does not establish the infinite-union statement. However, if the induction is carried out, note that you get $$Pr\left[\bigcup\limits_{n=1}^{k} A_n\right] \leq \sum\limits_{n=1}^{k} Pr[A_n] \leq \sum\limits_{n=1}^{\infty}Pr[A_n]$$ for every $k\in\Bbb N$; and then you can take the limit as $k\to\infty$ (the right-hand side no longer depends on $k$). – Greg Martin Oct 6 '16 at 6:19
• Professor X's hint is allright, I fail to see what there is to "challenge" here. – Did Oct 6 '16 at 6:48
• @Did, you believe the hint is ok because the strategy I've outlined does in fact establish the result, or because some other (unspecified) induction strategy establishes the result? – Chad Oct 6 '16 at 6:54
• I know the hint is allright and I object to your choice of words and to the attitude towards X's indications that it seems to reveal. @Greg's comment precisely describes a complete proof based on X's excellent indication. – Did Oct 6 '16 at 6:56
• @Did Thanks for clarifying. No bad attitude intended - just trying to understand. – Chad Oct 6 '16 at 7:04

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.
• do you mean as $k\rightarrow \infty$? – Chad Oct 6 '16 at 17:38