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

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}

• This is waiting on mods to move the answers from the old question here (one algebraic and one analytic proof). – darij grinberg Mar 27 at 15:25
• Shouldn't you make this a community wiki post? – Don Thousand Mar 27 at 15:34
• @DonThousand: Thought of that, but that would make the answers CW as well. – darij grinberg Mar 27 at 15:39
• Well, you get $$\dfrac{n!^2 k \binom{2n-k}{n-1}}{(2n)!}=\frac{k\binom{2n-k}{n-1}}{\binom{2n}{n}}.$$ So you really need $$\sum_{k=1}^{n+1}k\binom{2n-k}{n-1}=\frac{2n+1}{n+1}\binom{2n}{n}$$ – Thomas Andrews Mar 27 at 15:43
• @darijgrinberg You should give a link (in the question) to the deleted question to help prevent folks wasting time on composing dupe answers. – Bill Dubuque Mar 27 at 15:45

Starting from

$$n\sum_{k=1}^{n+1} {2n\choose k}^{-1} {n\choose k-1}$$

we find

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

This is

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

Now when $$k\gt n+1$$ there is no contribution to the coefficient extractor and we get

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

• Thank you for your answer!! – Young Nov 4 '18 at 0:28

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


• nice solution +1, demonstrates the properties of gamma and beta functions, binomial theorem and change of variables in integral. – farruhota Apr 5 at 17:07
• @farruhota Thanks. – Felix Marin Apr 8 at 22:02

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