Calculate $\sum_{0 \le k } \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{k+1}$

Question

Calculate $$\sum_{0 \le k } \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{k+1}$$

My approach

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

But unfortunately I have stucked, I don't know how I can finish that...
The main obstacle which I see is $$\binom{- 1 - n}{k} $$ is looks so dangerous because $- 1 - n<0$

Answer 1

Starting from

$$\sum_{k=0}^n {n+k\choose 2k} {2k\choose k} \frac{(-1)^k}{k+1}$$

for a self-contained answer we observe that

$${n+k\choose 2k} {2k\choose k} = \frac{(n+k)!}{(n-k)! \times k! \times k!} = {n+k\choose k} {n\choose k}$$

so we find

$$\sum_{k=0}^n {n+k\choose k} {n\choose k} \frac{(-1)^k}{k+1}$$

which is

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

The coefficient extractor controls the range (with $k\gt n$ we will always have $[z^n] (1+z)^{n+1} z^k = 0$) and we may continue by extending $k$ to infinity:

$$\frac{1}{n+1} [z^n] (1+z)^{n+1} \sum_{k\ge 0} {n+k\choose k} z^k (-1)^k \\ = \frac{1}{n+1} [z^n] (1+z)^{n+1} \frac{1}{(1+z)^{n+1}} = \frac{1}{n+1} [z^n] 1 = [[n=0]].$$

Answer 2

Your approach is also fine. Starting with the last line we obtain for $n\geq 0$:

\begin{align*} \color{blue}{\frac{1}{n+1}}&\color{blue}{\sum_{k\geq 0}\binom{-n-1}{k}\binom{n+1}{k+1}}\tag{1}\\ &=\frac{1}{n+1}\sum_{k=0}^n\binom{-n-1}{k}\binom{n+1}{n-k}\tag{2}\\ &=\frac{1}{n+1}\binom{0}{n}\tag{3}\\ &\,\,\color{blue}{=[[n=0]]}\tag{4} \end{align*}

Comment:

• In (1) we note $\binom{-n-1}{k}$ is a valid expression following the more general definition of binomial coefficients for $\alpha\in\mathbb{C},k\in\mathbb{Z}$:

\begin{align*} \binom{\alpha}{k}= \begin{cases} \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}&\qquad k\geq 0\\ 0&\qquad k<0 \end{cases} \end{align*}

$\qquad$This definition is given for instance as (5.1) in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.

• In (2) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$. We also set the upper limit of the sum to $n$, noting that $\binom{n+1}{n-k}=0$ if $k>n$.

• In (3) we apply Chu-Vandermonde's identity.

• In (4) we use Iverson brackets as compact notation.

Answer 3

$\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[10px,#ffd]{\sum_{0\ \leq\ k}{n + k \choose 2k}{2k \choose k}{\pars{-1}^{k} \over k + 1}} = \sum_{k\ =\ 0}^{\infty}{n + k \choose n - k}\bracks{{-1/2 \choose k} \pars{-4}^{k}}\pars{-1}^{k}\int_{0}^{1}t^{k}\,\dd t \\[5mm] = &\ \int_{0}^{1}\sum_{k\ =\ 0}^{\infty}{-1/2 \choose k} \braces{\bracks{z^{n - k}}\pars{1 + z}^{n + k}}\pars{4t}^{k}\,\dd t \\[5mm] = &\ \bracks{z^{n}}\pars{1 + z}^{n} \int_{0}^{1}\sum_{k\ =\ 0}^{\infty}{-1/2 \choose k} \bracks{4z\pars{1 + z}t}^{k}\,\dd t \\[5mm] = &\ \bracks{z^{n}}\pars{1 + z}^{n}\ \underbrace{\int_{0}^{1}\bracks{1 + 4z\pars{1 + z}t}^{\, -1/2}\,\,\dd t} _{\ds{1 \over 1 + z}}\ =\ \bracks{z^{n}}\pars{1 + z}^{n - 1} = \bbx{\large \delta_{n0}} \end{align}