Suppose we want to evaluate $$\sum_{k\geq 0} \binom{n}{3k}$$ This can be done using roots of unity filters, i.e. showing the sum is equivalent to: $$\frac{(1+1)^n+(1+\omega)^n+(1+\omega^2)^n}{3}$$ where $\omega$ is a primitive 3rd root of unity. Using the fact that $1+\omega+\omega^2=0$, we can show that this is equivalent to $$\frac{2^n+(-\omega^2)^n+(-\omega)^n}{3}$$ Depending on whether $n$ is even or odd, we get that this sum is equal to either $\frac{2^n-1}{3}$ or $\frac{2^n+1}{3}$

Can we use the same trick to evaluate the following sums? $$\sum_{k\geq 0}\binom{n}{3k+1}, \sum_{k\geq 0}\binom{n}{3k+2}$$ Also, can this idea be generalized?

I would appreciate any thoughts or ideas.

  • $\begingroup$ here is one such post... $\endgroup$ – Eleven-Eleven Oct 9 '16 at 1:40
  • $\begingroup$ here is the OEIS of $\binom{n}{3k}$ $\endgroup$ – Eleven-Eleven Oct 9 '16 at 1:45

$$\sum \binom{n}{3k+1} = \frac{1^2 (1+1)^n + \omega^2(1+\omega)^n + \omega(1+\omega^2)^n}{3}$$

Basically, apply the same approach to $f(x)=x^2(1+x)^n$.

Similarly, taking $g(x)=x(1+x)^n$ we get:

$$\sum\binom{n}{3k+2}=\frac{1(1+1)^n + \omega(1+\omega)^n + \omega^2(1+\omega^2)^n}{3}$$

You should be able to get nice formula for these, depending on $n\bmod 3$.

| cite | improve this answer | |

Here is Pascal's Triangle for the first $8$ rows

$$1$$ $$1, 1$$ $$1,2,1$$ $$1,3,3,1$$ $$1,4,6,4,1$$ $$1,5,10,10,5,1$$ $$1,6,15,20,15,6,1$$ $$1,7,21,35,35,21,7,1$$ Then your sequence $S_n$ of $\binom{n}{3k}$ is $\{1,1,1,2,5,11,22,43\}$

Then your sequence $\Sigma S_n$ of $\binom{n}{3k}$ (the partial sums of $S_n$) is $\{1,2,3,5,10,21,43, 86\}$

But what happens if we look at $T_n=\binom{n}{3k+1}$?

Then $T_n=\{0,1,2,3,5,10,21,43\}$

What do you notice, and can you prove a link?

Or $U_n=\binom{n}{3k+2}$?


Now consider $\Sigma T_n$....noticing anything??????

Hopefully you can see that $\Sigma S_n=T_{n+1}$

and then you can see that $\Sigma T_n=U_{n+1}$

and finally $\Sigma \Sigma S_n=U_{n+2}$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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