0

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

mike
  • 5,604
  • 1
    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)$? – Robert Israel Jul 15 '16 at 21:44
  • Yes. $j=6n^3$. So the Faulhaber's formula can not readily used. – mike Jul 15 '16 at 22:06
  • 1
    Why do you think it can't be readily used? – Robert Israel Jul 16 '16 at 00:33
  • 1
    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))$. – Robert Israel Jul 16 '16 at 00:43
  • What I meant is that the $m+1$th term is larger than the $m$th term in your series. So the last term dominates, as shown in your last comment. Thanks a lot! – mike Jul 16 '16 at 02:11
  • @RobertIsrael: How do you get the upper bound $n^j (1 + n/(j+1))$? Thanks – mike Jul 16 '16 at 22:43
  • 1
    $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$. – Robert Israel Jul 17 '16 at 21:30
  • Nice result! We can also replace j+1 by j and obtain $n^j(1+n/j)$ as the upper bound! – mike Jul 18 '16 at 05:59

1 Answers1

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

Robert Israel
  • 448,999