<s>[INST] What is the summation of $^nC_1 + ^nC_4 + ^nC_7+ \ldots$? I know how to find the following sum:
$$ S_0 = {}^nC_0 + ^nC_3 + ^nC_6 + ^nC_9 + \ldots \\= \sum {^nC_{3k}} $$
To solve it, we set: $$(1 + x)^n = \sum_{i=0}^{n} {^nC_{r}} {x^r} $$
Then we substitute $x$ with cube roots of unity to get 3 equations. We sum these 3 equations and then simplify them. Finally, we get $S_0 = \frac{2^n + 2\cos(\frac{n\pi}{3})}{3} $
Now, similarly, can we get the following sums as well?
$$ S_1 = {}^nC_1 + ^nC_4 + ^nC_7 + ^nC_{10} + \ldots \\ = \sum {^nC_{3k+1}} $$
$$ S_2 = {}^nC_2 + ^nC_5 + ^nC_8 + ^nC_{11} + \ldots \\ = \sum {^nC_{3k+2}} $$
I just can’t simplify the above expressions to get a nice and simplified result. Can you help me to find $S_1$ and $S_2$?
 [/INST] $$(1 + x)^n = \sum_{i=0}^{n} {^nC_{r}} {x^r} $$
Let $w=e^{i\frac{2\pi}3}$. So, $w^3=1$ and $1+w+w^2=0$.
$1+w=-w^2=e^{i\pi+i\frac{4\pi}3}=e^{i\frac\pi3}$.
$1+w^2=-w=e^{i\pi+i\frac{2\pi}3}=e^{i\frac{-\pi}3}$.
$$(1 + 1)^n = \sum_{i=0}^{n} {^nC_{r}} =S_0 + S_1 + S_2\\
(1 + w)^n = \sum_{i=0}^{n} {^nC_{r}} {w^{r\%3}} =S_0 +S_1w+S_2w^2\\
(1 + w^2)^n = \sum_{i=0}^{n} {^nC_{r}} {w^{(2r)\%3}}=S_0 +S_1w^2+S_2w$$
$$3S_0=(1 + 1)^n + (1 + w)^n + (1 + w^2)^n\\=2^n + e^{i\frac{n\pi}3}+ e^{i\frac{-n\pi}3}=2^n + 2\cos(\frac{n\pi}3)\\
3S_1=(1 + 1)^n + (1 + w)^nw^2 + (1 + w^2)^nw\\=2^n + e^{i\frac{n\pi-2\pi}3}+ e^{i\frac{-n\pi+2\pi}3}=2^n + 2\cos(\frac{(n-2)\pi}3)\\
3S_2=(1 + 1)^n + (1 + w)^nw + (1 + w^2)^nw^2\\=2^n + e^{i\frac{n\pi-4\pi}3}+ e^{i\frac{-n\pi+4\pi}3}=2^n + 2\cos(\frac{(n-4)\pi}3)\\
$$
So for $r=0,1,2$, $$S_r=\frac{2^n+2\cos(\frac{(n-2i)\pi}3)}3$$
$$3S_r -2^n=\begin{cases}
2 &\text{if } (n-2r) \% 6 = 0 \\
1 &\text{if } (n-2r) \% 6 = 1 \\
-1 &\text{if } (n-2r) \% 6 = 2 \\
-2 &\text{if } (n-2r) \% 6 = 3 \\
-1 &\text{if } (n-2r) \% 6 = 4 \\
1 &\text{if } (n-2r) \% 6 = 5 \\
\end{cases}$$
</s>