4
$\begingroup$

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.

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

1 Answer 1

8
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Tobias
    Dec 4, 2023 at 11:49
  • $\begingroup$ because $(-1)^{n}{-m\choose n}={m+n-1\choose n}$ $\endgroup$ Dec 4, 2023 at 11:53
  • $\begingroup$ I see. Thanks a lot for your patience ^^. $\endgroup$
    – Tobias
    Dec 4, 2023 at 11:54
  • $\begingroup$ You are welcome. I edited accordingly. $\endgroup$ Dec 4, 2023 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.