# what is the value of $\binom{n}{1}​+\binom{n}{4}+\binom{n}{7}​+\binom{n}{10}+\binom{n}{13}+\dots$

what is the value of $$\binom{n}{1}​+\binom{n}{4}+\binom{n}{7}​+\binom{n}{10}+\binom{n}{13}+\dots$$ in the form of number, cos, sin

attempts : I can calculate the value of $$\binom{n}{0}​+\binom{n}{3}+\binom{n}{6}​+\binom{n}{9}+\binom{n}{12}+\dots=\frac{1}{3}\left(2^n+2\cos \frac{n\pi}{3}\right)$$ by use primitive $$3^\text{rd}$$ root of the unity but this problem i cant solve it.

• Can you please show how you calculated the second sum? – RobPratt Apr 26 at 4:28
• @RobPratt See AoPS or another post on this site for how to find the second sum. Found using Approach0. – Toby Mak Apr 26 at 4:33
• @TobyMak, I know how to do both of them. I was looking for some effort from the OP. – RobPratt Apr 26 at 4:34

Let $$\omega=\exp(2\pi i/3)$$. Then $$\frac{1+\omega^k+\omega^{2k}}{3}= \begin{cases} 1 &\text{if 3\mid k}\\ 0 &\text{otherwise} \end{cases}$$ So \begin{align} \sum_{k=0}^\infty \binom{n}{3k+1} &=\sum_{k=0}^\infty \binom{n}{k+1}\frac{1+\omega^k+\omega^{2k}}{3} \\ &=\sum_{k=1}^\infty \binom{n}{k}\frac{1+\omega^{k-1}+\omega^{2(k-1)}}{3} \\ &=\frac{1}{3}\sum_{k=1}^\infty \binom{n}{k} + \frac{1}{3\omega}\sum_{k=1}^\infty \binom{n}{k}\omega^k + \frac{1}{3\omega^2}\sum_{k=1}^\infty \binom{n}{k} \omega^{2k} \\ &=\frac{1}{3}(2^n-1) + \frac{1}{3\omega}((1+\omega)^n-1) + \frac{1}{3\omega^2}((1+\omega^2)^n-1)\\ &=\frac{1}{3}(2^n-1) + \frac{\omega^2}{3}((1+\omega)^n-1) + \frac{\omega}{3}((1+\omega^2)^n-1)\\ &=\frac{2^n + \omega^2(1+\omega)^n + \omega(1+\omega^2)^n}{3} \end{align}
Let $$\sum_{r=0}^{3r+1\le n}\binom n{3r+1}=\sum_{k=0}^2a_k(1+w_k)^n$$
where $$w_k=w^k;k=0,1,2$$ and $$w$$ is a complex cube root of unity so that $$1+w+w^2=0$$
Set $$n=0,1,2$$ to find $$a_k;k=0,1,2$$
Binimial Series: $$(1+x)^n=\sum_{k=0}^{n} {n \choose k} x^k~~~~(1)$$ $$w^3=1, 1+w+w^2=0$$, let $$x=1$$ in (1) we get $$2^n=\sum_{k=0}^n {n \choose k}~~~(2)$$ Let $$x=w$$ in (1) and miltiply it by $$w^2$$, to get $$w^2(1+w)^n=(-1)^n w^{2n+2}=\sum_{k=1}^{n} w^{k+2} {n \choose k}~~~~~(3)$$ Let $$x=w^2$$ in (1) and multiply by $$w$$, to get $$w(1+w^2)^n=(-1)^n w^{n+1}=\sum_{k=0}^{n} w^{2k+1} {n \choose k}~~~~(4)$$ Now add (2), (3), (4), to get $$\sum_{k=0}^{n} [1+w^{k+1}+w^{2k+1}] {n \choose k}=2^n+(-1)^n[w^{2n+2}+w^{n+1}]$$ Whenever $$k=3m+1$$, $$[1+w^{k+2}+w^{2k+1}]=[1+w^3+w^3]=3$$, otherwise it vanishes as $$[1+w+w^2]=0$$ when $$k\ne 2m+1$$ So we get $$\sum_{m=0}^{n} {n\choose 3m+1}= \frac{1}{3}\left(2^n+(-1)^n[w^{2n+2}+w^{n+1}\right)=\frac{1}{3}(2^n+2\cos[(n-2)\pi/3])$$