13
$\begingroup$

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}$$

$\endgroup$
15
  • $\begingroup$ This inequality does not seem to hold when $k=n$ because then the right-hand side is zero, isn't it? $\endgroup$
    – René Gy
    Sep 15, 2021 at 17:16
  • $\begingroup$ Yes, it has to be $1\leq k\leq n-1$. I'll edit that now. $\endgroup$ Sep 15, 2021 at 17:17
  • $\begingroup$ 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$. $\endgroup$
    – mathlove
    Sep 15, 2021 at 18:10
  • $\begingroup$ It doesn't hold either when $k=2$ for $n= 3$ , $n=4$ nor $n=5$ $\endgroup$
    – René Gy
    Sep 15, 2021 at 18:12
  • $\begingroup$ It seems that $i \ge 3$ and $k \le n-2$ is required. $\endgroup$
    – René Gy
    Sep 15, 2021 at 18:13

1 Answer 1

2
+125
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ Sep 22, 2021 at 12:13
  • $\begingroup$ @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? $\endgroup$ Sep 22, 2021 at 15:46
  • $\begingroup$ 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) $\endgroup$ Sep 22, 2021 at 16:18
  • $\begingroup$ I have checked some extreme values (n=400 and 40, k=20, i=1), and what you say holds up nice and tightly. $\endgroup$ Sep 22, 2021 at 18:44
  • $\begingroup$ @LuisFerroni I made a mistake with the hockey stick identity (fixed) and simplified some things. $\endgroup$ Sep 22, 2021 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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