Bonferroni Inequalities

Let $f(k,m)$ be the number of ways to choose $m$ out of $k$ objects, without choosing the last one.

By inclusion-exclusion, $f(k,m)=\binom{k}{m}-f(k,m-1)=(-1)^mP_{m+1}$.

But $f(k,m)$ is obviously $\binom{k-1}{m}$. Therefore $P_{m+1}=(-1)^m\binom{k-1}{m}$.

$$\begin{align} \require{cancel} &1-\binom{k}{1} + \binom{k}{2} - \cdots (-1)^m\binom{k}{m}\\ &=1+\sum_{r=1}^{m}(-1)^k\binom kr\\ &=1+\sum_{r=1}^{m}(-1)^r\left[\binom {k-1}{r-1}+\binom {k-1}r\right]\\ &=\color{lightgrey}{\cancel{1}-\left[\cancel{{\binom {k-1}0}}+\bcancel{\binom {k-1}1}\right] +\left[\bcancel{\binom {k-1}1}+\cancel{\binom {k-1}2}\right] -\left[\cancel{\binom {k-1}2}+\bcancel{\binom {k-1}3}\right] +\cdots +(-1)^m\left[\bcancel{\binom {k-1}{m-1}}+\binom {k-1}m\right]}\\ &=(-1)^m\binom {k-1}m\qquad \blacksquare\\ \end{align}$$

Alternatively: $$\begin{align} &1-\binom{k}{1} + \binom{k}{2} - \cdots (-1)^m\binom{k}{m}\\ &=1+\sum_{r=1}^{m}(-1)^k\binom kr\\ &=1+\sum_{r=1}^{m}(-1)^r\left[\binom {k-1}{r-1}+\binom {k-1}r\right]\\ &=1+\sum_{r=0}^{m-1}(-1)^{r+1}\binom {k-1}{r}+\sum_{r=1}^{m}(-1)^r\binom {k-1}r\\ &=1\color{blue}{-\sum_{r=0}^{m-1}(-1)^r\binom {k-1}{r}} \color{green}{+\sum_{r=1}^{m}(-1)^r\binom {k-1}r}\\ &=\cancel{1}\color{blue}{-\cancel{1}-\bcancel{\sum_{r=1}^{m-1}(-1)^r\binom {k-1}{r}}} \color{green}{+\bcancel{\sum_{r=1}^{m-1}(-1)^r\binom {k-1}r}+(-1)^m\binom {k-1}m}\\ &=(-1)^m\binom {k-1}m\qquad \blacksquare\\ \end{align}$$