Compute $\sum \binom{n}{k} \binom{n+k-1}{k} (-1)^k$

$[x^k]:f(x)$ means the coefficient of $x^k$ in the function $f(x)$. So for instance \begin{eqnarray*} \binom{n}{k}=[x^k]: (1+x)^n. \end{eqnarray*}

So for your sum we have

\begin{eqnarray*} \sum_{k=0}^n (-1)^k \binom{n}{k} \binom{n+k-1}{k} &=& [x^0]: \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{(1+x)^{n+k-1}}{x^k} \\ &=& [x^0]: (1+x)^{n-1} \left(1- \frac{(1+x)}{x} \right)^n \\ &=& [x^n]: (1+x)^{n-1} (-1)^n =\color{red}{0}. \end{eqnarray*}


Here we have the Chu-Vandermonde Identity in disguise.

We obtain for $n>0$: \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{ \binom{n}{k}\binom{n+k-1}{k} (-1)^k}\\ &=\sum_{k=0}^{n}\binom{n}{n-k}\binom{-n}{k}\tag{1}\\ &=\binom{0}{n}\tag{2}\\ &\,\,\color{blue}{=0} \end{align*}

and the claim follows.

Comment:

  • In (1) we use the binomial identities $\binom{p}{q}=\binom{p}{p-q}$ and $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

  • In (2) we apply the Chu-Vandermonde identity.


You may also use shifted Legendre polynomials. Rodrigues' formula ensures

$$P_n(2x-1)=(-1)^n\sum_{k=0}^{n}\binom{n}{k}\binom{n+k}{k}(-1)^k x^k $$ hence

$$\sum_{k=0}^{n}\binom{n}{k}\binom{n+k-1}{k}(-1)^k=\sum_{k=0}^{n}\binom{n}{k}\binom{n+k}{k}(-1)^k\frac{n}{k+n}=n(-1)^n\int_{0}^{1}P_n(2x-1)x^{n-1}\,dx $$ and the RHS is zero, since $P_n(2x-1)$ is orthogonal to any polynomial with degree less than $n$.