A nice generalization

Let $S$ be the desired sum and let $w=e^{2 \pi i/3}$ . Consider the following sum: $\begin{aligned} \sum_{m=0}^{2} w^{-bm}(1+w^m)^n &= \sum_{m=0}^{2} w^{-bm} \sum_{k=0}^{n} w^{mk} \binom{n}{k}\\ &= \sum_{m=0}^{2} \sum_{k=0}^{n} w^{m(k-b)} \binom{n}{k}\\ &= \sum_{k=0}^{n} \sum_{m=0}^{2} w^{m(k-b)} \binom{n}{k} \end{aligned}$ When $k-b$ is a multiple of $3$ we have $\displaystyle \sum_{m=0}^{2} w^{m(k-b)}=3$ , otherwise we have $\displaystyle \sum_{m=0}^{2} w^{m(k-b)}=0$ , so we are left only with the terms of the sum where $k \equiv b \pmod 3$ , so: $\begin{aligned} \sum_{m=0}^{2} w^{-bm}(1+w^m)^n &= \sum_{k=0}^{\left\lfloor \frac{n-b}{3} \right\rfloor} 3\binom{n}{3k+b}\\ &= 3S \end{aligned}$ Finally, using the fact that $w^2+w+1=0$ , $\begin{aligned} S &= \dfrac{1}{3} \sum_{m=0}^{2} w^{-bm}(1+w^m)^n \\ &= \dfrac{1}{3} \left[(1+1)^n+w^{-b}(1+w)^n+w^{-2b}(1+w^2)^n\right] \\ &= \dfrac{1}{3} \left[2^n+w^{-b}(-w^2)^n+w^{-2b}(-w)^n\right] \\ &= \dfrac{1}{3} \left[2^n+(-1)^n(w^{2n-b}+w^{n-2b})\right] \\ &= \dfrac{1}{3} \left[2^n+(-1)^n(w^{-(n+b)}+w^{n+b})\right]\\ &= \boxed{\dfrac{1}{3} \left[2^n+2(-1)^n \cos\left(\dfrac{2 \pi (n+b)}{3}\right) \right]} \end{aligned}$