Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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