An interesting Sum involving Binomial Coefficients

Question

How would you evaluate

$$\sum _{ k=1 }^{ n } k\left( \begin{matrix} 2n \\ n+k \end{matrix} \right) $$

I tried using Vandermonde identity but I can't seem to nail it down.

Answer 1

Let $$ S_n = \sum_{k=1}^{n} k\binom{2n}{n+k}=(2n)!\cdot\sum_{k=1}^{n}\frac{k}{(n+k)!(n-k)!}.\tag{1}$$ We have: $$\begin{eqnarray*} 2S_n &=& (2n)!\cdot \sum_{k=1}^{n}\frac{(n+k)-(n-k)}{(n+k)!(n-k)!}\\ &=& (2n)!\cdot \sum_{k=1}^{n}\left(\frac{1}{(n+k-1)!(n-k)!}-\frac{1}{(n+k)!(n-k-1)!}\right)\\&=&(2n)\cdot \sum_{k=1}^{n}\left(\binom{2n-1}{n+k-1}-\binom{2n-1}{n+k}\right)\tag{2}\end{eqnarray*} $$ but the last sum is a telescopic sum, that leads to:

$$ 2S_n = \color{red}{n\binom{2n}{n}}.\tag{3} $$

Answer 2

$$ \begin{align} \sum_{k=1}^nk\binom{2n}{n+k} &=\sum_{k=1}^n(n+k)\binom{2n}{n+k}-\sum_{k=1}^nn\binom{2n}{n+k}\tag{1}\\ &=\sum_{k=1}^n2n\binom{2n-1}{n+k-1}-\sum_{k=1}^nn\binom{2n}{n+k}\tag{2}\\ &=n2^{2n-1}-\frac n2\left(2^{2n}-\binom{2n}{n}\right)\tag{3}\\ &=\frac n2\binom{2n}{n}\tag{4} \end{align} $$ Explanation:
$(1)$: $k=(n+k)-n$
$(2)$: $k\binom{n}{k}=n\binom{n-1}{k-1}$
$(3)$: $\sum_{k=0}^n\binom{n}{k}=2^n$. The red parts below are in $(2)$
$\phantom{(3):}$$\underbrace{\binom{2n-1}{0}+\binom{2n-1}{1}+\cdots+\binom{2n-1}{n-1}}_{\text{half of $2^{2n-1}$}}+\underbrace{\color{#C00000}{\binom{2n-1}{n}+\binom{2n-1}{n+1}+\cdots+\binom{2n-1}{2n-1}}}_{\text{half of $2^{2n-1}$}}=2^{2n-1}$
$\phantom{(3):}$$\underbrace{\binom{2n}{0}+\binom{2n}{1}+\cdots+\binom{2n}{n-1}}_{\text{half of $2^{2n}-\binom{2n}{n}$}}+\binom{2n}{n}+\underbrace{\color{#C00000}{\binom{2n}{n+1}+\binom{2n}{n+2}+\cdots+\binom{2n}{2n}}}_{\text{half of $2^{2n}-\binom{2n}{n}$}}=2^{2n}$
$(4)$: cancel

Answer 3

A different computational approach:

$$\begin{align*} \sum_{k=1}^nk\binom{2n}{n+k}&=\sum_{k=1}^nk\binom{2n}{n-k}\\ &=\sum_{k=0}^{n-1}(n-k)\binom{2n}k\\ &=n\sum_{k=0}^{n-1}\binom{2n}k-\sum_{k=0}^{n-1}k\binom{2n}k\\ &=n\sum_{k=0}^{n-1}\binom{2n}k-2n\sum_{k=0}^{n-1}\binom{2n-1}{k-1}\\ &=n\sum_{k=0}^{n-1}\binom{2n}k-2n\sum_{k=0}^{n-2}\binom{2n-1}k\\ &=n\sum_{k=0}^{n-1}\left(\binom{2n-1}{k-1}+\binom{2n-1}k\right)-2n\sum_{k=0}^{n-2}\binom{2n-1}k\\ &=n\sum_{k=0}^{n-2}\binom{2n-1}k+n\sum_{k=0}^{n-1}\binom{2n-1}k-2n\sum_{k=0}^{n-2}\binom{2n-1}k\\ &=n\sum_{k=0}^{n-1}\binom{2n-1}k-n\sum_{k=0}^{n-2}\binom{2n-1}k\\ &=n\binom{2n-1}{n-1} \end{align*}$$

Note that

$$\binom{2n}n=\frac{2n}n\binom{2n-1}{n-1}\;,$$

so

$$n\binom{2n-1}{n-1}=\frac{n}2\binom{2n}n\;,$$

and this answers agrees with the others already posted.

Answer 4

Permit me to contribute an algebraic proof.

Suppose we seek to evaluate $$\sum_{k=0}^n k {2n\choose n+k} = \sum_{k=0}^n (n-k) {2n\choose 2n-k} = \sum_{k=0}^n (n-k) {2n\choose k} \\ = n \frac{1}{2} \left(2^{2n} - {2n\choose n}\right) + n {2n\choose n} - \sum_{k=0}^n k {2n\choose k} \\ = n \frac{1}{2} \left(2^{2n} + {2n\choose n}\right) - \sum_{k=0}^n k {2n\choose k} .$$

Now we have $$\sum_{k=0}^n k {2n\choose k} = \sum_{k=1}^n k {2n\choose k} = 2n \sum_{k=1}^n {2n-1\choose k-1} \\ = 2n \sum_{k=0}^{n-1} {2n-1\choose k} = 2n \frac{1}{2} 2^{2n-1}.$$

Collecting everything we obtain $$n \frac{1}{2} \left(2^{2n} + {2n\choose n}\right) - n \frac{1}{2} 2^{2n} = \frac{1}{2} n {2n\choose n}.$$

Remark. This would appear to be the technique used by @robjohn.

Answer 5

The following proof uses complex variable techniques and improves the elementary one I posted earlier. It serves to demonstrate the method even though it requires somewhat more of an effort.

Suppose we seek to evaluate $$\sum_{k=1}^n k {2n\choose n+k}.$$

Introduce $${2n\choose n+k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \frac{1}{(1-z)^{n+k+1}} \; dz.$$

Observe that this is zero when $k\gt n$ so we may extend $k$ to infinity to obtain for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^{n+1}} \sum_{k\ge 1} k \frac{z^k}{(1-z)^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^{n+1}} \frac{z/(1-z)}{(1-z/(1-z))^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} \frac{1}{(1-z)^{n}} \frac{1}{(1-2z)^2} \; dz.$$

Now put $z(1-z)=w$ so that (observe that with $w=z+\cdots$ the image of $|z|=\epsilon$ with $\epsilon$ small is another closed circle-like contour which makes one turn and which we may certainly deform to obtain another circle $|w|=\gamma$)

$$z = \frac{1-\sqrt{1-4w}}{2} \quad\text{and}\quad (1-2z)^2 = 1-4w$$

and furthermore $$dz = -\frac{1}{2} \times \frac{1}{2} \times (-4) \times (1-4w)^{-1/2} \; dw = (1-4w)^{-1/2} \; dw$$

to get for the integral $$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^n} \frac{1}{1-4w} (1-4w)^{-1/2} \; dw = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^n} \frac{1}{(1-4w)^{3/2}} \; dw.$$

This evaluates by inspection to $$4^{n-1} {n-1+1/2\choose n-1} = 4^{n-1} {n-1/2\choose n-1} = \frac{4^{n-1}}{(n-1)!} \prod_{q=0}^{n-2} (n-1/2-q) \\ = \frac{2^{n-1}}{(n-1)!} \prod_{q=0}^{n-2} (2n-2q-1) = \frac{2^{n-1}}{(n-1)!} \frac{(2n-1)!}{2^{n-1} (n-1)!} \\ = \frac{n^2}{2n} {2n\choose n} = \frac{1}{2} n {2n\choose n}.$$

Here the mapping from $z=0$ to $w=0$ determines the choice of square root. For the conditions on $\epsilon$ and $\gamma$ we have that for the series to converge we require $|z/(1-z)|\lt 1$ or $\epsilon/(1-\epsilon) \lt 1$ or $\epsilon \lt 1/2.$ The closest that the image contour of $|z|=\epsilon$ comes to the origin is $\epsilon-\epsilon^2$ so we choose $\gamma \lt \epsilon-\epsilon^2$ for example $\gamma = \epsilon^2-\epsilon^3.$ This also ensures that $\gamma \lt 1/4$ so $|w|=\gamma$ does not intersect the branch cut $[1/4,\infty)$ (and is contained in the image of $|z|=\epsilon$). For example $\epsilon = 1/3$ and $\gamma = 2/27$ will work.