2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ This is waiting on mods to move the answers from the old question here (one algebraic and one analytic proof). $\endgroup$ – darij grinberg Mar 27 at 15:25
  • 1
    $\begingroup$ Shouldn't you make this a community wiki post? $\endgroup$ – Don Thousand Mar 27 at 15:34
  • $\begingroup$ @DonThousand: Thought of that, but that would make the answers CW as well. $\endgroup$ – darij grinberg Mar 27 at 15:39
  • $\begingroup$ 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}$$ $\endgroup$ – Thomas Andrews Mar 27 at 15:43
  • 2
    $\begingroup$ @darijgrinberg You should give a link (in the question) to the deleted question to help prevent folks wasting time on composing dupe answers. $\endgroup$ – Bill Dubuque Mar 27 at 15:45
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for your answer!! $\endgroup$ – Young Nov 4 '18 at 0:28
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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}

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.