While analyzing the properties of an algorithm I am working on, I came up with the following inequality of inclusion-exclusion terms.
Let $0 \leq i \leq j < k$ be natural numbers. Then, I want to prove $$ \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{.} $$ The inequality seems fairly simple ($\frac{a}{k - a} > 0$). However, the alternating sign complicates things. I have tried to develop a proof by induction but cannot identify the induction step. Also, I have tried to partition the sum into positive and negative terms to handle them separately.
Example: If we look at $k=10$, $j=8$, and vary $i \in \lbrace 0, ..., 8 \rbrace$, we get the following summands:
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]
Note that no grouping of two, three, or four elements produces the desired sum.
Edit: By applying common identities from "Concrete Mathematics" (Graham, Knuth, and Patashnik), the problem statement is equivalent to $$ \sum_{a=0}^{i-1} (-1)^a \frac{(k-a-2)!}{a! (i-a-1)! (j-a-1)!} \geq 0 \ \text{.} $$
I would appreciate any suggestions or hints. Thanks in advance.