Estimating $\frac{\sum_{r = 1}^{N} r^n}{N^n}$, getting a good numerical approximaion for large $N$

Question

I am trying to find an accurate estimate for

$$f(n,N) = \frac{\sum^{N}_{r = 1} r^n}{N^n}$$

for large values of $N$.

I know the result that as ${N\to \infty}$, the $\frac{f(n,N)}{N}$ assumes value of $\frac{1}{n+1}$.

So I try to approximate $f(n,N)$ as $\frac{N}{n+1}$. Now what I have found running some python program that a better estimation for the sum is $\frac{N}{n+1} + \frac{1}{2}$ which fits much more exactly with correct value.

from math import *

n = 40
N = 1000000

s = 0
for i in range(N+1):
    s += i**n

s /= N**n
print("s:  ", s)

s1 = N/(n+1)
print("s1: ", s1)

s2 = (N)/(n+1) +1 
print("s2: ", s2)

av = (s1+s2)/2
print("av: ", av)

perr_s_av = fabs(av-s)/s * 100
print("error (av): ", perr_s_av)

perr_s_s1 = fabs(s1-s)/s * 100
print("error (s1): ", perr_s_s1)

The output is this

s:   24390.743905772357
s1:  24390.243902439026
s2:  24391.243902439026
av:  24390.743902439026
error (av):  1.3666376215028742e-08
error (s1):  0.0020499716419575546

It is clear that the value $\frac{N}{n+1} + \frac{1}{2}$ is numerically much better approximation, why is this so, am I missing something

EDIT:

My assumption is that the next term of the polynomial $f(n, N)$ must be $\frac{1}{2}$ which is leading to this result, ie the polynomial form of $f(n, N) = \frac{N}{n+1} + \frac{1}{2} + \text{lower powers of N}$

Answer 1

The way to compute this sum, is to find a polynomial of degree $N+1$ such that $$ P(X+1)-P(X)=X^n.$$ Assuming that such a polynomial has been found, note that since we only ask for the difference of $P(X+1)-P(X)$ do be something, we can assume that $P(0)=0$. Then You see that $$ \sum_{r=1}^N r^n = \sum_{r=1}^N P(r+1) -P(r) = P(N+1)-P(0)=P(N+1). $$ Suppose $P(X)= a_{n+1} X^{n+1} +a_{n}X^n + \ldots +a_1 X.$ Then, expanding the leading terms by the binomial rule, $$ P(N+1)= a_{n+1} N^{n+1} + \left((n+1) a_{n+1} +a_{n}\right) N^{n} + \ldots $$ and therefore

$$ \frac{P(N+1)}{N^n} = a_{n+1} N + \left((n+1) a_{n+1} +a_{n}\right) + O(N^{-1}). \quad\quad (1) $$

So what you are asking is: what are the first two terms of $P$? To make our life simpler, let us differentiate the relationship $n$ times. This gives $$ P^{(n)}(X+1)-P^{(n)}(X) = (n+1)!a_{n+1} (X + 1)+n!a_n - \left((n+1)!a_{n+1} X+n!a_n\right) = n! $$ so $$a_{n+1} = \frac{1}{n+1}.$$ Now differentiate only $(n-1)$ times : $$ P^{(n-1)}(X+1)-P^{(n-1)}(X)= \frac{(n+1)!}{2} a_{n+1} (X + 1)^2 + n!a_n (X + 1) - \left(\frac{(n+1)!}{2} a_{n+1} X^2 + n!a_n X \right) = n! X $$ So using what we already know, $$ \frac{1}{2} (X + 1)^2 + a_n (X + 1) - \left(\frac{1}{2}X^2 + a_n X \right) = X $$ in other words $$ X+\frac{1}{2} +a_n = X, $$ or $a_n=-\frac{1}{2}$. Plugin this back into (1), you find

$$ \frac{P(N+1)}{N^n} = \frac{1}{n+1} N + \frac{1}{2} + O(N^{-1}). \quad\quad (1) $$

Answer 2

Using generalized harmonic numbers $$f(n,N) = \frac{\sum^{N}_{r = 1} r^n}{N^n}= \frac{H_N^{(-n)} }{N^n}$$ Using asymptotics for large $N$ $$f(n,N) = \frac{N}{n+1}+\frac{1}{2}+\frac{n}{12 N}-\frac{n(n-1)(n-2)}{720 N^3}+O\left(\frac{1}{N^5}\right)$$

The above approximation gives $$f(40,10^6) \sim \frac{1000020500136666666663291}{41000000000000000000} $$ showing a relative error equal to $1.07\times 10^{-29}$%.