# Inequality of inclusion-exclusion term

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.

• The natural inequities about the inclusion-exclusion formula are Bonferroni inequalities. Isn't that by chance they apply to your initial counting problem? Dec 4, 2023 at 9:31
• @PietroMajer, I have added more detail to the question. Dec 4, 2023 at 10:32

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).
• Thanks a lot. I still have some difficulties understanding why $(-1)^{j-1}\frac{(k-j-1)!}{(i-1)!}{i+j-k-1\choose j-1} \geq 0$, though, as $(-1)^{j-1}$ is negative for even $j$. Dec 4, 2023 at 11:49
• because $(-1)^{n}{-m\choose n}={m+n-1\choose n}$ Dec 4, 2023 at 11:53