13
$\begingroup$

Help me to simplify:$$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$

I got a hunch that it will depend on whether $n$ is a multiple of $6$ and equals to $\frac{2^n+2}{3}$ when $n$ is a multiple of $6$.

$\endgroup$
22
$\begingroup$

This technique is known as the Roots of Unity Filter. See this related question.

Note that $(1+x)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}x^k$. Let $\omega = e^{i2\pi/3}$. Then, we have:

$(1+1)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}1^k$

$(1+\omega)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^k$

$(1+\omega^2)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^{2k}$

Add these three equations together to get $\displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}(1+\omega^k+\omega^{2k}) = 2^n+(1+\omega)^n+(1+\omega^2)^n$

You can see that $1+\omega^k+\omega^{2k} = 3$ if $k$ is a multiple of $3$ and $0$ otherwise.

Thus, $\displaystyle\sum_{m = 0}^{\lfloor n/3 \rfloor}\dbinom{n}{3m} = \dfrac{1}{3}\left[2^n+(1+\omega)^n+(1+\omega^2)^n\right]$

Now, simplify this.

$\endgroup$
11
$\begingroup$

Here's a method that doesn't (explicitly) involve complex numbers.

Let $A_n=\sum_k \binom{n}{3k}$, $B_n=\sum_k \binom{n}{3k+1}$, $C_n=\sum_k \binom{n}{3k+2}$.

Then $A_n+B_n+C_n=2^n$ by the binomial theorem. Moreover, Pascal's identity implies the following: $$ \begin{eqnarray} A_n&=&A_{n-1} + C_{n-1} =2^{n-1}-B_{n-1} \\ B_n&=&B_{n-1} + A_{n-1} = 2^{n-1}-C_{n-1} \\ C_n&=&C_{n-1} + B_{n-1} = 2^{n-1}-A_{n-1} \end{eqnarray} $$ Putting all these together, $$A_n = 2^{n-1}-(2^{n-2} - C_{n-2})=2^{n-2} + C_{n-2} = 2^{n-2} + 2^{n-3} - A_{n-3} = 3(2^{n-3}) - A_{n-3} \, .$$ Also, $A_0=A_1=A_2=1$.

It follows that $A_{3n}=3(2^{n-3}-2^{n-6}+\dots \pm 2^0) \mp 1$, with similar expressions for $A_{3n+1}$ and $A_{3n+2}$. Obviously, you could use a geometric series formula to further simplify this.

$\endgroup$
5
$\begingroup$

The $n$th sum is $\dfrac{2^n+2\cos(n\pi/3)}3$. Note that $2\cos(n\pi/3)$ is always in $\{-2,-1,1,2\}$ and, that, starting at $n=0$, it is $2$, $1$, $-1$, $-2$, $-1$, $1$, $2$, $1$, $-1$, $-2$, $-1$, $1$, $2$, $1$, etc.

To see why, use the third unit roots $$1,\qquad \mathrm j=\mathrm e^{2\mathrm i\pi/3},\qquad\mathrm j^2=\mathrm e^{-2\mathrm i\pi/3},$$ and that $1+\mathrm j^k+\mathrm j^{2k}=0$ for every $k$ except when $k$ is a multiple of $3$, and then $1+\mathrm j^k+\mathrm j^{2k}=3$.

Thus, the sum $S_n$ to compute solves $$3S_n=\sum_k{n\choose k}(1+\mathrm j^k+\mathrm j^{2k})=\sum_k{n\choose k}+\sum_k{n\choose k}\mathrm j^k+\sum_k{n\choose k}\mathrm j^{2k},$$ that is, $$3S_n=(1+1)^n+(1+\mathrm j)^n+(1+\mathrm j^2)^n. $$ Identifying $1+\mathrm j=\mathrm e^{\mathrm i\pi/3}$ and $1+\mathrm j^2=\mathrm e^{-\mathrm i\pi/3}$ allows to deduce that $$(1+\mathrm j)^n+(1+\mathrm j^2)^n=\mathrm e^{n\mathrm i\pi/3}+\mathrm e^{-n\mathrm i\pi/3}=2\cos(n\pi/3), $$ which concludes the proof.

$\endgroup$
2
$\begingroup$

If $1+\zeta+\zeta^2=0$, try to compute $(1+\zeta^0)^n + (1+\zeta)^n + (1+\zeta^2)^n$. Hint: $\zeta^3=1$, and, if $k$ is not divisible by $3$, $1+\zeta^k+\zeta^{2k}=0$.

$\endgroup$
2
$\begingroup$

I wanted to post this as a comment but it's not letting me, so please go easy on me.

Binomial coefficients are listed in Pascal's triangle, which suggests there is a recurrence relation for $\sum_{i = 0}^{\lceil \frac{n}{3} \rceil} \binom{n}{3i}$ and indeed there is. I looked in http://oeis.org/A024493 and found: $a(0) = 1$, $a(1) = 1$, $a(2) = 1$, $a(n) = 3a(n - 1) - 3a(n - 2) + 2a(n - 3)$.

$\endgroup$
2
$\begingroup$

$\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{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ We can sum 'up to' $\ds{\infty\ \pars{~\mbox{Why ?}~}}$:

\begin{align}&\color{#66f}{\large\sum_{k = 0}^{\infty}{n \choose 3k}} =\sum_{k = 0}^{\infty}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{n} \over z^{3k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{n} \over z}\sum_{k = 0}^{\infty}\pars{1 \over z^{3}}^{k} \,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{n} \over z}{1 \over 1 - 1/z^{3}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{n}z^{2} \over z^{3} - 1}\,{\dd z \over 2\pi\ic} \end{align}

$\ds{z^{3} - 1 = 0}$ has roots at $\ds{z_{m} = \expo{2m\pi\ic/3}\,,\ m = -1,0,1}$: \begin{align}&\color{#66f}{\large\sum_{k = 0}^{\infty}{n \choose 3k}} =\sum_{m = -1}^{1}\lim_{z\ \to\ z_{m}} \bracks{\pars{z - z_{m}}\,{\pars{1 + z}^{n}z^{2} \over z^{3} - 1}} =\sum_{m = -1}^{1}\bracks{{\pars{1 + z_{m}}^{n}z_{m}^{2} \over 3z_{m}^{2}}} \\[3mm]&={1 \over 3}\sum_{m = -1}^{1}\pars{1 + z_{m}}^{n} ={1 \over 3}\braces{2^{n} + 2\,\Re\pars{\bracks{1 + \expo{2\pi\ic/3}}^{n}}} \\[3mm]&={1 \over 3}\bracks{% 2^{n} + 2\,\Re\pars{\expo{-n\pi\ic/3}2^{n}\cos^{n}\pars{\pi \over 3}}} =\color{#66f}{\large{1 \over 3}\bracks{2^{n} + 2\cos\pars{n\pi \over 3}}} \end{align}

$\endgroup$
  • 3
    $\begingroup$ Well, frankly, it is too difficult for me. :-( Can you, may be, elaborate a bit? $\endgroup$ – pushpen.paul Aug 10 '14 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.