1
$\begingroup$

I was working on proving the following fact of probability. Suppose $A_1,\dots,A_n$ are events, and define \begin{align*} S_1 &= \sum_{1\le i \le n}P(A_i) \\ S_2 &= \sum_{1\le i < j \le n}P(A_i\cap A_j) \\ S_3 &= \sum_{1\le i < j < k \le n}P(A_i\cap A_j\cap A_k) \\ \vdots & \qquad\qquad\vdots \end{align*} and so on. Then the probability of exactly $m$ events occurring is $$ p(m) = S_m - {m+1\choose m}S_{m+1}+{m+2\choose m}S_{m+2}-\dots+(-1)^{n-m}{n\choose m}S_n. $$ As a part of proving this identity, I ended up proving the following result about binomial coefficients.

Let $1\le m \le n$ and $1\le r\le n-m$. Then $$ \color{blue}{{m+r\choose m} = \sum_{j=1}^{r}(-1)^{j+1}{m+j\choose m}{m+r\choose m+j}}. $$ I suspect there has to be a nice combinatorial interpretation of this alternating sum, and I am hoping someone would make it clear to me if it exists.

Just to be clear, I am not asking for a proof of the identity in blue, which I already have. I am asking if there is a nice way to see the result by counting. After all, the left-hand side is the number of ways to choose $m$ objects from $m+r$ objects, and the right-hand side is some kind of inclusion-exclusion-y thing, also involving binomial coefficients. Thanks!


As a bonus, there is a similar alternating sum on this site, and I expect that these two are related. If there is a connection, $+\epsilon$ credit for explaining the connection between these two sums.

$\endgroup$
1
$\begingroup$

Let's rearrange the formula as $\sum_{j=0}^{r}(-1)^{j}{m+r\choose m+j}{m+j\choose m}=0$. We can interpret ${m+r\choose m+j}{m+j\choose m}$ as the number of ways to choose a first team of $r-j$ people and then choose a second team of $j$ people out of a group of $m+r$ people. The equality tells us that total number of ways when the number of members of the first team is even is equal to that when the number of members of the first team is odd. And it is true. Imagine there are a first team and a second team such that the number of members in the first team is even. We assume all people are of distinct ages, we pick the youngest person in the union of the first and the second teams, and reassign him to the second team if he was in the first team, and vice versa. Then we will get an arrangement for the teams such that the number of members in the first team is odd. This gives us a one-to-one correspondence, and proves the equality.


To your bonus question, the equality $\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$ is talking something about the number of ways to choose $n-i$ people to form the first team, then in the rest of the $i+1$ people, we do not consider the youngest person anymore and choose $i-k$ people to form the second team. But I would say it's actually what they have described in the chosen answer, where they didn't consider people but letters in order, you can also imagine that we can arrange all poeple by their ages, then actually everything is roughly the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.