0
$\begingroup$

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

$\endgroup$
8
  • 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$ Jul 15, 2016 at 21:44
  • $\begingroup$ Yes. $j=6n^3$. So the Faulhaber's formula can not readily used. $\endgroup$
    – mike
    Jul 15, 2016 at 22:06
  • 1
    $\begingroup$ Why do you think it can't be readily used? $\endgroup$ Jul 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$ Jul 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$ Jul 17, 2016 at 21:30

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .