# Thread: Approximation and error formula

1. ## Approximation and error formula

Show for $p=0,1,2,\ldots$ that $\displaystyle \sum^n_{k=1} k^p = \frac{n^{p+1}}{p+1} + O(n^p)$.

You may assume the error formula for the right rectangle rule: if $f'$ exists and is continuous on $[0,1]$, then for each $n$ there exists $\xi_n \in [0,1,]$ such that $\displaystyle \int^1_0 f(x) dx = h \sum^n_{k=1} f(kh) - \frac{1}{2} f'(\xi_n) h, \qquad h = \frac{1}{h}$, which is greater than $\displaystyle \sum^n_{k=1} k^p$ supposedly by error bound $O(n^p)$.

Attemp:

Let $f(x) = x^p$, then $\displaystyle \sum^n_{k=1} k^p$ can be approximated by $\displaystyle \int^n_0 f(x) dx = \int^n_0 x^p dx = \left[\frac{1}{p + 1} x^{p+1} \right]^n_0 = \frac{1}{p+1} n^{p+1}$.

But I don't understand how to obtain the big O bound of $O(n^p)$ using the right rectangle rule. I cannot see how the rule is relevant. Can someone please help?

2. May be this helps.
We have

$
\displaystyle
\int_0^1 f(x)dx=\frac{1}{n} \sum_{k=1}^n(\frac{k}{n})^p-\frac{1}{2}f'(\xi_n)\frac{1}{n}
$

Inserting

$
\displaystyle
f(x)=x^p
$

we get

$
\displaystyle
\int_0^1 x^pdx=\frac{1}{n} \sum_{k=1}^n(\frac{k}{n})^p-\frac{1}{2}p(\xi_n)^{p-1}\frac{1}{n}
$

Making substitution

$
\displaystyle
x=\frac{y}{n} \ \ \xi=\frac{\eta}{n}
$

we get

$
\displaystyle
\int_0^n (\frac{y}{n})^p\frac{dy}{n}=\frac{1}{n} \sum_{k=1}^n(\frac{k}{n})^p-\frac{1}{2}p(\frac{\eta_n}{n})^{p-1}\frac{1}{n}
$

$
\displaystyle
\int_0^n y^pdy=\sum_{k=1}^n \ k^p-\frac{1}{2}pn \ \eta_n^{p-1}
$

3. Thank you. You have solved my problem.