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
    Commented Sep 15, 2021 at 17:16
  • $\begingroup$ Yes, it has to be $1\leq k\leq n-1$. I'll edit that now. $\endgroup$ Commented 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
    Commented 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
    Commented Sep 15, 2021 at 18:12
  • $\begingroup$ It seems that $i \ge 3$ and $k \le n-2$ is required. $\endgroup$
    – René Gy
    Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Sep 22, 2021 at 18:44
  • $\begingroup$ @LuisFerroni I made a mistake with the hockey stick identity (fixed) and simplified some things. $\endgroup$ Commented Sep 22, 2021 at 19:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .