# Closed Formula Expression for Sum of Combinatorics

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.

-
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 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: en.wikipedia.org/wiki/Series_multisection –  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 Nov 3 '12 at 23:28

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

Then

$$(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.

Thus

$$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)$.

-
It is not clear why $1+ \omega +\omega^2=0$? –  Emmad Kareem 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. –  Emmad Kareem Nov 4 '12 at 4:52

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