1
$\begingroup$

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.

  • 0
    Reading this title and question hurts my eyes. For anyone who visits this page in the future, note: Combinatorics is the genre of mathematics which studies discrete objects, their properties, and how many of them there are. Combinatorial is an adjective used to describe something having to do with combinatorics. Neither are what you should call $\binom{n}{k}$. That is worded as a *Combination*. There is no such thing as a sum of combinatorics neither is there such a thing as a sum of combinatorials.2016-12-02

2 Answers 2

2

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

  • 0
    @wj32, thanks for your explanation.2012-11-04
0

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

See this entry of OEIS for more information.