Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

marked as duplicate by MJD, Amzoti, Dennis Gulko, userNaN, 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.

2  
See Faulhaber's Formula. –  JavaMan Mar 10 '13 at 18:24
2  
    
Also math.stackexchange.com/questions/18983/… and math.stackexchange.com/questions/65861/… and probably several others. –  MJD Mar 10 '13 at 18:56

1 Answer 1

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|improve this answer

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