2
$\begingroup$

closed form for $$\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+...+\binom{n}{n}$$

I tried to solve it by :

$$\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+...+\binom{n}{n}=\sum_{k=0}^{n/3}\binom{n}{3k}$$

$$\sum_{k=0}^{n/3}\binom{n}{3k}=\sum_{k=0}^{n/3}\frac{1}{2\pi i}\int_{\left |z \right |=1}\frac{(1+z)^n}{z^{3k+1}}dz$$

then using geometric series but i got no result .

what is your suggest to solve ?

$\endgroup$

marked as duplicate by Grigory M, Davide Giraudo, TMM, Yiyuan Lee, Lost1 Mar 18 '14 at 21:15

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.

  • $\begingroup$ are you sure that $n$ will be $3k$ for some $k\in \Bbb Z$? $\endgroup$ – Guy Mar 18 '14 at 19:53
  • $\begingroup$ @Sabyasachi yes for only n=3a ,where is $a \in z$ $\endgroup$ – user130806 Mar 18 '14 at 19:55
  • $\begingroup$ Also for what it's worth, this will be equal to $\Re\left((1+\omega)^n\right)$ where $\omega=e^{2i\pi/3}$ $\endgroup$ – Guy Mar 18 '14 at 19:56
  • $\begingroup$ does this count as a closed form? $\endgroup$ – Guy Mar 18 '14 at 19:56
  • $\begingroup$ Related: How do I count the subsets of a set whose number of elements is divisible by 3? 4? $\endgroup$ – Grigory M Mar 18 '14 at 19:59
2
$\begingroup$

Assume that $3|n$. $$S_1 = \binom{n}{0}+\binom{n}{3}+\cdots +\binom{n}{n}\\ S_2 = \binom{n}{1}+\binom{n}{4}+\cdots +\binom{n}{n-2}\\ S_3 = \binom{n}{2}+\binom{n}{5}+\cdots +\binom{n}{n-1}\\ S_1 + S_2 + S_3 = 2^n\\ S_1 + jS_2 + j^2 S_3 = (1+j)^n = (-1)^{n/3}\\ S_1 + j^2S_2 + j S_3 = (1+j^2)^n = (-1)^{n/3} $$ with $j^3 = 1, j\notin \Bbb R$.

Now sum up everything: $$ 3S_1 + (1+j+j^2)(S_2+S_3) = 2^n + 2(-1)^{n/3}\\ S_1 = \frac 13[2^n + 2(-1)^{n/3}] $$

$\endgroup$
  • $\begingroup$ what is $j$?${}$ $\endgroup$ – Guy Mar 18 '14 at 19:57
  • $\begingroup$ this is a complex root of $X^3 = 1$ $\endgroup$ – mookid Mar 18 '14 at 19:57
  • $\begingroup$ ah. see my comment below the question. I came up with something similar. +1 $\endgroup$ – Guy Mar 18 '14 at 19:58
  • $\begingroup$ wait. where do you get $(1+j)^3=-1$? $\endgroup$ – Guy Mar 18 '14 at 20:06
  • $\begingroup$ $(1+j)^3 = 1 + 3j + 3j^2 + 1 = 1 - 3 +1 = -1$ because the sum of the roots of $X^3-1$ is 0. $\endgroup$ – mookid Mar 18 '14 at 20:07