# Thread: Approximation and error formula

1. ## Approximation and error formula

Show for $\displaystyle p=0,1,2,\ldots$ that $\displaystyle \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 $\displaystyle f'$ exists and is continuous on $\displaystyle [0,1]$, then for each $\displaystyle n$ there exists $\displaystyle \xi_n \in [0,1,]$ such that $\displaystyle \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 \displaystyle \sum^n_{k=1} k^p$ supposedly by error bound $\displaystyle O(n^p)$.

Attemp:

Let $\displaystyle f(x) = x^p$, then $\displaystyle \displaystyle \sum^n_{k=1} k^p$ can be approximated by $\displaystyle \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 $\displaystyle 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 \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 \displaystyle f(x)=x^p$

we get

$\displaystyle \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 \displaystyle x=\frac{y}{n} \ \ \xi=\frac{\eta}{n}$

we get

$\displaystyle \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 \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.