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

Question

How can we study a series like this :

$\sum_{k=0}^{n} \binom{n}{k}\binom{n+k-1}{k} (-1)^k$.

I thought about consider $S(x) = \sum_{k=0}^{n} \binom{n}{k}\binom{n+k-1}{k} x^k$. But the only one I've found is hypergeometric function. It's hard to analyze.

Hope there are more combinatorical ideas for finding such series.

Any hints? Maybe generating functions?

Answer 1

$[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*}

Answer 2

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

Answer 3

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.

Answer 4

Using Vandermonde's Identity and Negative Binomial Coefficients $$ \begin{align} \sum_k\binom{n}{k}\binom{n+k-1}{k}(-1)^k &=\sum_k\binom{n}{n-k}\binom{-n}{k}\\ &=\binom{0}{n}\\[9pt] &=[n=0] \end{align} $$ Note that $\binom{-1}{0}=1$.

---

Using Finite Differences

For $n\ge1$, $$ \sum_k\binom{n}{k}\binom{n+k-1}{k}(-1)^k =\sum_k(-1)^k\binom{n}{k}\binom{n+k-1}{n-1} $$ which is an order $n$ repeated difference of a degree $n-1$ polynomial, and therefore, vanishes.

Answer 5

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[15px,#ffd]{\sum_{k = 0}^{n}{n \choose k} {n + k - 1 \choose k}\pars{-1}^{k}} \\[5mm] = &\ \sum_{k = 0}^{n}{n \choose k} \bracks{{-\bracks{n + k - 1} + k - 1 \choose k}\pars{-1}^{k}}\pars{-1}^{k} \\[5mm] = &\ \sum_{k = 0}^{n}{n \choose k}{-n \choose k}\ =\ \bbox[15px,#ffc,border:1px solid navy]{\delta_{n0}} \end{align}