Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
math.stackexchange.com/q/918/152 –  Grigory M Oct 14 '12 at 12:50

4 Answers 4

up vote 7 down vote accepted

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

share|improve this answer

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

share|improve this answer

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$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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