How to calculate the sum of general type $\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k- n + a \choose r }$?

Question

QUESTION. How to calculate the sum of such general type? $$\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k - n + a \choose r }. $$

Some particular examples $$\sum_{k=0}^n {n\choose k} {n\choose k+a} = {2n\choose n+a},$$ $$\sum_{k=0}^n {n\choose k} {n\choose k+a} \binom{2 k - n + a}1 = 0, $$ $$\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k - n + a \choose 2} = -\frac{(a+ n)(a-n)}{2 (2n-1)} {2n\choose n+a}, $$ $$\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k - n + a \choose 3} = \frac{(a+ n)(a-n)}{2 (2n-1)} {2n\choose n+a}. $$ I am struggling to calculate at least $$\sum_{k=0}^n {n\choose k} {n\choose k+a} {2 k - n + a \choose 4} $$ Can someone help me with this one?

Answer 1

The pattern continues indeed except the RHS becomes more and more involved as you increase $r$. At any rate, here is what we get for the case $r=4$: $$\sum_{k=0}^n\binom{n}k\binom{n}{k+a}\binom{2k-n+a}4= \frac{(a^2-n^2-6n+11)\,(a-n)\,(a+n)}{8\,(2n-1)\,(2n-3)}\cdot \binom{2n}{n+a}.$$ Another sampler for $r=5$: $$\sum_{k=0}^n\binom{n}k\binom{n}{k+a}\binom{2k-n+a}5= -\frac{(a^2-n^2-2n+5)\,(a-n)\,(a+n)}{4\,(2n-1)\,(2n-3)}\cdot \binom{2n}{n+a}.$$ These kinds of problems can be proved by the automated tools of Zeilberger's algorithm which relies on Wilf-Zeilberger pairs. If you are able to use the Maple symbolic software then download the algorithm to make use of it. These days, this package is also part of the routines in Maple as well as Mathematica.

Answer 2

For fixed $r$ you may expand ${2k-n+a\choose r}$ as a polynomial in $k$ (whose coefficients are polynomials in $n-a$) as ${2k-n+a\choose r}=\sum_{i=0}^r c_i {k\choose i}$. To find $c_i$'s, fix $s\in \{0,1,\ldots,r\}$; substitute $k=j\in \{0,1,\ldots,s\}$ to get $\sum_{i=0}^j c_i{j\choose i}={2j-n+a\choose r}$, multiply this by $(-1)^{s-j}{s\choose j}$ and sum up over $j=0,\ldots,s$. Then $c_i$ comes with the coefficient $$\sum_{j=i}^s (-1)^{s-j}{j\choose i}{s\choose j}=\sum_{j=i}^s (-1)^{s-j}{s\choose i}{s-i\choose j-i}={s\choose i}\sum_{\ell=0}^{s-i}(-1)^{s-i-\ell}{s-i\choose \ell}=\delta_{is},$$ and we get $$c_s=\sum_{j=0}^s (-1)^{s-j}{s\choose j}{2j-n+a\choose r}.$$

Therefore your sum $S$ equals $$S=\sum_{i=0}^r c_i\sum_{k=0}^n{n\choose k}{k\choose i}{n\choose k+a}.$$ Now use $${n\choose k}{k\choose i} ={n\choose i} {n-i\choose k-i},$$ and finally apply Vandermonde convolution $$\sum_{k=i}^n {n-i\choose k-i}{n\choose k+a}={2n-i\choose n+a}$$ to express your sum as $$S=\sum_{i=0}^rc_i{n\choose i}{2n-i\choose n+a}.$$

Answer 3

Alternatively, one can get an explicit expression for a fixed $r$ via generating functions by noticing that the given sum equals $$[y^{n+a}z^r]\ (y+1+z)^n (1+y(1+z))^n (1+z)^{-n}$$ and rewriting it as $$[y^{n+a}z^r]\ \big((1+y)^2 + \frac{z^2}{1+z}y\big)^n = [y^{n+a}z^r]\ \sum_{i=0}^{\lfloor r/2\rfloor} \binom{n}{i} (1+y)^{2(n-i)} y^i\left(\frac{z^2}{1+z}\right)^i,$$ which we evaluate as $$[y^{n+a}]\ \sum_{i=0}^{\lfloor r/2\rfloor} \binom{n}i\binom{-i}{r-2i} (1+y)^{2(n-i)}y^i = (-1)^r \sum_{i=0}^{\lfloor r/2\rfloor} \binom{n}i \binom{r-i-1}{r-2i} \binom{2(n-i)}{n+a-i}.$$