Find close expression for the sum $S_{n,k}=\sum\limits_{i=0}^{2n} (-1)^i \binom{n-1}{i} \binom{n+1}{k-i}.$

Question

Find close expression for the sum $$S_{n,k}=\sum_{i=0}^{2n} (-1)^i \binom{n-1}{i} \binom{n+1}{k-i}.$$ For small $k$ I have got following \begin{align} &S_{n,0}=1,\\ &S_{n,1}=2,\\ &S_{n,2}=-n+2,\\ &S_{n,3}=-2n+2,\\ &S_{n,4}=\frac{(n-1)(n-4)}{2},\\ &S_{n,5}=(n-1)(n-2),\\ &S_{n,6}=-\frac{(n-1)(n-2)(n-6)}{6} \end{align}

What is the expression for $S_{n,k}$ for arbitrary $n,k$?

Answer 1

$$S_{n,k}=\sum_{i=0}^{2n} (-1)^i \binom{n-1}{i} \binom{n+1}{k-i}=\sum_{i=0}^{k} (-1)^i \binom{n-1}{i} \binom{n+1}{k-i}$$ Let $[x^j] f(x)$ denote the coefficient of $x^j$ in the expansion of $f(x)$. $$\large\therefore S_{n,k}=[x^k]\ \sum_{k=0}^{\infty}\sum_{i=0}^{k} (-1)^i \binom{n-1}{i} \binom{n+1}{k-i}x^k$$$$\large=[x^k]\ \bigg(\sum_{j=0}^{\infty}(-1)^j \binom{n-1}{j}x^j\bigg)\bigg(\sum_{j=0}^{\infty}\binom{n+1}{j}x^j\bigg)$$$$\large=[x^k]\ (1-x)^{n-1}(1+x)^{n+1}=[x^k]\ (1-x^2)^{n-1}(x^2+2x+1)$$

$$\LARGE \therefore S_{n,k}=\begin{cases} (-1)^{\frac{k}{2}}\Bigg(\binom{n-1}{\frac{k}{2}} - \binom{n-1}{\frac{k}{2}-1}\Bigg)& k\text{ is even} \\ 2(-1)^{\frac{k-1}{2}}\huge\binom{n-1}{\frac{k-1}{2}} & k\text{ is odd} \end{cases}$$ $\blacksquare$

Also see Cauchy product.

Answer 2

There is a nice combinatorial solution as well. Let $[a,b]$ denote the set of integers $\{a,a+1,\dots,b\}$. You summation counts subsets of $[1,2n]$ of size $k$, except that subsets $S$ which have an even number of members in $[1,n-1]$ are counted positively, and those with an odd number of members in $[1,n-1]$ count negatively.

To evaluate this alternating sum, lets divide subsets of $[1,2n]$ into pairs $(S_1,S_2)$ where $|S_1\cap [1,n-1]|$ and $|S_2\cap [1,n-1]|$ have opposite parity. Such pairs will cancel in your summation, so can be ignored. First of all, if $1\in S$ but $n\notin S$, then $S$ can be paired with the set obtained by adding $1$ and removing $n$. Otherwise, we look at $2$ and $n+1$ and try to play the same game, then $3$ and $n+2$, and so on, ending with $n-1$ and $2n-2$.

After removing all these pairs, the remaining sets have the property that $i$ and $i+n-1$ are either both in $S$ or both not in $S$, for $i=1,\dots,n-1$. We must then break into cases based on the parity of $k$:

• If $k$ is odd, then since the elements of $S\cap [1,2n-2]$ break into pairs $(i,i+n-1)$, it follows that $S$ has exactly one element in $\{2n-1,2n\}$. There are $2$ ways to choose this last element, and $\binom{n}{(k-1)/2}$ ways to choose the elements of $S\cap [1,n-1]$ (which determines the elements of $S\cap [n,2n-2]$). This gives $2\binom{n}{(k-1)/2}$ ways, which must be multiplied by $(-1)^{(k-1)/2}$ to match the sign.

• If $k$ is even, then $S$ must have an even number of members in $\{2n-1,2n\}$. You then condition on whether $S$ contains both or neither of $\{2n-1,2n\}$, and derive a formula similarly to the last section.