# Estimating alternating sum of product of binomial coefficients $\sum_{i=0}^{k-1} \binom{n}{m+i} \binom{m+i}{k} \binom{k-1}{i} (-1)^i$

I am interested in getting a lower bound on the expression

$$\sum_{i=0}^{k-1} \binom{n}{m+i} \binom{m+i}{k} \binom{k-1}{i} (-1)^i .$$

for $$1 \le k,m \le n$$. In particular, $$m = n/2 + C\sqrt{n}$$ for some constant $$C > 0$$.

Applying the identity

$$\binom{a}{b} \binom{b}{c} = \binom{a}{c} \binom{a-c}{b-c}$$

gives

$$\binom{n}{k} \sum_{i=0}^{k-1} \binom{n-k}{m-k+i} \binom{k-1}{i} (-1)^i .$$

However, it is not clear how to proceed from here. I am curious to know if there are any combinatoric identities / estimates that could be useful here.

For starters one can think of $$k$$ being some constant. But I would also be interested in general $$1 \le k \le n$$.

• What is the source of this sum? Apr 16, 2021 at 0:52

There is an explicit result for this summation. For sure, it is given in terms of the gaussian hypergeometric function $$S_{m,n,k}=\sum_{i=0}^{k-1} (-1)^i\binom{n}{m+i} \binom{m+i}{k} \binom{k-1}{i}=$$ $$\frac{k-m-1}{m-n}\binom{m+1}{k} \binom{n}{m+1} (\, _2F_1(1-k,m-n;-k+m+1;-1)-1)$$

For the particular case where $$m=\frac n2$$, it is quite nice and write $$S_{\frac n2,n,k}=2^{n-1}\frac{ \Gamma \left(\frac{n+1}{2}\right)}{\Gamma (k+1)}\,A$$ $$A=2^k \left(\frac{1}{\Gamma \left(\frac{1-k}{2}\right) \Gamma \left(\frac{n+2-k}{2} \right)}+\frac{1}{\Gamma \left(\frac{2-k}{2}\right) \Gamma \left(\frac{n+1-k}{2} \right)}\right)- \frac{2}{\sqrt{\pi }\,\, \Gamma \left(\frac{n+2-2k}{2}\right)}$$

• Thanks! This looks quite useful. Can you please explain a little bit on how to derive the expression involving the hypergeometric function? Apr 16, 2021 at 15:41
• Also do you know what happens when $m = n/2 + O(\sqrt{n})$? I would be happy with an estimate (a lower bound in particular) rather of a closed-form expression. Apr 16, 2021 at 15:47

you can rewrite your last sum as
\eqalign{ & S(n,m,k) = \sum\limits_{i = 0}^{k - 1} {\left( { - 1} \right)^{\,i} \left( \matrix{ n - k \cr m - k + i \cr} \right) \left( \matrix{ k - 1 \cr i \cr} \right)} \quad \left| \matrix{ \,n,m,k \in Z \hfill \cr \,1 \le k \hfill \cr} \right.\quad = \cr & = \left( { - 1} \right)^{\,k - 1} \sum\limits_{i = 0}^{k - 1} {\left( { - 1} \right)^{\,k - 1 - i} \left( \matrix{ n - k \cr m - 1 - \left( {k - 1 - i} \right) \cr} \right) \left( \matrix{ k - 1 \cr \left( {k - 1 - i} \right) \cr} \right)} = \cr & = \left( { - 1} \right)^{\,k - 1} \sum\limits_{j = 0}^{k - 1} {\left( \matrix{ n - k \cr m - 1 - j \cr} \right)1^{\,m - 1 - j} \left( \matrix{ k - 1 \cr j \cr} \right)\left( { - 1} \right)^{\,j} } = \cr & = \left( { - 1} \right)^{\,k - 1} \left[ {x^{\,m - 1} } \right] \left( {1 + x} \right)^{n - k} \left( {1 - x} \right)^{k - 1} = \cr & = \left[ {x^{\,m - 1} } \right]\left( {1 + x} \right)^{n - k} \left( {x - 1} \right)^{k - 1} \quad = \quad \cdots \cr} the result depending on whether you consider that $$n,m$$ might also be negative.

But unfortunately the analysis fragments down into many different cases.

Even assuming as per your comment that all the parameters are positive, you come to distinguishing whether $$n-k$$ is positive or not.

Suppose it is positive $$\left\{ \matrix{ 1 \le k \le n \hfill \cr 1 \le n \hfill \cr} \right.$$ then \eqalign{ & S(n,m,k) = \left[ {x^{\,m - 1} } \right]\left( {1 + x} \right)^{n - k} \left( {x - 1} \right)^{k - 1} = \cr & = \left[ {x^{\,m - 1} } \right]\left( {x + 1} \right)^a \left( {x - 1} \right)^b \cr} and here you shall distinguish whether $$b \le a\;\left( {2k \le n + 1} \right)$$ in which case you can write \eqalign{ & S(n,m,k) = \left[ {x^{\,m - 1} } \right]\left( {x + 1} \right)^{a - b} \left( {x^{\,2} - 1} \right)^b = \cr & = \left[ {x^{\,m - 1} } \right]\sum\limits_j {\left( { - 1} \right)^{\,s - j} \left( \matrix{a - b \cr j \cr} \right)\left( \matrix{ b \cr s - j \cr} \right)x^{\,2s - j} } = \cr & = \sum\limits_j {\left( { - 1} \right)^{\,{{m - 1 - j} \over 2}} \left( \matrix{ a - b \cr j \cr} \right)\left( \matrix{b \cr {{m - 1 - j} \over 2} \cr} \right)} \cr} and in case, split between even \ odd $$m$$ ....

• Thanks. But this does not seem to give a way to estimate the quantity. I am interested in positive $n, m$ and $k$. Apr 15, 2021 at 23:46
• I expanded a bit my answer, but it comes out that the sum is much dependent on the values of the parameters Apr 16, 2021 at 15:09
• Thanks! Still, it is not clear how to handle the alternating sum. I have added a bit more details on the parameters. Apr 16, 2021 at 15:52
• the partial sum over the lower index does not have (to your goals) a manageable expression, either if it is straight or alternate Apr 16, 2021 at 18:21