Finding $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Question

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$

I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a multiple of $6$.

Answer 1

This technique is known as the Roots of Unity Filter. See this related question.

Note that $(1+x)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}x^k$. Let $\omega = e^{i2\pi/3}$. Then, we have:

$(1+1)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}1^k$

$(1+\omega)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^k$

$(1+\omega^2)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^{2k}$

Add these three equations together to get $\displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}(1+\omega^k+\omega^{2k}) = 2^n+(1+\omega)^n+(1+\omega^2)^n$

You can see that $1+\omega^k+\omega^{2k} = 3$ if $k$ is a multiple of $3$ and $0$ otherwise.

Thus, $\displaystyle\sum_{m = 0}^{\lfloor n/3 \rfloor}\dbinom{n}{3m} = \dfrac{1}{3}\left[2^n+(1+\omega)^n+(1+\omega^2)^n\right]$

Now, simplify this.

Answer 2

Here's a method that doesn't (explicitly) involve complex numbers.

Let $A_n=\sum_k \binom{n}{3k}$, $B_n=\sum_k \binom{n}{3k+1}$, $C_n=\sum_k \binom{n}{3k+2}$.

Then $A_n+B_n+C_n=2^n$ by the binomial theorem. Moreover, Pascal's identity implies the following: $$ \begin{eqnarray} A_n&=&A_{n-1} + C_{n-1} =2^{n-1}-B_{n-1} \\ B_n&=&B_{n-1} + A_{n-1} = 2^{n-1}-C_{n-1} \\ C_n&=&C_{n-1} + B_{n-1} = 2^{n-1}-A_{n-1} \end{eqnarray} $$ Putting all these together, $$A_n = 2^{n-1}-(2^{n-2} - C_{n-2})=2^{n-2} + C_{n-2} = 2^{n-2} + 2^{n-3} - A_{n-3} = 3(2^{n-3}) - A_{n-3} \, .$$ Also, $A_0=A_1=A_2=1$.

It follows that $A_{3n}=3(2^{n-3}-2^{n-6}+\dots \pm 2^0) \mp 1$, with similar expressions for $A_{3n+1}$ and $A_{3n+2}$. Obviously, you could use a geometric series formula to further simplify this.

Answer 3

The $n$th sum is $\dfrac{2^n+2\cos(n\pi/3)}3$. Note that $2\cos(n\pi/3)$ is always in $\{-2,-1,1,2\}$ and, that, starting at $n=0$, it is $2$, $1$, $-1$, $-2$, $-1$, $1$, $2$, $1$, $-1$, $-2$, $-1$, $1$, $2$, $1$, etc.

To see why, use the third unit roots $$1,\qquad \mathrm j=\mathrm e^{2\mathrm i\pi/3},\qquad\mathrm j^2=\mathrm e^{-2\mathrm i\pi/3},$$ and that $1+\mathrm j^k+\mathrm j^{2k}=0$ for every $k$ except when $k$ is a multiple of $3$, and then $1+\mathrm j^k+\mathrm j^{2k}=3$.

Thus, the sum $S_n$ to compute solves $$3S_n=\sum_k{n\choose k}(1+\mathrm j^k+\mathrm j^{2k})=\sum_k{n\choose k}+\sum_k{n\choose k}\mathrm j^k+\sum_k{n\choose k}\mathrm j^{2k},$$ that is, $$3S_n=(1+1)^n+(1+\mathrm j)^n+(1+\mathrm j^2)^n. $$ Identifying $1+\mathrm j=\mathrm e^{\mathrm i\pi/3}$ and $1+\mathrm j^2=\mathrm e^{-\mathrm i\pi/3}$ allows to deduce that $$(1+\mathrm j)^n+(1+\mathrm j^2)^n=\mathrm e^{n\mathrm i\pi/3}+\mathrm e^{-n\mathrm i\pi/3}=2\cos(n\pi/3), $$ which concludes the proof.

Answer 4

If $1+\zeta+\zeta^2=0$, try to compute $(1+\zeta^0)^n + (1+\zeta)^n + (1+\zeta^2)^n$. Hint: $\zeta^3=1$, and, if $k$ is not divisible by $3$, $1+\zeta^k+\zeta^{2k}=0$.

Answer 5

I wanted to post this as a comment but it's not letting me, so please go easy on me.

Binomial coefficients are listed in Pascal's triangle, which suggests there is a recurrence relation for $\sum_{i = 0}^{\lceil \frac{n}{3} \rceil} \binom{n}{3i}$ and indeed there is. I looked in http://oeis.org/A024493 and found: $a(0) = 1$, $a(1) = 1$, $a(2) = 1$, $a(n) = 3a(n - 1) - 3a(n - 2) + 2a(n - 3)$.

Answer 6

$\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{\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{\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{\verts}[1]{\left\vert\, #1 \,\right\vert}$ We can sum 'up to' $\ds{\infty\ \pars{~\mbox{Why ?}~}}$:

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

$\ds{z^{3} - 1 = 0}$ has roots at $\ds{z_{m} = \expo{2m\pi\ic/3}\,,\ m = -1,0,1}$: \begin{align}&\color{#66f}{\large\sum_{k = 0}^{\infty}{n \choose 3k}} =\sum_{m = -1}^{1}\lim_{z\ \to\ z_{m}} \bracks{\pars{z - z_{m}}\,{\pars{1 + z}^{n}z^{2} \over z^{3} - 1}} =\sum_{m = -1}^{1}\bracks{{\pars{1 + z_{m}}^{n}z_{m}^{2} \over 3z_{m}^{2}}} \\[3mm]&={1 \over 3}\sum_{m = -1}^{1}\pars{1 + z_{m}}^{n} ={1 \over 3}\braces{2^{n} + 2\,\Re\pars{\bracks{1 + \expo{2\pi\ic/3}}^{n}}} \\[3mm]&={1 \over 3}\bracks{% 2^{n} + 2\,\Re\pars{\expo{-n\pi\ic/3}2^{n}\cos^{n}\pars{\pi \over 3}}} =\color{#66f}{\large{1 \over 3}\bracks{2^{n} + 2\cos\pars{n\pi \over 3}}} \end{align}