Vrftsjtryk

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

$$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)$.
$$largetherefore 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^jbigg)bigg(sum_{j=0}^{infty}binom{n+1}{j}x^jbigg)$$$$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)& ktext{ is even} \
2(-1)^{frac{k-1}{2}}hugebinom{n-1}{frac{k-1}{2}} & ktext{ is odd}
end{cases}$$
$blacksquare$

Also see Cauchy product.

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_1cap [1,n-1]|$ and $|S_2cap [1,n-1]|$ have opposite parity. Such pairs will cancel in your summation, so can be ignored. First of all, if $1in S$ but $nnotin 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 $Scap [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 $Scap [1,n-1]$ (which determines the elements of $Scap [n,2n-2]$). This gives $2binom{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.