This question already has an answer here:

Well as the title says I'm having problems trying to derive a general expression for this sum which involves cubic roots of unity

$$\sum_{k=0}^ {\lfloor \frac n 3\rfloor} {n \choose 3k}$$

Need help guys!


marked as duplicate by Winther, Community Jun 18 '16 at 9:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ I read this math.stackexchange.com/questions/142260/… but I have never come across the second sum they mentioned :s $\endgroup$ – Ron Jun 18 '16 at 9:44
  • $\begingroup$ As we need $3k,$ put $1,w,w^2$ where $w^3=1$ in $$(1+x)^n$$ and add $\endgroup$ – lab bhattacharjee Jun 18 '16 at 9:44
  • $\begingroup$ I still can't see where the $\lfloor n/3 \rfloor$ comes from :s $\endgroup$ – Ron Jun 18 '16 at 9:59
  • $\begingroup$ Note that ${n\choose 3k} = 0$ by definition if $3k > n$ so the sum of ${n\choose 3k}$ over all integers $k$ is the same as the sum over all integers satisfying $k \leq \frac{n}{3}$. This is the likely reason why the upper-limit is taken as $\lfloor n/3 \rfloor$. $\endgroup$ – Winther Jun 18 '16 at 11:01
  • $\begingroup$ Now I see it. Thank you! $\endgroup$ – Ron Jun 18 '16 at 21:13

Here's a hint:

The binomial theorem gives $f(x) = (1+x)^n = \sum_{i = 0} \binom{n}{i} x^i$.

Now if $\zeta$ is a cubic root of unity, consider an appropriate linear combination of $f(1), f(\zeta)$ and $f(\zeta^2)$. Since $1 + \zeta + \zeta^2 = 0$, you should be able to make all but the threeven terms in the sum cancel.


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