Calculating $\binom{n}{0}+\binom{n}{4}+\binom{n}{8}+\cdots$

Calculate: $$\binom{n}{0}+\binom{n}{4}+\binom{n}{8}+\cdots$$

The solution of this exercise:

Let $$S_1=\binom{n}{0}-\binom{n}{2}+\binom{n}{4}-\binom{n}{8}+\cdots$$

$$S_2=\binom{n}{1}-\binom{n}{3}+\binom{n}{5}-\cdots$$

$$S_3=\binom{n}{0}+\binom{n}{4}+\binom{n}{8}+\cdots$$

$$S_4=\binom{n}{2}+\binom{n}{6}+\binom{n}{10}+\cdots$$

And we consider $$(1+i)^n=S_1+iS_2=\sqrt2^n\left(\cos\frac{n\pi}{4}+i\sin\frac{n\pi}{4}\right)$$ and $$2^{n-1}+S_1=2S_3$$

The problem is that i didn't get the part with $$(1+i)^n$$.. from here i got lost.I saw more exercises like this with combinatorial sums whose solution was about complex numbers and i wish that someone explain me that method.Thanks!

• Suggest you take a look at our MathJax tutorial: math.meta.stackexchange.com/questions/5020/…. Jun 18, 2019 at 14:37
• What you need is that $i^2=-1$ so compute $(1+x)^n$, and then put $x=i$. You are picking out every fourth term and you have $i^4=1$. If you were picking out every fifth term you'd want to work with $\omega^5=1$ and its powers. These "roots of unity" have good properties for this kind of problem. Jun 18, 2019 at 14:46

As we need every fourth term,

Calculate $$a(1+1)^n+b(1-1)^n+c(1+i)^n+d(1-i)^n=\binom n0+\binom n4+\cdots$$

Compare the coefficients of $$\binom n0=1$$ and those of $$\binom nr,1\le r\le3$$

to find $$a,b,c,d$$

• $$a+c+d=1$$ $$a+ci-di=0$$ $$a-c-d=0$$ $$\implies a=\dfrac12,$$ $$c+d=\dfrac12,i(c-d)=-\dfrac12$$ Jun 18, 2019 at 14:59

The part with $$(1+i)^n$$ is explained by De Moivre:
$$(1+i)^n=\sqrt2^ne^{i\frac{n\pi}{4}}=\sqrt2^n(\cos\frac{\pi}{4}+i\sin\frac{\pi}{4})^n=\sqrt2^n(\cos\frac{n\pi}{4}+i\sin\frac{n\pi}{4})$$

Now comparing the $$\Re$$ parts of the LHS and RHS of the given equation:
$$\Re(\sqrt2^n(\cos\frac{n\pi}{4}+i\sin\frac{n\pi}{4}))=\Re(S_1+iS_2)$$ $$\iff\sqrt2^n\cos\frac{n\pi}{4}=S_1$$ $$\iff \sqrt2^n\cos\frac{n\pi}{4}=2^{n-1}-2S_3.$$ Thereby, $$S_3=\binom{n}{0}+\binom{n}{4}+\dots=\frac{1}{2}\left(2^{n-1}-\sqrt2^n\cos\frac{n\pi}{4}\right).$$

$$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#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}$$

With $$\ds{n \in \mathbb{N}_{\ \geq\ 0}}$$:

\begin{align} \sum_{k = 0}^{\infty}{n \choose 4k} & = \sum_{k = 0}^{\infty}{n \choose k}{1^{k} + \pars{-1}^{k} + \ic^{k} + \pars{-\ic}^{k} \over 4} \\[5mm] & = {1 \over 4}\ \underbrace{\sum_{k = 0}^{\infty}{n \choose k}1^{k}}_{\ds{2^{n}}}\ +\ {1 \over 4}\ \underbrace{\sum_{k = 0}^{\infty}{n \choose k}\pars{-1}^{k}} _{\ds{\delta_{n0}}} + {1 \over 2}\,\Re\ \underbrace{\sum_{k = 0}^{\infty}{n \choose k}\ic^{k}} _{\ds{\pars{1 + \ic}^{n}}} \\[5mm] & = 2^{n - 2} + {\delta_{n0} \over 4} + {1 \over 2}\,\Re\bracks{2^{n/2}\expo{n\pi\ic/4}} \\[5mm] & = \bbx{2^{n - 2} + {\delta_{n0} \over 4} + 2^{n/2 - 1}\cos\pars{n\pi \over 4}} \end{align}