Evaluating a sum involving binomial coefficients

[Saitama]

Problem:
Evaluate
$$\mathop{\sum \sum}_{0\leq i<j\leq n} (-1)^{i-j+1}{n\choose i}{n\choose j}$$

Attempt:
I wrote the sum as:
$$\sum_{j=1}^{n} \sum_{i=0}^{j-1} (-1)^{i-j+1}{n\choose i}{n\choose j}$$
I am not sure how to proceed from here. I tried writing down a few terms but that doesn't seem to help.

Any help is appreciated. Thanks!

 

[Prove It]

To me, the innermost sum looks like a binomial expansion...

 

[Saitama]

To me, the innermost sum looks like a binomial expansion...

I don't think so...(Wondering)

The sum is
$$-\sum_{j=1}^{n} (-1)^i{n\choose i} \sum_{i=0}^{j-1} (-1)^j {n\choose j}$$
The limits for innermost sum varies from 0 to j-1, not 0 to n.

 

[Opalg]

Problem:
Evaluate
$$\mathop{\sum \sum}_{0\leq i<j\leq n} (-1)^{i-j+1}{n\choose i}{n\choose j}$$

First, $(-1)^{-j} = (-1)^{\,j}$, so we can write the sum as \(\displaystyle S = \mathop{\sum \sum}_{0\leqslant i<j\leqslant n} (-1)^{i+j+1}{n\choose i}{n\choose j}\). The summand is then symmetric in $i$ and $j$, so the sum $S$ is equal to \(\displaystyle \mathop{\sum \sum}_{0\leqslant j<i\leqslant n} (-1)^{i+j+1}{n\choose i}{n\choose j}\) (with $i$ and $j$ interchanged). If we now add those two sums, and also throw in the diagonal terms (those with $i=j$ in the summand, namely \(\displaystyle \sum_{i=0}^n -{n\choose i}^2\)), then we would get the sum over the whole $n\times n$ array of indices $\{(i,j): 1\leqslant i \leqslant n,\; 1 \leqslant j \leqslant n\}$. But that sum is \(\displaystyle -\sum_{i=0}^n (-1)^i{n\choose i} \sum_{j=0}^n (-1)^j{n\choose j}\). And \(\displaystyle \sum_{i=0}^n (-1)^i{n\choose i} = 0\), because it is the binomial expansion of $(1-1)^n$.

It follows that \(\displaystyle 2S - \sum_{i=0}^n {n\choose i}^2 = 0\), and so \(\displaystyle S = \frac12\sum_{i=0}^n {n\choose i}^2 = \frac{(2n)!}{2(n!)^2}\) (see formula (9) here for the sum of the squares of binomial coefficients $n\choose i$).

 

[Saitama]

First, $(-1)^{-j} = (-1)^{\,j}$, so we can write the sum as \(\displaystyle S = \mathop{\sum \sum}_{0\leqslant i<j\leqslant n} (-1)^{i+j+1}{n\choose i}{n\choose j}\). The summand is then symmetric in $i$ and $j$, so the sum $S$ is equal to \(\displaystyle \mathop{\sum \sum}_{0\leqslant j<i\leqslant n} (-1)^{i+j+1}{n\choose i}{n\choose j}\) (with $i$ and $j$ interchanged). If we now add those two sums, and also throw in the diagonal terms (those with $i=j$ in the summand, namely \(\displaystyle \sum_{i=0}^n -{n\choose i}^2\)), then we would get the sum over the whole $n\times n$ array of indices $\{(i,j): 1\leqslant i \leqslant n,\; 1 \leqslant j \leqslant n\}$. But that sum is \(\displaystyle -\sum_{i=0}^n (-1)^i{n\choose i} \sum_{j=0}^n (-1)^j{n\choose j}\). And \(\displaystyle \sum_{i=0}^n (-1)^i{n\choose i} = 0\), because it is the binomial expansion of $(1-1)^n$.

It follows that \(\displaystyle 2S - \sum_{i=0}^n {n\choose i}^2 = 0\), and so \(\displaystyle S = \frac12\sum_{i=0}^n {n\choose i}^2 = \frac{(2n)!}{2(n!)^2}\) (see formula (9) here for the sum of the squares of binomial coefficients $n\choose i$).

This is great, thank you Opalg! :) (Bow)