Tight bounds on the sum of the $j$th power of the first $n$ natural number?

Question

What are the tight bounds for $S_{n,j}=\sum_{k=1}^n k^j$? Where $O(j)=O(n^3)$.

Answer 1

Simplest bounds are: for $j > 0$

$$ \dfrac{n^{j+1}}{j+1} = \int_0^{n} x^j \; dx < \sum_{k=1}^n k^j \le \int_1^{n+1} x^j\; dx = \dfrac{(n+1)^{j+1}-1}{j+1}$$

Tighter bounds can be obtained by using a few terms of Faulhaber's formula. Thus if $j \ge 4$

$$ \sum_{k=1}^n k^j = \frac{n^{j+1}}{j+1} + \frac{1}{2} n^j + \frac{j}{12} n^{j-1} - \frac{j(j-1)(j-2)}{720} n^{j-3} + \frac{j(j-1)(j-2)(j-3)(j-4)}{30240} n^{j-4} - \ldots$$

so for sufficiently large $n$, a lower bound is $$ \frac{n^{j+1}}{j+1} + \frac{1}{2} n^j + \frac{j}{12} n^{j-1} - \frac{j(j-1)(j-2)}{720} n^{j-3}$$ and an upper bound is $$ \frac{n^{j+1}}{j+1} + \frac{1}{2} n^j + \frac{j}{12} n^{j-1} - \frac{j(j-1)(j-2)}{720} n^{j-3} + \frac{j(j-1)(j-2)(j-3)(j-4)}{30240} n^{j-4} $$