1
$\begingroup$

In a combinatorial math problem, I found the need to have a short form for $\sum_{k=1}^n {2n-k \choose n}$. I searched it on Wolfram|Alpha and it gave me the result $\frac{2n{2n-1 \choose n}}{n+1}$ which indeed solves my problem, but no steps were available and I wasn't able to find a way to prove it by myself. I tried by writing the sum term by term and using ${n \choose k} = {n! \over k!(n-k)!}$ but it overcomplicated everything. Could anyone help me with this?

I'm sorry if this is a duplicate. As far as I searched, I haven't found any question regarding this sum, but maybe I haven't searched enough.

$\endgroup$
5
$\begingroup$

You can use the Hockey-stick identity. Using $\binom{i}{j}+\binom{i}{j+1} =\binom{i+1}{j+1}$ recursively, we have $$\begin{align*} \sum_{k=1}^n {2n-k \choose n} &= \color{red}{\binom{n}{n}}+\binom{n+1}{n}+\cdots+\binom{2n-1}{n}\\ &=\color{red}{\binom{n+1}{n+1}}+\binom{n+1}{n}+\cdots+\binom{2n-1}{n} \\&=\binom{n+2}{n+1}+\binom{n+2}{n}+\cdots+\binom{2n-1}{n} \\&=\binom{n+3}{n+1}+\binom{n+3}{n}+\cdots+\binom{2n-1}{n} \\&=\cdots\\&=\binom{2n}{n+1} =\frac{2n\binom{2n-1}{n}}{n+1}. \end{align*}$$

$\endgroup$
2
$\begingroup$

$\displaystyle \sum_{k=1}^{n}\binom{2n-k}{n}$ is the coefficient of $x^n$ in the expansion of $\displaystyle \sum_{k=1}^n(1+x)^{2n-k}$.

Note that $\displaystyle \sum_{k=1}^n(1+x)^{2n-k}=\frac{(1+x)^n[(1+x)^n-1]}{(1+x)-1}=\frac{(1+x)^{2n}-(1+x)^n}{x}$.

Therefore, $\displaystyle \sum_{k=1}^{n}\binom{2n-k}{n}=\binom{2n}{n+1}=\frac{(2n)!}{(n+1)!(n-1)!}=\frac{2n}{n+1}\binom{2n-1}{n}$.

$\endgroup$
1
$\begingroup$

By substituting $k\mapsto n-k$, we get $$ \sum_{k=1}^n\binom{2n-k}{n}=\sum_{k=0}^{n-1}\binom{n+k}{n}\tag1 $$

We can derive a closed form for a generalization of the sum on the right hand side of $(1)$ using the expansion $$ \sum_{k=0}^\infty\binom{n+k}{n}x^k=(1-x)^{-n-1}\tag2 $$ Taking the product of $(2)$ for two different exponents, we get $$ \begin{align} (1-x)^{-n-1}(1-x)^{-m-1} &=\sum_{k=0}^\infty\binom{n+k}{n}x^k\sum_{j=0}^\infty\binom{m+j}{m}x^j\tag3\\ &=\sum_{k=0}^\infty\sum_{j=0}^k\binom{n+k-j}{n}\binom{m+j}{m}x^k\tag4\\ (1-x)^{-n-m-2} &=\sum_{k=0}^\infty\binom{n+m+k+1}{n+m+1}x^k\tag5 \end{align} $$ Equating the coefficients of $x^k$ in $(3)$ and $(4)$, we get $$ \bbox[5px,border:2px solid #C0A000]{\sum_{j=0}^k\binom{n+k-j}{n}\binom{m+j}{m}=\binom{n+m+k+1}{n+m+1}}\tag6 $$ Substituting $$ \begin{matrix} n&\to&0\\ m&\to&n\\ k&\to&n-1\\ j&\to&k\\ \end{matrix}\tag7 $$ into $(6)$ yields $$ \sum_{k=0}^{n-1}\binom{0+n-1-k}{0}\binom{n+k}{n}=\binom{0+n+n}{0+n+1}\tag8 $$ which evaluates to $$ \sum_{k=0}^{n-1}\binom{n+k}{n}=\binom{2n}{n+1}\tag9 $$ Applying $(9)$ to $(1)$ yields $$ \begin{align} \sum_{k=1}^n\binom{2n-k}{n} &=\binom{2n}{n+1}\tag{10}\\[6pt] &=\frac{2n}{n+1}\binom{2n-1}{n}\tag{11} \end{align} $$

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

$\ds{\sum_{k = 1}^{n}{2n - k \choose n} = {2n{2n - 1 \choose n} \over n + 1}:\ {\LARGE ?}}$.

\begin{align} &\bbox[10px,#ffd]{\sum_{k = 1}^{n}{2n - k \choose n}} = \sum_{k = 1}^{\infty}\overbrace{2n - k \choose n - k}^{\ds{Symmetry}} \ =\ \sum_{k = 1}^{\infty}\overbrace{{-n - 1 \choose n - k} \pars{-1}^{n - k}}^{\ds{Negation}} \\[5mm]= &\ \sum_{k = 1}^{\infty} \pars{-1}^{n - k}\bracks{z^{n - k}}\pars{1 + z}^{-n - 1} = \pars{-1}^{n}\bracks{z^{n}}\pars{1 + z}^{-n - 1} \sum_{k = 1}^{\infty}\pars{-z}^{k} \\[5mm] = &\ \pars{-1}^{n}\bracks{z^{n}}\pars{1 + z}^{-n - 1}\, {-z \over 1 - \pars{-z}} = \pars{-1}^{n + 1}\bracks{z^{n - 1}}\pars{1 + z}^{-n - 2} \\[5mm] & = \pars{-1}^{n + 1}{-n - 2 \choose n - 1} = \pars{-1}^{n + 1}{2n \choose n - 1}\pars{-1}^{n - 1} = \bbx{2n \choose n - 1} \\[5mm] = &\ {\pars{2n}\pars{2n - 1}! \over \pars{n - 1}!\pars{n + 1}n!} = \bbx{{2n{2n - 1 \choose n} \over n + 1}} \end{align}

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