How to prove: $\sum_{k=0}^{n}~(-1)^k{n \choose k} {2n-2k \choose n+m-1}=2^{n-m+1} {n \choose m-1}$

Question

The sum $$S_{n,m} =\sum_{k=0}^{n}~ (-1)^k{n \choose k} {2n-2k\choose n+m-1}$$ can be evaluated by Mathematica for $m=0,1,2,3$ in simple closed forms. But in general $$ S_{n,m}=2^{n-m+1}{n \choose m-1}~~~(*).$$ The question is how to prove (*) by hand?

Answer 1

We have

$$\sum_{k=0}^n (-1)^k {n\choose k} {2n-2k\choose n+m-1} = [z^{n+m-1}] (1+z)^{2n} \sum_{k=0}^n (-1)^k {n\choose k} (1+z)^{-2k} \\ = [z^{n+m-1}] (1+z)^{2n} \left(1-\frac{1}{(1+z)^2}\right)^n \\ = [z^{n+m-1}] ((1+z)^2-1)^{n} = [z^{n+m+1}] (2z+z^2)^{n} \\= [z^{n+m-1}] z^{n} (z+2)^{n} = [z^{m-1}] (z+2)^n = {n\choose m-1} \times 2^{n-m+1}.$$

The last coefficient extractor returns zero when $m-1\lt 0,$ as does the binomial coefficient.

Answer 2

The answer is simple (but my solution below is not...). Suppose $n\geqslant m-1$ (otherwise the sum is trivially zero). Then $S_{n,m}$ is equal to the coefficient of $x^{2n}$ in the power series $A(x)B(x)$, where \begin{align}A(x)&:=\sum_{k=0}^{n}(-1)^k\binom{n}{k}x^{2k}=(1-x^2)^n,\\B(x)&:=\sum_{k=0}^{\infty}\binom{2k}{n+m-1}x^{2k}=\frac12\big(C(x)+C(-x)\big),\\C(x)&:=\sum_{k=0}^{\infty}\binom{k}{n+m-1}x^k=\frac{x^{n+m-1}}{(1-x)^{n+m}},\end{align} thus \begin{align}S_{n,m}&=\frac12[x^{2n}](1-x^2)^n\left(\frac{x^{n+m-1}}{(1-x)^{n+m}}+\frac{(-x)^{n+m-1}}{(1+x)^{n+m}}\right)\\&=\frac12[x^{n-m+1}]\frac{(x+1)^{n+m}-(x-1)^{n+m}}{(1-x^2)^m}.\end{align} Using Cauchy's integral formula, we have $$S_{n,m}=\frac{1}{4\pi i}\oint_{|z|=\epsilon}\frac{(z+1)^{n+m}-(z-1)^{n+m}}{z^{n-m+2}(1-z^2)^m}\,dz$$ where $0<\epsilon<1$; substituting $z=1/w$, we get $$S_{n,m}=\frac{1}{4\pi i}\oint_{|w|=1/\epsilon}\frac{(1+w)^{n+m}-(1-w)^{n+m}}{(w^2-1)^m}\,dw,$$ which is easily computed using residues (at $w=\pm 1$, turn out to be equal). The result is $$\color{blue}{S_{n,m}=2^{n-m+1}\binom{n}{m-1}}.$$

Answer 3

To sum $$S_{n.m}=\sum_{k=0}^{n} (-1)^k {n \choose k} {2n-2k\choose n+m-1}, m=0,1,2 ~~~~(1)$$

$$(1-x^2)^n= \sum_{k=0}^{n} (-1)^k {n \choose k} (x)^{2k}~~~~~~~(2)$$ $$(1-x)^{-n-m} =\sum_{j=0}^{\infty} {j+n+m-1, \choose n+m-1} x^j~~~~(3)$$ Multiply (1) and (2) to write $$\frac{(1+x)^n}{(1-x)^m}=\sum_{j=0}^n \sum_{k=0}^{n} (-1)^k {n \choose k}{j+n+m-1 \choose n+m-1} x^{j+2k}~~~~(4)$$ In oder that (4) resembles with (1) , we set $j+n+m-1=2n-2k \implies j=n-2k-m+1\implies j+2k=n-m+1$. Thus $$S_{n.m}=[x^{n-m+1}] \frac{1+x)^n}{(1-x)^m}$$. It then follows that $$S_{n.0}=[x^{n+1}] ~(1+x)^n=0$$ $$S_{n,1}=[x^n] ~ \frac{(1+x)^n}{(1-x)}=[x^n]~ (1+x)^n (1-x)^{-1}={n \choose n}+{n \choose ,n-1}+{n \choose n-2}+...+{n \choose 0}=2^n.$$ $$S_{n,2}=[x^{n-1}] ~ \frac{(1+x)^{n-1}}{(1-x)^2}=[x^{n-1}]~ (1+x)^n (1-x)^{-2}=0{n \choose n}+1{n \choose ,n-1}+2{n \choose n-2}+...+n{n \choose 0}=n2^{n-1}.$$ In (4), we use $$(1-x)^{-m}=\sum_{k=0}^{\infty} {-m \choose k} x^k=\sum_{k=0}^{\infty} (-1)^k {m+k-1 \choose k} x^k$$ The generalization is that the sum $$S_{n,m}=\sum_{k=0}^n (-1)^k {-m \choose k} {n \choose n-k-m+1}=\sum_{k=0}^{n} {m+k-1 \choose k}{n \choose m+k-1}= \sum_{k=0}^{n} {n \choose k} {n-k \choose m-1}=\sum_{k=0}^{n} {n \choose n-k} {n-k \choose m-1}={n \choose m-1} \sum_{k=0}^n {n-m+1 \choose k}={n \choose m-1}2^{n-m+1} $$