9
$\begingroup$

The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one would arrive at this answer.

My progress so far has been limited. I have mostly been trying to see if I can somehow relate the sum to $$\sum_{k=0}^{3n}\binom{3n}{k}=8^n$$ but I'm not getting very far. I have also tried to write it out in factorial form, but that hasn't helped me much either.

How would I arrive at the explicit formula?

$\endgroup$
10
$\begingroup$

$$f(x)=\sum_0^{3n}{3n\choose r}x^r=(1+x)^{3n}$$ Now let $a,b$ be the nonreal third roots of 1, and evaluate $$f(1)+f(a)+f(b)$$

$\endgroup$
6
$\begingroup$

It can be proved fairly straightforwardly by induction.

Let $S_0(n)=\sum_{k\ge 0}\binom{3n}{3k}$, $S_1(n)=\sum_{k\ge 0}\binom{3n}{3k+1}$, and $S_2(n)=\sum_{k\ge 0}\binom{3n}{3k+2}$; then $$S_0(n)+S_1(n)+S_2(n)=\sum_{k\ge 0}\binom{3n}k=2^{3n}=8^n\;.$$

Now

$$\begin{align*} S_0(n)&=\sum_{k\ge 0}\binom{3n}{3k}\\ &=\sum_{k\ge 0}\left(\binom{3n-3}{3k-3}+3\binom{3n-3}{3k-2}+3\binom{3n-3}{3k-1}+\binom{3n-3}{3k}\right)\\ &=\sum_{k\ge 0}\left(\binom{3n-3}{3k-3}+\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)\\ &\qquad\qquad+\sum_{k\ge 0}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}+\binom{3n-3}{3k}\right)\\ &\qquad\qquad+\sum_{k\ge 0}\left(\binom{3n-3}{3k-2}+\binom{3n-3}{3k-1}\right)\\ &=S_0(n-1)+S_1(n-1)+S_2(n-1)\\ &\qquad\qquad+S_0(n-1)+S_1(n-1)+S_2(n-1)\\ &\qquad\qquad+S_1(n-1)+S_2(n-1)\\ &=3\cdot8^{n-1}-S_0(n-1)\\ &=3\cdot8^{n-1}-\frac{8^{n-1}+2(-1)^{n-1}}3\qquad\qquad\text{by the induction hypothesis}\\ &=\frac{8^n-2(-1)^{n-1}}3\\ &=\frac{8^n+2(-1)^n}3\;. \end{align*}$$

$\endgroup$
6
$\begingroup$

$\newcommand{\+}{^{\dagger}} \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{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $$ \mbox{Note that}\quad\sum_{k = 0}^{n}{3n \choose 3k} =\sum_{k = 0}^{\infty}{3n \choose 3k} $$

\begin{align} &\color{#c00000}{\sum_{k = 0}^{n}{3n \choose 3k}}= \sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{3n} \over z^{3k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{3n} \over z} \sum_{k = 0}^{\infty}\pars{1 \over z^{3}}^{k}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{3n} \over z} {1 \over 1 - 1/z^{3}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1} {z^{2}\pars{1 + z}^{3n} \over z^{3} - 1}\,{\dd z \over 2\pi\ic} \end{align}

The integrand has three simple poles inside the contour: $\quad\ds{z_{m} \equiv \expo{2m\pi\ic/3}\,,\quad m = -1,0,1}$: \begin{align} &\color{#c00000}{\sum_{k = 0}^{n}{3n \choose 3k}}= \sum_{m = -1}^{1}\lim_{z \to z_{m}} \bracks{\pars{z - z_{m}}\,{z^{2}\pars{1 + z}^{3n} \over z^{3} - 1}} =\sum_{m = -1}^{1}{z_{m}^{2}\pars{1 + z_{m}}^{3n} \over 3z_{m}^{2}} \\[5mm]&={1 \over 3}\sum_{m = -1}^{1}\pars{1 + \expo{2m\pi\ic/3}}^{3n} ={1 \over 3}\sum_{m = -1}^{1}\expo{mn\pi\ic} \pars{\expo{-m\pi\ic/3} + \expo{m\pi\ic/3}}^{3n} \\[5mm]&={8^{n} \over 3}\sum_{m = -1}^{1} \pars{-1}^{mn}\cos^{3n}\pars{m\,{\pi \over 3}} \\[5mm]&={8^{n} \over 3}\bracks{\pars{-1}^{-n}\cos^{3n}\pars{-\,{\pi \over 3}} + 1 + \pars{-1}^{n}\cos^{3n}\pars{\pi \over 3}} ={8^{n} \over 3}\bracks{1 + 2\pars{-1}^{n}\pars{\half}^{3n}} \\[5mm]&={8^{n} \over 3}\bracks{1 + {2\pars{-1}^{n} \over 8^{n}}} \end{align}

$$ \color{#66f}{\large\sum_{k = 0}^{n}{3n \choose 3k} ={8^{n} + 2\pars{-1}^{n} \over 3}} $$

$\endgroup$
4
$\begingroup$

I'll try to give a more detailed version of Gerry Myerson's hint.

If $S$ is your sum then you have $$3S=(1+1)^{3n}+(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n}.$$ (To get this observe which terms get cancelled. If you are not familiar with this way of writing complex numbers, see Wikipedia.)

Now we want to simplify $(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n}$. We notice (by a direct computation - it helps if you draw a picture) that $1+e^{i\frac{2\pi}3}=e^{i\frac\pi3}$ and $1+e^{i\frac{2\pi}3}=e^{-i\frac\pi3}$. $$(1+e^{i\frac{2\pi}3})^{3n}+(1+e^{-i\frac{2\pi}3})^{3n} = (e^{i\frac\pi3})^{3n}+(e^{-i\frac\pi3})^{3n}=e^{in\pi}+e^{-in\pi}=(e^{i\pi})^n+(e^{-i\pi})^n.$$ Since $e^{i\pi}=e^{-i\pi}=-1$, you get $$3S=2^{3n}+2(-1)^n=8^n+2(-1)^n.$$

The trick is very similar to the using $(1+1)^n+(1-1)^n$ to get the sum of even binomial coefficients, see this question: Evaluate $ \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{2k}+\cdots$

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