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

This question already has an answer here:

Here $ 1<N<10^9$ and $0<k<50$

So we have to calculate it in order of $O(\log N)$.

share|cite|improve this question

marked as duplicate by MJD, Amzoti, Dennis Gulko, Norbert, Davide Giraudo Mar 10 '13 at 20:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

See Faulhaber's Formula. – JavaMan Mar 10 '13 at 18:24
Also… and… and probably several others. – MJD Mar 10 '13 at 18:56

Very interesting question, using generating functions

The multiply-by-$n$ operator $xD$, is defined by $$ (xD)^k f \rightarrow^{ops} \{n^k a_n\}_{n\geq 0} $$ where $f$ is a ordinary power series (ops) generating function for $\{a_n\}_0^\infty$. That means that $f = \sum_n a_n x^n $.

Begin with the fact that $$ \sum_{n=0}^{N} x^n= \frac{x^{N+1} - 1}{x-1} $$

Then, apply $(xD)^k$ operator both sides of this relation and then set $x=1$, $$ \sum_{n=1}^{N} n^k = (xD)^k \left\{{\frac{x^{N+1}-1}{x-1}}\right\}|_{x=1} $$ By, example, for $k=2$, then $$ \sum_{n=1}^{N} n^2 = \frac{N(N+1)(2N+1)}{6} $$

share|cite|improve this answer

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