# How to find the General expression of $\sum_{k=0}^ {\lfloor n/3\rfloor} {n \choose 3k}$ [duplicate]

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

• I read this math.stackexchange.com/questions/142260/… but I have never come across the second sum they mentioned :s – Ron Jun 18 '16 at 9:44
• As we need $3k,$ put $1,w,w^2$ where $w^3=1$ in $$(1+x)^n$$ and add – lab bhattacharjee Jun 18 '16 at 9:44
• I still can't see where the $\lfloor n/3 \rfloor$ comes from :s – Ron Jun 18 '16 at 9:59
• 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$. – Winther Jun 18 '16 at 11:01
• Now I see it. Thank you! – Ron Jun 18 '16 at 21:13

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.