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

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.

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

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

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}

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