Proof of Binomial Sum via Double Counting I have attempted to double count the following equivalence but to no avail. I'm unable to arrive at the Left Hand Side.
$\displaystyle \sum_{k=0}^n \frac{(-1)^k}{k+3} \binom{n}{k} = \frac{2}{(n+1)(n+2)(n+3)} = \frac{1}{n+1}-\frac{2}{n+2}+\frac{1}{n+3}$
 A: This is the $m = 2$ case of the more general identity
$$\sum_{k=0}^n \frac{(-1)^k}{k + m + 1} \binom nk = \frac{m!n!}{(m + n + 1)!} = \sum_{k=0}^m \frac{(-1)^k}{k + n + 1} \binom mk.$$
We’ll prove the left equation, since the right equation is symmetric.
Consider the following game. From a shuffled stack of $n + m + 1$ envelopes containing different numbers, one envelope is set aside, and $m$ envelopes are dealt to the player’s hand. The player chooses any subset of the remaining $n$ envelopes to add to their hand. Then all the envelopes are opened. The player wins if all numbers in their hand are higher than the number that was set aside.
Eve plays a game, choosing a random even-sized subset of the remaining $n$ envelopes. Odin plays a game, choosing a random odd-sized subset. Their respective winning probabilities are clearly
$$p_E = \frac{1}{2^{n - 1}}\sum_{\text{$k$ even}} \frac{1}{k + m + 1} \binom nk, \quad p_O = \frac{1}{2^{n - 1}}\sum_{\text{$k$ odd}} \frac{1}{k + m + 1} \binom nk.$$
To compare these strategies, construct a correspondence between Eve games and Odin games by finding the largest-numbered of the $n$ envelopes, and retroactively adding it to, or removing it from, the player’s hand. Any winning Odin game is converted into a winning Eve game (because adding an envelope larger than one already in the hand has no effect, and removing an envelope can only help). Any winning Eve game is converted back into a winning Odin game, unless

*

*Eve’s hand had none of the $n$ envelopes (only the required $m$), and

*all of the $m$ numbers are larger than the number set aside, and

*all of the $n$ numbers are smaller than the number set aside.

The difference between Eve’s and Odin’s winning probabilities is the probability of this exception:
$$p_E - p_O = \frac{1}{2^{n-1}} · \frac{m!n!}{(m + n + 1)!},$$
yielding the desired result.
