closed form for $\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+…+\binom{n}{n}$ [duplicate]

closed form for $$\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+...+\binom{n}{n}$$

I tried to solve it by :

$$\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+...+\binom{n}{n}=\sum_{k=0}^{n/3}\binom{n}{3k}$$

$$\sum_{k=0}^{n/3}\binom{n}{3k}=\sum_{k=0}^{n/3}\frac{1}{2\pi i}\int_{\left |z \right |=1}\frac{(1+z)^n}{z^{3k+1}}dz$$

then using geometric series but i got no result .

what is your suggest to solve ?

marked as duplicate by Grigory M, Davide Giraudo, TMM, Yiyuan Lee, Lost1Mar 18 '14 at 21:15

• are you sure that $n$ will be $3k$ for some $k\in \Bbb Z$? – Guy Mar 18 '14 at 19:53
• @Sabyasachi yes for only n=3a ,where is $a \in z$ – user130806 Mar 18 '14 at 19:55
• Also for what it's worth, this will be equal to $\Re\left((1+\omega)^n\right)$ where $\omega=e^{2i\pi/3}$ – Guy Mar 18 '14 at 19:56
• does this count as a closed form? – Guy Mar 18 '14 at 19:56
• – Grigory M Mar 18 '14 at 19:59

Assume that $3|n$. $$S_1 = \binom{n}{0}+\binom{n}{3}+\cdots +\binom{n}{n}\\ S_2 = \binom{n}{1}+\binom{n}{4}+\cdots +\binom{n}{n-2}\\ S_3 = \binom{n}{2}+\binom{n}{5}+\cdots +\binom{n}{n-1}\\ S_1 + S_2 + S_3 = 2^n\\ S_1 + jS_2 + j^2 S_3 = (1+j)^n = (-1)^{n/3}\\ S_1 + j^2S_2 + j S_3 = (1+j^2)^n = (-1)^{n/3}$$ with $j^3 = 1, j\notin \Bbb R$.
Now sum up everything: $$3S_1 + (1+j+j^2)(S_2+S_3) = 2^n + 2(-1)^{n/3}\\ S_1 = \frac 13[2^n + 2(-1)^{n/3}]$$
• what is $j$?${}$ – Guy Mar 18 '14 at 19:57
• this is a complex root of $X^3 = 1$ – mookid Mar 18 '14 at 19:57
• wait. where do you get $(1+j)^3=-1$? – Guy Mar 18 '14 at 20:06
• $(1+j)^3 = 1 + 3j + 3j^2 + 1 = 1 - 3 +1 = -1$ because the sum of the roots of $X^3-1$ is 0. – mookid Mar 18 '14 at 20:07