Find the value of $\sum_{r=0}^{\left\lfloor\frac{n-1}3\right\rfloor}\binom{n}{3r+1}$

Question

Show that $$\binom{n}{1}+\binom{n}{4}+\binom{n}{7}+\ldots=\dfrac{1}{3}\left[ 2^{n-2} + 2\cos{\dfrac{(n-2)\pi}{3}}\right]$$

---

My solution:-

$$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\binom{n}{3}x^3+\ldots=\sum_{r=0}^{n}{\binom{n}{r}x^r} \\ \therefore x^2(1+x)^n=\binom{n}{0}x^2+\binom{n}{1}x^3+\binom{n}{2}x^4+\binom{n}{3}x^5+\ldots=\sum_{r=0}^{n}{\binom{n}{r}x^{r+2}}$$

In the above Binomial Expansion on substituting $x=1,\omega,\omega^2$, $\omega$ being a complex cube root of unity, we get the following three equations

$$\tag{1}(1)^2(1+1)^n=\sum_{r=0}^{n}{\binom{n}{r}}=2^n$$

$$(\omega)^2(1+\omega)^n=\sum_{r=0}^{n}{\binom{n}{r}\omega^{r+2}}=(-1)^n(\omega)^{2n+2} \tag{2}$$

$$(\omega)^4(1+\omega^2)^n=(\omega)(1+\omega^2)^n=\sum_{r=0}^{n}{\binom{n}{r}\omega^{2r+4}}=(-1)^n(\omega)^{n+1} \tag{3}$$

On adding $(1),(2) \text{ and }(3)$, we get

$$\dfrac{1}{3}\left(2^n+(-1)^n(\omega^{n+1}+\omega^{2n+2})\right)=\sum_{r=0}^{\left\lfloor\frac{n-1}3\right\rfloor}\binom{n}{3r+1}$$ Now, as $\omega=-e^{i(\pi/3)}$ ($\omega$ being the cube root of unity)

$$\begin{aligned} \therefore (\omega^{n+1} +\omega^{2n+2}) &= \left(\left(-e^{i(\pi/3)}\right)^{n+1}+\left(-e^{-i(\pi/3)}\right)^{n+1}\right) \\ &=(-1)^{n+1}\left(e^{i(\pi(n+1)/3)}+e^{-i(\pi(n+1)/3)}\right) \\ &=(-1)^n\left(2\cos{\left(\dfrac{\pi(n+1)}{3}\right)}\right) \end{aligned}$$

Now, substituting the value of $(\omega^{n+1}+\omega^{2n+2})$ back into $(4)$, we get

$$2^n+(-1)^n(\omega^{n+1}+\omega^{2n+2})=2^n-2\cos{\left(\dfrac{\pi(n+1)}{3}\right)}=\sum_{r=0}^{n}{\binom{n}{3r+1}}$$

$$\therefore \sum_{r=0}^{\left\lfloor\frac{n-1}3\right\rfloor}\binom{n}{3r+1}=\boxed{\dfrac{1}{3}\left(2^n-2\cos{\left(\dfrac{\pi(n+1)}{3}\right)}\right)}$$

So, where did I go wrong, or is it that the book has provided the wrong answer.

Answer 1

