2
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .