The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one would arrive at this answer.
My progress so far has been limited. I have mostly been trying to see if I can somehow relate the sum to $$\sum_{k=0}^{3n}\binom{3n}{k}=8^n$$ but I'm not getting very far. I have also tried to write it out in factorial form, but that hasn't helped me much either.
How would I arrive at the explicit formula?
Best Answer
$$f(x)=\sum_0^{3n}{3n\choose r}x^r=(1+x)^{3n}$$ Now let $a,b$ be the nonreal third roots of 1, and evaluate $$f(1)+f(a)+f(b)$$