Combinatorial Sum I am trying to prove
$$0^2 \binom{n}{0}+3^2\binom{n}{3}+6^2\binom{n}{6}+ \cdots + \left[\dfrac{n}{3}\right]^2 \binom{n}{\left[\dfrac{n}{3}\right]},$$ where $[x]$ is the greatest integer not exceeding $x$.
Here is what I get so far:
$$\sum_{k=0}^n \binom{n}{k} k^2x^k = nx[(1+x)^{n-1}+x(n-1)(1+x)^{n-2}]$$
And I think that I should substitutes something like $1,\zeta_3, \zeta_3^2$, the cube roots of unity, but I can't get it, can anyone help? thank you very much!
 A: We can write
$$0^2\binom n0+3^2\binom n3+6^2\binom n6+\cdots+\biggl(3\Bigl\lfloor\frac n3\Bigr\rfloor\biggr)^2\binom n{3\lfloor n/3\rfloor}=\sum_{\substack{k\in\mathbb Z\\3\mid k}}k^2\binom nk$$
(recall that $\binom pq=0$ when $q<0$ or $q>p$). On the other hand, according to your post we have
$$\sum_{k\in\mathbb Z}\binom nkk^2x^k=nx\bigl[(1+x)^{n-1}+(n-1)x(1+x)^{n-2}\bigr]=F(x)\,.$$
Therefore, applying series multisection we get
$$\sum_{\substack{k\in\mathbb Z\\3\mid k}}\binom nkk^2x^k=\frac13\sum_{k=0}^2F(\zeta_3^kx)\,.$$
Finally, take $x=1$.
A: Take $\omega$ as one of the other third roots of 1, so $\omega^3 = 1$ and $\omega^2 + \omega + 1 = 0$.
Use the operator $z D = z \dfrac{d}{d z}$, and consider the sum:
$$
\begin{align*}
S(z) &= \sum_k \binom{n}{k} z^k = (1 + z)^n \\
(z D)^2 S(z) &= \sum_k k^2 \binom{n}{k} z^k
              = n z (1 + z)^{n - 2} (n z + 1)
\end{align*}
$$
Now use the fact that if $R(z) = \sum_k r_k z^k$:
$$
\frac{R(z) + R(\omega z) + R(\omega^2 z)}{3} = \sum_k r_{3 k} z^{3 k}
$$
Need to evaluate the expression for the sum given above at 1, $\omega$, and $\omega^2 = \overline{\omega}$, add up and simplify.
