5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How can you get $${{m \choose n}} =\oint_{\verts{z} = 1}{\pars{1 + z}^{m} \over z^{n+1}}$$? $\endgroup$ – Zack Ni Jul 18 '16 at 8:46
  • 1
    $\begingroup$ @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} $\endgroup$ – Felix Marin Jul 18 '16 at 8:53
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.