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

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

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

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

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

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