Let $\alpha=e^{2\pi i/3}=\frac{-1+i\sqrt3}2$, that is $\alpha^3=1$, then if $k\not\equiv0\pmod3$, $\alpha^k+1+\alpha^{-k}=\frac{\alpha^{3k}-1}{\alpha^k\left(\alpha^k-1\right)}=0$. If $k\equiv0\pmod3$, then $\alpha^k+1+\alpha^{-k}=1+1+1=3$. That is, $$ \frac{\alpha^{k-1}+1+\alpha^{1-k}}3=\left\{\begin{array}{} 1&\text{if }k\equiv1\pmod3\\ 0&\text{if }k\not\equiv1\pmod3 \end{array}\right. $$ Furthermore, $$ 1+\alpha=\frac{1+i\sqrt3}2=e^{\pi i/3} $$ Therefore, $$ \begin{align} \sum_{k=0}^{\left\lfloor\frac{n-1}3\right\rfloor}\binom{n}{3k+1} &=\sum_{k=0}^n\binom{n}{k}\frac{\alpha^{k-1}+1+\alpha^{1-k}}{3}\\ &=\frac1{3\alpha}(1+\alpha)^n+\frac13\cdot2^n+\frac\alpha3\left(1+\frac1\alpha\right)^n\\ &=\frac1{3\alpha}e^{\pi in/3}+\frac13\cdot2^n+\frac\alpha3e^{-\pi in/3}\\ &=\frac13e^{\pi i(n-2)/3}+\frac13\cdot2^n+\frac13e^{-\pi i(n-2)/3}\\ &=\frac13\left(2^n+2\cos\left(\pi\frac{n-2}3\right)\right)\\ &=\frac13\left(2^n-2\cos\left(\pi\frac{n+1}3\right)\right) \end{align} $$ As far as the periodic part goes, neither is wrong: $\cos\left(\pi\frac{n-2}3\right)=-\cos\left(\pi\frac{n+1}3\right)$.

However, $$ \sum_{k=0}^{\left\lfloor\frac{n}3\right\rfloor}\binom{n}{3k} +\sum_{k=0}^{\left\lfloor\frac{n-1}3\right\rfloor}\binom{n}{3k+1} +\sum_{k=0}^{\left\lfloor\frac{n-2}3\right\rfloor}\binom{n}{3k+2} =2^n $$ and since each of the sums above are approximately equal, the non-periodic part of the sum should be $\frac13\cdot2^n$.

Answer 2

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#f00}{\sum_{k = 0}^{\left\lfloor\pars{n - 1}/3\right\rfloor} \,\,{n \choose 3k + 1}} & = \sum_{k = 0}^{\infty}{n \choose n - 3k - 1} = \sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ 1^{\color{#f00}{-}}} {\pars{1 + z}^{n} \over z^{n - 3k}}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{\color{#f00}{-}}} {\pars{1 + z}^{n} \over z^{n}}\sum_{k = 0}^{\infty}\pars{z^{3}}^{k}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z}\ =\ 1^{\color{#f00}{-}}}\,\,\, {\pars{1 + z}^{n} \over z^{n}\pars{1 - z^{3}}}\,{\dd z \over 2\pi\ic} \\[5mm] &\ \stackrel{z\ \mapsto\ 1/z}{=}\ \oint_{\verts{z}\ =\ 1^{\color{#f00}{+}}}\,\,\, {z\pars{1 + z}^{n} \over z^{3} - 1}\,{\dd z \over 2\pi\ic} = \sum_{p}{p\,\pars{1 + p}^{n} \over 3p^{2}} \end{align} $\ds{p}$ are the roots of $\ds{z^{3} - 1 = 0}$. Namely, $\ds{p \in \braces{\expo{-2\pi\ic/3},1,\expo{2\pi\ic/3}}}$.

---

Then $\ds{~\pars{\mbox{note that}\ p^{2} = {p^{3} \over p} = {1 \over p}}~}$, \begin{align} \color{#f00}{\sum_{k = 0}^{\left\lfloor\pars{n - 1}/3\right\rfloor} \,\,{n \choose 3k + 1}} & = {1 \over 3}\sum_{p}p^{2}\pars{1 + p}^{n} \\[5mm] & = {1 \over 3}\,2^{n} + {2 \over 3}\, \Re\bracks{\expo{4\pi\ic/3}\pars{1 + \expo{2\pi\ic/3}}^{n}} \\[5mm] & = {1 \over 3}\,2^{n} + {2 \over 3}\, \Re\braces{\expo{\pars{n + 4}\pi\ic/3}\,\,\bracks{2\cos\pars{\pi \over 3}}^{n}} \\[5mm] & = \color{#f00}{{1 \over 3}\braces{2^{n} - 2\cos\pars{\bracks{n + 1}\pi \over 3}}} \end{align}

Note that $\ds{2\cos\pars{\pi \over 3} = 1}$ and $\ds{\expo{\pars{n + 4}\pi\ic/3} = -\expo{\pars{n + 1}\pi\ic/3}}$.