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$?
 A: Using roots of unity, we get that
$$
[d|k-m]=\frac1d\sum_{j=0}^{d-1}e^{2\pi ij(k-m)/d}\tag1
$$
where $[\dots]$ are Iverson Brackets.
$$
\begin{align}
S_m
&=\sum_{k=0}^n[3|k-m]\binom{n}{k}\tag{2a}\\
&=\frac13\sum_{k=0}^n\sum_{j=0}^2e^{2\pi ij(k-m)/3}\binom{n}{k}\tag{2b}\\
&=\frac13\sum_{k=0}^n\sum_{j=-1}^1e^{2\pi ij(k-m)/3}\binom{n}{k}\tag{2c}\\
&=\frac13\sum_{j=-1}^1e^{-2\pi ijm/3}\left(1+e^{2\pi ij/3}\right)^n\tag{2d}\\
&=\frac13\sum_{j=-1}^1e^{\pi ij(n-2m)/3}\left(e^{\pi ij/3}+e^{-\pi ij/3}\right)^n\tag{2e}\\
&=\frac{2^n}3\sum_{j=-1}^1e^{\pi ij(n-2m)/3}\cos^n\left(\frac{\pi j}3\right)\tag{2f}\\
&=\frac{2^n}3+\frac23\cos\left(\frac{\pi(n-2m)}3\right)\tag{2g}
\end{align}
$$
Explanation:
$\text{(2a):}$ write $S_m$ using Iverson Brackets
$\text{(2b):}$ apply $(1)$ with $d=3$, then sum in $k$ against $\binom{n}{k}$
$\text{(2c):}$ the terms for $j=2$ and $j=-1$ are identical
$\text{(2d):}$ apply the Binomial Theorem
$\text{(2e):}$ pull $e^{\pi ijn/3}$ out of $\left(1+e^{2\pi ij/3}\right)^n$
$\text{(2f):}$ $e^{\pi ij/3}+e^{-\pi ij/3}=2\cos\left(\frac{\pi j}3\right)$
$\text{(2g):}$ compute the sum, applying $e^{ix}+e^{-ix}=2\cos(x)$
$\text{(2g)}$ gives the answer. It may be useful to remember some values of cosine:
$$
\cos\left(\frac{\pi j}3\right)=\left\{\begin{array}{}
1&\text{if }j\equiv0\pmod6\\
\frac12&\text{if }j\equiv1\pmod6\\
-\frac12&\text{if }j\equiv2\pmod6\\
-1&\text{if }j\equiv3\pmod6\\
-\frac12&\text{if }j\equiv4\pmod6\\
\frac12&\text{if }j\equiv5\pmod6\\
\end{array}\right.\tag3
$$
A: $$(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}$$
