3

Let $k$ and $m$ be positive integers with $k>m$. Then the partial sums of $$ 1-\binom{k}{1} + \binom{k}{2} - \cdots (-1)^m\binom{k}{m} $$ has alternating signs.

(The partial sums of the given sum are $P_1=1$, $P_2=1-\binom{k}{1}$, $P_3=1-\binom{k}{1}+\binom{k}{2}$, etc)

I arrived at the above problem while trying to show the follwoing (known as Bonferroni inequalities):

Let $A_1, \ldots, A_n$ be events of a probability space. For a subset $I$ of $\{1,\ldots, n\}$, write $A_I$ to denote $\bigcap_{j\in I}A_j$. Further, denote $\sum_{|I|=i}P(A_I)$ as $\sigma_i$. We agree by convention that $\sigma_0=1$.

Then the partial sums of $$ P(A_1^c\cap A_2^c\cap \cdots\cap A_n^c)-\sigma_0+\sigma_1-\sigma_2\cdots $$ have alternating signs.

caffeinemachine
  • 18,510

2 Answers2

4

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}$.

Andrew Woods
  • 3,672
  • Brilliant! How did you think of this? I mean what was the thought process? – caffeinemachine Apr 02 '15 at 21:07
  • 3
    My first idea was to use the fact that $\binom{k}{m}$ increases for increasing $m<\tfrac12k$, and then use the final sum of $0$ to show that the partial sums make a palindromic sequence. But I realized that there was a combinatorial explanation of the actual values, and that that approach would be a lot quicker. – Andrew Woods Apr 02 '15 at 22:42
  • Thank you for the response. – caffeinemachine Apr 03 '15 at 06:23
2

$$\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}$$

Hypergeometricx
  • 22,657