Elementary proof that alternating sum over inversion coefficients of permutations vanishes

Question

For a permutation $a_1 a_2 \ldots a_n$ of $\{1,\ldots, n \}$, an inversion is a pair $a_i, a_j$ with $i < j$ but $a_i > a_j$. Example $1~4~3~5~2$ has the inversions $4,3; 4,2; 3,2;5,2$. Let $I_{n,k}$ be the number of $n$-permutations with exactly $k$ inversions. Show that $$ \sum_{k=0}^{\binom{n}{2}} (-1)^k I_{n,k} = 0. $$

This problem is taken from M. Aigner, Discrete Mathematics, ex. 1.31. Do you know an elementary proof for it? By elementary I mean just using counting arguments introduced in the first chapter of this book (some basic enumerative combinatorics stuff).

I know that this must be true by some basic abstract algebra as the signum of a permutation is given by $(-1)^{\textrm{number of inversion}}$ and $|A_n : S_n| = 2$, and as the above sum counts exactly all permutations it must vanish. But this argument I think is to advanced, so I am looking for an more elemetary one.

For example, if $n$ is odd, then $\binom{n}{2}$ is odd too, and with $I_{n,k} = I_{n, \binom{n}{2}-k}$ (which is also part of the exercise) it easy to see that this sum cancels, but this does not work if $n$ is even.

Answer 1

As stated, this is not true. You've lost the qualification $n \ge 2$ from the source: with $n = 1$ the sum is just $(-1)^0 I_{1,0} = 1$.

With $n \ge 2$ you can partition the $n!$ permutations into pairs by matching $\pi$ with $(2 1)\pi$. The numbers of inversions of the two elements of each pair differ by exactly $1$, so they cancel.

Answer 2

Try induction on $n$. Insert $n+1$ at position $i$ of an n-permutation, so it contributes $n+1-i$ inversions. All permutations on $n+1$ objects can be uniquely constructed this way, so $$\sum_{k=0}^{\binom {n+1}2}(-1)^kI_{n+1,k}=\sum_{k=0}^{\binom n2}(\sum_{i=1}^{n+1}(-1)^{n+1-i+k} I_{n,k})$$ $$=\sum_{i=1}^{n+1}(-1)^{n+1-i}\sum_{k=0}^{\binom n2}(-1)^kI_{n,k}$$ $$=0$$