Prove that: $\frac{(n+0)!}{0!}+\frac{(n+1)!}{1!}+...+\frac{(n+n)!}{n!}=\frac{(2n+1)!}{(n+1)!}$

Question

Prove that: $$\frac{(n+0)!}{0!}+\frac{(n+1)!}{1!}+...+\frac{(n+n)!}{n!}=\frac{(2n+1)!}{(n+1)!}$$

My work so far:

$$\frac{(n+0)!}{0!}+\frac{(n+1)!}{1!}+...+\frac{(n+n)!}{n!}=\frac{(2n+1)!}{(n+1)!}$$ $$\frac{(n+0)!}{n!0!}+\frac{(n+1)!}{n!1!}+...+\frac{(n+n)!}{n!n!}=\frac{(2n+1)!}{n!(n+1)!}$$ $$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+...+\binom{2n}{n}=\binom{2n+1}{n}$$

How to prove the last equality?

Answer 1

Try to use the following identity: $$ \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}. $$

Answer 2

First, note ${n\choose0}={n+1\choose0}$, then repeatedly use ${k\choose r}+{k\choose r+1}={k+1\choose r+1}$

Answer 3

Combinatorial proof of $$\frac{(n+0)!}{0!}+\frac{(n+1)!}{1!}+...+\frac{(n+n)!}{n!}=\frac{(2n+1)!}{(n+1)!}$$ that is, after dividing by $n!$, $$\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+...+\binom{2n}{n}=\binom{2n+1}{n+1}.$$ The RHS counts the number of $\{0,1\}$-strings of length $2n+1$ with $(n+1)$ $1$s. The LHS enumerates the same set according to the position $k$ of the last $1$ on the right: for $k=n+1,n+2,\dots, 2n+1$ they are $$\binom{k-1}{n}.$$

Answer 4

$$\sum_{r=0}^n\binom{n+r}r$$ is the coefficient of $x^n$ in $$\sum_{r=0}^n(1+x)^{n+r}$$ which is a Finite Geometric Series and is $$=(1+x)^n\cdot\dfrac{(1+x)^{n+1}-1}{1+x-1}=\dfrac{(1+x)^{2n+1}-(1+x)^n}x$$

Now the coefficient of $x^{n+1}$ in $$(1+x)^{2n+1}-(1+x)^n$$

$$=\binom{2n+1}{n+1}-0$$

Answer 5

You can calculate directly: $$\begin{align} & \frac{(n+0)!}{0!}+\frac{(n+1)!}{1!}=\frac{n!(1+n+1)}{1!}; \\ & \frac{n!(n+2)}{1!}+\frac{(n+2)!}{2!}=\frac{n!(n+2)(2+n+1)}{2!}; \\ & \cdots \\ & \frac{n!(n+2)(n+3)\cdots ((n-1)+n+1)}{(n-1)!}+\frac{(n+n)!}{n!}= \\ & \frac{n!(n+2)(n+3)\cdots (n+n+1)}{n!}=\frac{(2n+1)!}{(n+1)!}. \end{align}$$

Answer 6

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