Sum of $\frac{n \binom{n}{k-1}}{\binom{2 n}{k}}$

Question

Let $n$ be a positive integer. Then, \begin{align} \sum_{k=1}^{n+1} \dfrac{n \binom{n}{k-1}}{\binom{2 n}{k}}=\frac{2n+1}{n+1} . \end{align}

Note that we can rewrite $\dfrac{n \binom{n}{k-1}}{\binom{2 n}{k}}$ as $\dfrac{n!^2 k \binom{2n-k}{n-1}}{(2n)!}$ (by the standard $\dbinom{a}{b} = \dfrac{a!}{b!\left(a-b\right)!}$ formula). Thus, the question is equivalent to proving that \begin{align} \sum_{k=1}^{n+1} k \dbinom{2n-k}{n-1} = \dbinom{2n+1}{n+1} . \end{align}

Answer 1

The equality $ \sum_{k=1}^{n+1} k \binom{2n-k}{n-1} = \binom{2n+1}{n+1} $ is just a special case of $$ \sum_{k=i}^{m-j} \binom{k}{i}\binom{m-k}{j}=\binom{m+1}{i+j+1}. $$ where $i\gets1,j\gets(n-1),m\gets 2n$. For a combinatorial proof:

How many subsets of $\{1,2,\dots,m+1\}$ have size $i+j+1$?

How many such subsets contain $k+1$, and have exactly $i$ elements smaller than $k+1$?

See $\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}$ using Counting argument.

Answer 2

Proof Using Convolutions and Generating Functions

First, we show the more general result:

$$ \sum_{k=0}^{m}\binom{k}{l}\binom{m-k}{q} = \binom{m+1}{l+q+1}, \quad \text{for integers } m, l, q \ge 0. $$

Proof. $\quad$ Note that the sequence $(c_m)$ defined by $c_m=\sum_{k=0}^{m}\binom{k}{l}\binom{m-k}{q}$ is the convolution of $(a_k)$ and $(b_k),$ where $a_k=\binom{k}{l}$ and $b_k=\binom{k}{q}.$ Thus, $c_m$ is the coefficient of $z^m$ in $A(z)B(z),$ where $A(z)$ and $B(z)$ are the generating functions of $(a_k)$ and $(b_k),$ respectively. But, $A(z)=z^l/(1-z)^{l+1}$ and $B(z)=z^q/(1-z)^{q+1},$ so that $$ A(z)B(z) = \frac{z^{l+q}}{(1-z)^{l+q+2}}=\frac{1}{z}\frac{z^{l+q+1}}{(1-z)^{l+q+2}}= \frac{1}{z}\sum_{k\ge0}\binom{k}{l+q+1}z^k. $$ Finally, $$ c_m=[z^m]A(z)B(z)= \binom{m+1}{l+q+1}. \tag*{$\blacksquare$} $$

Setting $m:=2n, l:=1,$ and $q:= n-1,$ we get: $$ \sum_{k=0}^{2n}\binom{k}{1}\binom{2n-k}{n-1} = \binom{2n+1}{n+1}, $$ and it is easy to see that $\sum_{k=0}^{2n}\binom{k}{1}\binom{2n-k}{n-1} = \sum_{k=1}^{n+1}k\binom{2n-k}{n-1}.$

Answer 3

This is late, but here's an elementary solution that uses only summation by parts and the hockey stick identity.

We want to prove that \begin{equation}\label{3}\displaystyle \sum_{k=1}^{n+1}k\binom{2n-k}{n-1}= \binom{2n+1}{n+1}\end{equation}

Let \begin{align}S_{m} = \displaystyle \sum_{k=1}^{m}\binom{2n-k}{n-1} &= \displaystyle \sum_{r=n-1}^{2n-1}\binom{r}{n-1} - \displaystyle \sum_{r=n-1}^{2n-m-1}\binom{r}{n-1}\\& = \binom{2n}{n} - \binom{2n-m}{n} \end{align}

where the latter equality follows from the hockey stick identity.

Using summation by parts on $\displaystyle \sum_{k=1}^{n+1}k\binom{2n-k}{n-1}$, we get

\begin{align}\displaystyle \sum_{k=1}^{n+1}k\binom{2n-k}{n-1} &= (n+1)S_{n+1} - \displaystyle \sum_{k=1}^{n}S_{k}\\&= (n+1)\binom{2n}{n} - n\binom{2n}{n}+ \displaystyle \sum_{k=1}^{n}\binom{2n-k}{n}\\&= \binom{2n}{n}+ \displaystyle \sum_{r=n}^{2n-1}\binom{r}{n}\\&= \binom{2n}{n}+ \binom{2n}{n+1}\\&= \binom{2n+1}{n+1}\end{align}

where we used the hockey stick identity again in the second last step and Pascal's identity in the last step.