2
$\begingroup$

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

$\endgroup$

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.

3
$\begingroup$

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

$\endgroup$

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