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$

Question

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

Answer 1

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

Answer 2

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