Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have recently been interested in the problem of summing Combinatorials. I have been beating my brain for the past days to figure out how to find an explicit closed form of:

$n \choose 0 $+$ n \choose 3 $+$ n \choose 6$ + $\dots$ + $n \choose 3K$, where $3K$ is the largest multiple of $3$ less than or equal to $n$.

I have tried the expansion of $(1+1+1)^n$ which got nowhere, and I dont know how to proceed. I figure the answer will be conditional on $n \pmod 6$.

Can someone lend help? Thank you.

share|cite|improve this question
Since the set $\mathbb{Z}\cap(n,\infty)$ is not bounded above, what do you mean by $3K$ being the largest number such that $3(K+1)>n$? – Mercy King Nov 3 '12 at 22:48
Ah right. $n$ is a constant- a fixed number. Thus, if we had-say- $n=100$, $K$ would be $33$. What i was trying to get at is pretty much to just have all the multiples of $3$ that are less then $n$ being in the combinatorics. I will fix the typo – Apurva Nov 3 '12 at 22:51
There's a duplicate somewhere, but I'm too lazy to find it. See this: – wj32 Nov 3 '12 at 22:52
You don't need to worry about defining K precisely: $$\binom{a}{b} = 0$$ when $a,b \in \mathbb{N}$ and $b > a$. – Peter Taylor Nov 3 '12 at 22:59
@PeterTaylor I'm not worried about defining $K$, but it simply makes no sense to say that $3K$ is the largest the largest number satisfying $3(K+1)>n$ since such a number doesn't actually exist. – Mercy King Nov 3 '12 at 23:28

Let $\omega$ be a third root of 1.


$$(1+1)^n = \binom{n}{0} +\binom{n}{1}+ \binom{n}{2}+ \binom{n}{3}+ ...+\binom{n}{n} \,.$$ $$ (1+\omega)^n = \binom{n}{0} + \binom{n}{1}\omega+ \binom{n}{2} \omega^2+ \binom{n}{3}+ ...+ \binom{n}{n} \omega^n \,.$$

$$ (1+\omega^2)^n =\binom{n}{0} + \binom{n}{1} \omega^2+ \binom{n}{2} \omega+ \binom{n}{3}+ ...+ \binom{n}{n}\omega^{2n} \,.$$

Now, since $1+ \omega +\omega^2=0$, adding them only every third column remains.


$$2^n+ (1+\omega)^n+(1+\omega^2)^n =3 \left( \binom{n}{0} +\binom{n}{3}+ \binom{n}{6}+ \binom{n}{9}+ ...+\binom{n}{3k} \right)$$

All you have left is to calculate $(1+\omega)^n$ and $(1+\omega^2)^n$ by writing them in polar/trig form.

P.S. Same trick with $\omega(1+\omega)^n$ and $\omega^2 (1+\omega^2)^n$ yields $\left( \binom{n}{2} +\binom{n}{5}+ \binom{n}{8}+ \binom{n}{11}+ ... \right)$ while $\omega^2(1+\omega)^n$ and $\omega (1+\omega^2)^n$ yields $\left( \binom{n}{1} +\binom{n}{4}+ \binom{n}{7}+ \binom{n}{10}+ ... \right)$.

share|cite|improve this answer
It is not clear why $1+ \omega +\omega^2=0$? – NoChance Nov 3 '12 at 23:47
@EmmadKareem: What N.S. meant was "Let $\omega$ be a third root of 1 not equal to 1". Now $\omega^3-1=0$, so $(\omega-1)(\omega^2+\omega+1)=0$. Since $\omega \ne 1$, $\omega^2+\omega+1=0$. – wj32 Nov 4 '12 at 0:56
@wj32, thanks for your explanation. – NoChance Nov 4 '12 at 4:52

A closed form is given by $\ \displaystyle \frac{2^n+2\cos(n\pi/3)}3$.

See this entry of OEIS for more information.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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