What are the tight bounds for $S_{n,j}=\sum_{k=1}^n k^j$? Where $O(j)=O(n^3)$.
-
1$\begingroup$ Do you really mean that $j = O(n^3)$, or do you want bounds where the difference between upper and lower bounds is $O(n^3)$? $\endgroup$– Robert IsraelJul 15, 2016 at 21:44
-
$\begingroup$ Yes. $j=6n^3$. So the Faulhaber's formula can not readily used. $\endgroup$– mikeJul 15, 2016 at 22:06
-
1$\begingroup$ Why do you think it can't be readily used? $\endgroup$– Robert IsraelJul 16, 2016 at 0:33
-
1$\begingroup$ With $j$ so large the $k=n$ term is much larger than the others: $n^{6n^3}/(n-1)^{6n^3} \approx e^{6n^2 + 3n+2}$. So $n^j$ is quite a good lower bound. A good upper bound is $n^j (1 + n/(j+1))$. $\endgroup$– Robert IsraelJul 16, 2016 at 0:43
-
1$\begingroup$ $n^j$ plus the upper bound from my answer for the sum from $1$ to $n-1$ (I left out the term $-1/(j+1)$, which is very small compared to $n^j$. $\endgroup$– Robert IsraelJul 17, 2016 at 21:30
1 Answer
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} $$