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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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