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

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

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.


• How can you get $${{m \choose n}} =\oint_{\verts{z} = 1}{\pars{1 + z}^{m} \over z^{n+1}}$$? – Zack Ni Jul 18 '16 at 8:46
• @ZackNi \begin{align} &\oint_{\left\vert z\right\vert = 1}{\pars{1 + z}^{m} \over z^{n + 1}}\,{\mathrm{d}z \over 2\pi\mathrm{i}} = \oint_{\left\vert z\right\vert = 1}{1 \over z^{n + 1}}\sum_{k = 0}^{m}{m \choose k}z^{k} \,{\mathrm{d}z \over 2\pi\mathrm{i}} = \sum_{k = 0}^{m}{m \choose k}\underbrace{\oint_{\left\vert z\right\vert = 1} {1 \over z^{n - k + 1}}\,{\mathrm{d}z \over 2\pi\mathrm{i}}}_{\displaystyle{\delta_{kn}}} = {m \choose n} \end{align} – Felix Marin Jul 18 '16 at 8:53

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.

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