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

$$\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} \sum_{k = 1}^{n + 1}{n{n \choose k - 1} \over {2n \choose k}} & = n\sum_{k = 0}^{n}{{n \choose k} \over {2n \choose k + 1}} \\[5mm] & = n\sum_{k = 0}^{n}{n \choose k} {1 \over \pars{2n}!/\bracks{\pars{k + 1}!\pars{2n - k - 1}!}} \\[5mm] & = n\pars{2n + 1}\sum_{k = 0}^{n} {n \choose k}{\Gamma\pars{k + 2}\Gamma\pars{2n - k}! \over \Gamma\pars{2n + 2}} \\[5mm] & = n\pars{2n + 1}\sum_{k = 0}^{n} {n \choose k}\int_{0}^{1} t^{k + 1}\pars{1 - t}^{2n - k - 1}\,\dd t \\[5mm] & = n\pars{2n + 1}\int_{0}^{1}\pars{1 - t}^{2n}\, {t \over 1 - t}\sum_{k = 0}^{n}{n \choose k} \pars{t \over 1 - t}^{k}\,\dd t \\[5mm] & = n\pars{2n + 1}\int_{0}^{1}\pars{1 - t}^{2n - 1}\, t \pars{1 + {t \over 1 - t}}^{n}\,\dd t \\[5mm] & = n\pars{2n + 1}\int_{0}^{1}t\, \pars{1 - t}^{n - 1}\,\dd t \\[5mm] & = n\pars{2n + 1}\int_{0}^{1}\pars{1 - t}\,t^{n - 1}\,\dd t \\[5mm] & = n\pars{2n + 1}\pars{{1 \over n} - {1 \over n +1}} = \bbx{2n + 1 \over n + 1} \end{align}

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