# A proof of a non-standard increasing alternating sum of binomial coefficients identity

While working on an elementary combinatorics problem, I made the observation that the following identity holds for all examples I have calculated:

$$\sum_{j=2}^{n} (-1)^j (j-1) { n \choose j} = 1.$$

I have not been able to prove this identity. (I do not have a strong combinatorics background.) I have searched the internet for a similar identity but only came up with the standard identity

$$\sum_{j=0}^{n} (-1)^{j+1} (j) { n \choose j} = 0$$.

I have been unable to modify a proof of the standard identity to prove the one I originally stated. I also do not see an obvious (to me) way to apply the binomial theorem directly to develop a proof. Any ideas would be appreciated.

• Yes I did type a $n$ for the exponent of (-1) when it should have been $j$. My apologies. Feb 3, 2019 at 3:06
• Thank you for the responses. Feb 3, 2019 at 23:05

\begin{align} \sum_{j=2}^n (-1)^j (j-1){n\choose j}&= 1 + \sum_{j=0}^n (-1)^j (j-1){n\choose j}\\ &= 1 + \sum_{j=0}^n (-1)^j j{n\choose j} - \sum_{j=0}^n (-1)^j {n\choose j} \\ &= 1 + 0 + (1 + (-1))^n = 1. \end{align} using the "standard identity" that you stated and the binomial theorem.

EDIT: As Mike Earnest noted in the comments, this works for $$(-1)^j$$, not $$(-1)^n$$, which I didn't notice the question actually said. I'm assuming that OP meant the former, since the latter is not true.

I have a semi-combinatorial proof. We interpret the expression as counting pairs $$(S,x)$$, where $$S\subseteq [n]$$ where $$[n]=\{1,2,\ldots,n\}$$, such that $$x\in S$$, and $$x$$ is not the largest element of $$x$$. That is, one element of the set, which is not the largest one, is deemed special. This is because $${n\choose j}$$ chooses a size $$j$$ subset of $$[n]$$, and $$(j-1)$$ chooses an element, besides the largest one. Each term has a positive contribution if $$|S|$$ is even, and a negative contribution if $$|S|$$ is odd. Then we want to show that the number of such pairs $$(S,x)$$ where $$|S|$$ is even is one greater than the number of pairs $$(S,x)$$ where $$|S|$$ is odd.

We prove this by bijection- kind of. Given $$S\subseteq [n]$$, consider the following function:

$$f(S)=\begin{cases} S\cup\{n\}, \text{if }n\notin S\\ S\setminus\{n\},\text{if }n\in S \end{cases}$$.

Then given a pair $$(S,x)$$, consider the pair $$g(S,x)=(f(S),x)$$. Then $$f(S)$$ is even when $$S$$ is odd, and vice versa. This is similar to the proof that the number of even subsets of $$[n]$$ is equal to the number of odd subsets of $$[n]$$ when $$n>0$$. Then $$g(S,x)$$ is matching the pairs $$(S,x)$$ where $$|S|$$ is even with the pairs where $$|S|$$ is odd. But remember that we want $$x\in S$$ to not be the greatest element of $$S$$. If $$n\in S$$ and $$x$$ is the second greatest element of $$S$$, then $$(f(S),x)$$ will not satisfy the given requirement.

We've reduced the problem into looking at this special case where $$n\in S$$ and $$x$$ is the second greatest element of $$S$$. How many such pairs are there? Counting such pairs corresponds to choosing a subset $$T$$ of $$[n-1]$$ and automatically picking its greatest element $$y$$, since we can then just take $$(T\cup\{n\},y)$$ to be our pair. However, we can't take $$T=\varnothing$$, since it does not have a greatest element. In other words, we just look at $$\#\text{odd subsets of } [n-1]-\#\text{nonempty even subsets of }[n-1]$$ (since if $$T$$ is odd, $$T\cup\{n\}$$ is even, and vice versa), which we know is $$1$$, since $$\#\text{odd subsets of }[n-1]-\#\text{even subsets of }[n-1]=0$$, but not subtracting $$1$$ for the empty set increases the value by $$1$$, which is where we get the $$1$$ from.