# Inequality between binomial sums

I want to prove that the following inequality holds whenever $$k\leq n-1$$ and $$1\leq i\leq \lfloor\frac{k}{2}\rfloor$$.

$$\frac{2}{C}\binom{n}{k}\binom{k}{i+1} \leq \frac{k}{i}\sum_{j=i}^{k-1} (k-j)\binom{j-1}{i-1}\binom{n-k+j-1}{j}$$

where $$C = \max(k,n-k)+1$$.

Two identities I suspect might be very useful here are $$\binom{k}{i+1} = \sum_{j=i}^{k-1} (k-j)\binom{j-1}{i-1}$$ $$\binom{n-1}{k-1}=\sum_{j=0}^{k-1} \binom{n-k+j-1}{j}$$

I tried to use these and the Chebyshev's inequality (which states that if $$a_1\leq \cdots \leq a_n$$ and $$b_1\leq \cdots \leq b_n$$, then $$\sum a_i \cdot \sum b_i \leq n \sum a_ib_i$$) but it didn't work. I think that this inequality is somehow "tight".

Also, I tried splitting into two cases $$k\leq n-k$$ and $$k\geq n-k$$ to have a more concrete expression for $$C$$. Any help would be highly appreciated.

EDIT: I have tried approaching the case $$i=1$$, and many identities can be used. The inequality in this case is very tight, and I think that proceeding via induction on $$i$$ does not help, as the inequality seems to get tighter at every step.

EDIT2: The problem with the Chebyshev approach is that the sequence $$(k-j)\binom{j-1}{i-1}$$ is not increasing (hence it is not possible to use the Chebyshev's inequality as stated).

EDIT3: I have noticed using Zeilberger's algorithm that $$\sum_{j=i}^{k-1} j\binom{j-1}{i-1}\binom{n-k+j-1}{j} = \frac{i(i+1)(n-k)}{n(n+i-k)} \binom{n}{k}\binom{k}{i+1}$$

However, no closed expression seems to exist for

$$\sum_{j=i}^{k-1}\binom{j-1}{i-1}\binom{n-k+j-1}{j}$$

• This inequality does not seem to hold when $k=n$ because then the right-hand side is zero, isn't it? Sep 15, 2021 at 17:16
• Yes, it has to be $1\leq k\leq n-1$. I'll edit that now. Sep 15, 2021 at 17:17
• I think that for $i=2,k=4$ and $n=5$, the inequality does not hold because the left-hand side is $10$ and the right-hand side is $8$. Sep 15, 2021 at 18:10
• It doesn't hold either when $k=2$ for $n= 3$ , $n=4$ nor $n=5$ Sep 15, 2021 at 18:12
• It seems that $i \ge 3$ and $k \le n-2$ is required. Sep 15, 2021 at 18:13

(Still a work in progress, see last expression for a sufficient condition on $$C$$.)

The strategy is to rewrite both sides as multinomials. We then get something that looks similar enough to the hockey stick identity for multinomials.

For the left hand side:

$$\frac{2}{C}\binom{n}{k}\binom{k}{i+1} = \frac{2}{C}\binom{n}{n-k,\,i+1,\,k-i-1}$$

For the right hand side:

$$\frac{k}{i}(k-j)\binom{j-1}{i-1}\binom{n-k+j-1}{j}$$

$$= \binom{n-k+j}{n-k,\, i, \, j-i} \frac{k(k-j)(n-k)}{j(n-k+j)}$$

The hockey stick identity for multinomials (https://www.fq.math.ca/Scanned/34-3/jones.pdf) says that:

$$\binom{n}{n-k,\,i+1,\,k-i-1}$$

$$= \sum_{j=i}^{k-1} \binom{n-k+j}{n-k-1,\, i+1, \, j-i} + \sum_{j=i}^{k-1} \binom{n-k+j}{n-k,\, i, \, j-i}$$

$$= \frac{n-k + i +1}{i+1} \sum_{j=i}^{k-1} \binom{n-k+j}{n-k,\, i, \, j-i}$$

Therefore,

$$\frac{2}{C}\binom{n}{k}\binom{k}{i+1} = \frac{2}{C} \cdot \frac{n-k + i +1}{i+1} \sum_{j=i}^{k-1} \binom{n-k+j}{n-k,\, i, \, j-i}$$

We are done if we can show for all valid $$j$$ that:

$$\frac{2}{C} \cdot \frac{n-k + i +1}{i+1} \leq \frac{k(k-j)(n-k)}{j(n-k+j)}$$

Or that:

$$\frac{2j(n-k + i +1)(n-k+j)}{k(i+1)(k-j)(n-k)} \leq C$$

Since the left hand side increases in $$j$$, we can plug in $$j=k-1$$:

$$\frac{2(k-1)(n-k + i +1)(n-1)}{k(i+1)(n-k)} \leq C$$

We could get tighter bounds by not trying to prove the coefficient is larger for all $$j$$ but just enough of them (specifically when the multinomial is large). Also, when $$k$$ is almost $$n$$, the summation is very flat, and so we don't care as much about $$j=k-1$$ versus $$j=k-2$$, etc. So, if $$k$$ is close to $$n$$, then the inequality might only need to hold for a somewhat smaller value of $$j$$. I think, we might need to break up the proof into cases over $$k$$. (The $$k-j$$ term in the denominator then becomes pretty important.)

• Regarding to your last sentence, I do have direct proofs for $i=1$, but I agree that it is exactly the scenario in which the right-hand-side and the left-hand-side have minimum difference when fixing $k$ and $n$. Sep 22, 2021 at 12:13
• @LuisFerroni Interesting, $i=1$ seems to be the most difficult case for me to prove. Maybe your proof for $i=1$ could be generalized? Are you able to post it? Sep 22, 2021 at 15:46
• If I find time to write it up, I will post it. (Notice that when $i=1$, the right hand side admits a closed form which allows you to work much more comfortably) Sep 22, 2021 at 16:18
• I have checked some extreme values (n=400 and 40, k=20, i=1), and what you say holds up nice and tightly. Sep 22, 2021 at 18:44
• @LuisFerroni I made a mistake with the hockey stick identity (fixed) and simplified some things. Sep 22, 2021 at 19:42