# Bounding this combinatorial sum

I'm looking to find a closed form expression or to bound the following sum $$\sum_{\atop \LARGE j\ =\ \left(k + 1\right)/3\ +\ 1} ^{\LARGE 2\left(k + 1\right)/3 \atop} {i - 1 \choose j - 1}{n - {\rm i} \choose k - j + 1}$$ where $$1\leq i \leq n,\,\,0< k and $$k + 1$$ is divisible by $$3$$.

I've been able to bound it by $${n - 1\,\choose k}$$, but it is not enough for the problem I'm working on.

Context: Given an input set $$S$$ of $$n$$ distinct numbers, we sample from it $$k+1$$ distinct numbers and get a new set $$S'$$. Let us call the rank of an element in a set, its position in the sorted version of the set in increasing order. For example, for the set $$\{ 1, 8, 7, 3\}$$, 8 would be the element of rank 4. The probability that the element of rank $$i$$ in the input set $$S$$ is the element of rank $$j$$ in the sampled set $$S'$$ is clearly $$\frac{{i-1\choose j-1}{n-i \choose k-j+1}}{n \choose k+1}.$$ I'm interested in bounding the probability that the element of rank $$i$$ in the input array $$S$$ is in the middle third of the sampled set $$S'$$: $$\frac{\sum_{\atop \LARGE j\ =\ \left(k + 1\right)/3\ +\ 1} ^{\LARGE 2\left(k + 1\right)/3 \atop} {i - 1 \choose j - 1}{n - {\rm i} \choose k - j + 1}}{n \choose k+1}$$

• This is very similar to your previous question. You are more likely to get an answer if you tell us where the sum comes from, because the context can hint at possible solution methods. For example, if you see a complicated sum like $\sum_{i=0}^n{\binom{n}{i}}/{\binom{n+k}i}$, it is unclear how to simplify, but knowing the context it came from allows you to use linearity of expectation to prove the sum is $(n+k+1)/(k+1)$. Nov 24, 2022 at 18:16
• @MikeEarnest: Just added the context to my original question. Nov 24, 2022 at 21:09