What is the summation of $^nC_1 + ^nC_4 + ^nC_7+ \ldots$?

Question

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

Answer 1

$$(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}$$

Answer 2

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