Prove that $\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$ 
Prove that $$\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$$

I've tried multiple things that didn't work. 
Maybe this would help
$$\sum_{k=0}^n \binom{3n-k}{2n}=\sum_{k=0}^n \binom{3n-(n-k)}{2n}=\sum_{k=0}^n \binom{2n+k}{2n}$$
 A: Choose $2n+1$ of $3n+1$ ordered items by choosing the greatest first, at position $2n+k+1$, and then choosing the remaining $2n$ items out of the $2n+k$ items less than it.
A: Your identity is a special case of the more general identity $$S(m,n) = \sum_{k=0}^n \binom{m+k}{m} = \binom{m+n+1}{m+1},$$ which you can prove by induction on $n$:  note $S(m,0) = 1 = \binom{m+1}{m+1}$.  Then observe $$\begin{align*} S(m,n+1) &= S(m,n) + \binom{m+n+1}{m} \\ 
&= \binom{m+n+1}{m+1} + \binom{m+n+1}{m} \\
&= \binom{m+n+2}{m+1} = \binom{m + (n+1) + 1}{m+1},
\end{align*}$$
hence by the induction hypothesis, the claim is proven.  Then choose $m = 2n.$
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \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{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#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}
\color{#f00}{\sum_{k = 0}^{n}{3n - k \choose 2n}} & =
\sum_{k = 0}^{n}\oint_{\verts{z} = 1}{\pars{1 + z}^{3n - k} \over  z^{2n + 1}}
\,{\dd z \over 2\pi\ic} =
\oint_{\verts{z} = 1}{\pars{1 + z}^{3n} \over  z^{2n + 1}}\sum_{k = 0}^{n}
\pars{1 \over 1 + z}^{k}\,{\dd z \over 2\pi\ic}
\\[4mm] & =
\oint_{\verts{z} = 1}{\pars{1 + z}^{3n} \over  z^{2n + 1}}
{\pars{1 + z}^{-n - 1}\,\, -\ 1 \over 1/\pars{1 + z} - 1}\,{\dd z \over 2\pi\ic} \\[4mm] & =
-\oint_{\verts{z} = 1}{\pars{1 + z}^{2n} \over  z^{2n + 2}}
\,{\dd z \over 2\pi\ic} +
\oint_{\verts{z} = 1}{\pars{1 + z}^{3n + 1} \over  z^{2n + 2}}
\,{\dd z \over 2\pi\ic}
\\[4mm] &=
-\,\overbrace{{2n \choose 2n + 1}}^{\ds{=\ 0}}\ +\ {3n + 1 \choose 2n + 1} =
{3n + 1 \choose \pars{3n + 1} - \pars{2n + 1}} =
\color{#f00}{3n + 1 \choose n}
\end{align}
A: Here is another variation. It's convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g.
\begin{align*}
\binom{n}{k}=[x^k](1+x)^n
\end{align*}

We obtain
  \begin{align*}
\sum_{k=0}^n\binom{3n-k}{2n}&=\sum_{k=0}^n\binom{3n-k}{n-k}\tag{1}\\
&=\sum_{k=0}^\infty[x^{n-k}](1+x)^{3n-k}\tag{2}\\
&=[x^n](1+x)^{3n}\sum_{k=0}^\infty\left(\frac{x}{1+x}\right)^k\tag{3}\\
&=[x^n](1+x)^{3n}\frac{1}{1-\frac{x}{1+x}}\tag{4}\\
&=[x^n](1+x)^{3n+1}\\
&=\binom{3n+1}{n}
\end{align*}

Comment:


*

*In (1) we use the binomial identity $\binom{n}{k}=\binom{n}{n-k}$.

*In (2) we apply the coefficient of operator and set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

*In (3) we use the linearity of the coefficient of operator and use the rule
\begin{align*}
[x^{p-q}]A(x)=[x^p]x^{q}A(x)
\end{align*}

*In (4) we apply the geometric series expansion.
A: Suppose we seek to evaluate
$$\sum_{k=0}^n {3n-k\choose 2n}$$
using a  different integral than  what was used by  @MarkusScheuer and
@FelixMarin. 
Introduce
$${3n-k\choose 2n} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{n-k+1}}
\frac{1}{(1-z)^{2n+1}} \; dz.$$
Observe that  this vanishes for $k\gt n$  so we may extend  the sum to
infinity, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{n+1}}
\frac{1}{(1-z)^{2n+1}} 
\sum_{k\ge 0} z^k
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{n+1}}
\frac{1}{(1-z)^{2n+2}} 
\; dz.$$
This evaluates by inspection to
$${n+2n+1\choose 2n+1} = {3n+1\choose 2n+1} = {3n+1\choose n}.$$
