Inequality of inclusion-exclusion term

Question

This question was initially posted on math.stackexchange.com but did not receive any answers for half a week.

While analyzing the properties of an algorithm I am working on (I'm a computer scientist), I came up with the following inequality. I am counting the occurrences of two different events using inclusion-exclusion terms. Then, I want to prove that one occurs at least as frequently as the other.

For $0 \leq i \leq j < k$ (natural numbers), the inequality boils down to $$ \sum_{a = 1}^{i} (-1)^{a+1} \frac{a}{k - a} \binom{k}{a} \binom{k - a}{k - i} \binom{k - a}{k - j} \geq 0 \ \text{.} $$ This is also equivalent to $$ \sum_{a=0}^{i-1} (-1)^a \frac{(k-a-2)!}{a! (i-a-1)! (j-a-1)!} \geq 0 \ \text{,} $$ using common identities.

Example: If we look at $k=10$, $j=8$, and vary $i \in \lbrace 0, ..., 8 \rbrace$, we get the following summands for the first expression:

k=10, i=0, j=8:  0 = []
k=10, i=1, j=8:  40 = [40]
k=10, i=2, j=8:  45 = [360, -315]
k=10, i=3, j=8:  0 = [1440, -2520, 1080]
k=10, i=4, j=8:  0 = [3360, -8820, 7560, -2100]
k=10, i=5, j=8:  0 = [5040, -17640, 22680, -12600, 2520]
k=10, i=6, j=8:  0 = [5040, -22050, 37800, -31500, 12600, -1890]
k=10, i=7, j=8:  0 = [3360, -17640, 37800, -42000, 25200, -7560, 840]
k=10, i=8, j=8:  0 = [1440, -8820, 22680, -31500, 25200, -11340, 2520, -180]

Edit: The original problem that I want to tackle is $$ \sum_{a = 1}^{i} (-1)^{a+1} \binom{k}{a} \binom{k - a}{k - i} \binom{k - a}{k - j} \leq \binom{k}{i} \binom{k}{j} \ \text{.} $$ Using Bonferroni's inequalities, we have $$ \sum_{a = 1}^{i} (-1)^{a+1} \binom{k}{a} \binom{k - a}{k - i} \binom{k - a}{k - j} \leq \sum_{a = 1}^{1} (-1)^{a+1} \binom{k}{a} \binom{k - a}{k - i} \binom{k - a}{k - j} = k \binom{k-1}{i-1} \binom{k-1}{j-1} = \frac{ij}{k} \binom{k}{i} \binom{k}{j} \nleq \binom{k}{i} \binom{k}{j} \ \text{.} $$ Unfortunately, $\frac{ij}{k} \nleq 1$.

I would appreciate any suggestions or hints. Thanks in advance.

Answer 1

This is simply computable explicitly via Chu--Vandermonde convolution identity $$\sum_{a+b=n, a,b\geqslant 0}{x\choose a}{y\choose b}={x+y\choose n}.$$ Namely, $$ (-1)^a \frac{(k-a-2)!}{a! (i-a-1)! (j-a-1)!} = (-1)^a \frac{(k-j-1)!}{(i-1)!}\cdot {i-1\choose a}{k-a-2\choose j-a-1}. $$ Further, denoting $b=j-a-1\geqslant 0$ (so $a+b=j-1$) we have $${k-a-2\choose b}={b+(k-j-1)\choose b}=(-1)^b{-(k-j)\choose b},$$ and $$ \sum_{a=0}^{i-1}(-1)^a \frac{(k-a-2)!}{a! (i-a-1)! (j-a-1)!} =(-1)^{j-1}\frac{(k-j-1)!}{(i-1)!}\sum_{a+b=j-1}{i-1\choose a}{-(k-j)\choose b}\\=(-1)^{j-1}\frac{(k-j-1)!}{(i-1)!}{i+j-k-1\choose j-1}= \frac{(k-j-1)!}{(i-1)!}{k-i-1\choose j-1}\geqslant 0. $$ (Note that in the first equality I added several terms corresponding to $a$ between $i$ and $j-1$, but they are all equal to 0).