# 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!

-
And what were you trying to prove? – Abhijit Mar 24 '13 at 18:35
@marty : Might you have meant you are trying to evaluate that sum, rather than that you are trying to "prove" it? It's not the kind of thing one proves. – Michael Hardy Mar 24 '13 at 18:52
The last summand must be $\Bigl(3\Bigl\lfloor\dfrac n3\Bigr\rfloor\Bigr)^2\dbinom n{3\lfloor n/3\rfloor}$ instead of $\Bigl\lfloor \dfrac n3\Bigr\rfloor^2\dbinom n{\lfloor n/3\rfloor}$ – Matemáticos Chibchas Mar 24 '13 at 19:13

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

-

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.

-