# $\sum _{k=1}^{n-1}k^p \lt \frac {n^{p+1}} {p+1} \lt \sum _{k=-1}^{n}k^p$

I'm going through a proof of the theorem that says $\int_0^bx^pdx = \frac {b^{p+1}}{p+1}$, and it begins with the inequality. $\sum _{k=1}^{n-1}k^p \lt \frac {n^{p+1}} {p+1} \lt \sum _{k=-1}^{n}k^p$ What I'm having trouble understanding where this middle term came from.

-
induction doesn't help? –  Arjang Mar 2 '13 at 2:33
I'm not trying to prove it. I'm trying to see where it came from. I know that the left and right side are partitions of the function $x^p$ on the interval $[0,b]$, but what I'm trying to figure out is where the middle equality came from. –  AlexHeuman Mar 2 '13 at 2:35
The induction comment was meant toward showing the inequalities. –  Alex R. Mar 2 '13 at 2:37
looks like the upper and lower bounds for a Riemann Integral, no? –  Arjang Mar 2 '13 at 2:37
The middle term seems to be the integral, the left and right terms are the bounding rectangles, one bounds the integral from above and the other one from below, so when the integral in the middle is evaluated to the term in middle, it will be bounded above and below by the same values. Have you seen a picture of Rieman integral with rectangles above and below the function? –  Arjang Mar 2 '13 at 2:42

Since this inequality is being used to prove an integral, perhaps a non-calculus proof would be best.

At the end of this answer is a simple inductive proof of Bernoulli's Inequality:

For non-negative integer $n$ and $x\ge-1$, $$1+nx\le(1+x)^n\tag{1}$$ Applying $(1)$ \begin{align} 1-\frac{p+1}{k}&\le\left(1-\frac1k\right)^{p+1}\\ k^{p+1}-(p+1)k^p&\le(k-1)^{p+1}\\ k^{p+1}-(k-1)^{p+1}&\le(p+1)k^p\tag{2} \end{align} Applying $(1)$ \begin{align} 1+\frac{p+1}{k-1}&\le\left(1+\frac1{k-1}\right)^{p+1}\\ \frac{p+1}{k-1}&\le\left(1+\frac1{k-1}\right)^{p+1}-1\\ (p+1)(k-1)^p&\le k^{p+1}-(k-1)^{p+1}\tag{3} \end{align} Combining $(2)$ and $(3)$, $$(p+1)(k-1)^p\le k^{p+1}-(k-1)^{p+1}\le(p+1)k^p\tag{4}$$ Summing $(4)$ from $1$ to $n$ and dividing by $p+1$ yields $$\sum_{k=0}^{n-1}k^p\le\frac{n^{p+1}}{p+1}\le\sum_{k=1}^nk^p\tag{5}$$ Note that for $p=0$, we have equalty in $(5)$. I've added a strict case to the proof of Bernoulli that, when replacing $(1)$ for $n\ge2$, yields that for $p\ge1$, we have strict inequality: $$\sum_{k=0}^{n-1}k^p\lt\frac{n^{p+1}}{p+1}\lt\sum_{k=1}^nk^p\tag{6}$$

-

I didn't realize I was going to get something slightly different of what you're being given when I started to write this, but I leave you an idea to prove that $$\int_0^a x^pdx=\frac{a^{p+1}}{p+1}$$ The idea is the following:

PROP Let $$A(n)=\sum_{k=1}^n k^p$$

Then $A(n)=\frac{n^{p+1}}{p+1}+P_p(n)$ where $\operatorname{deg}P\leq p$

PROFF By induction on $p$.

For $p=1$, we obtain $$\sum\limits_{k = 1}^n k = {{{n^2}} \over 2} + {n \over 2}$$ Assume true for $m\leq p-1$ and consider $p$. We exploit the fact that $${(k + 1)^{p+1}} - {k^{p+1}} = \sum\limits_{m = 0}^{p} {p+1\choose m}{{k^m}}$$

We then have, after summing from $k=1$ to $p$ that $${(n + 1)^{p + 1}} - 1 = \sum\limits_{m = 0}^p {\left( \matrix{ p + 1 \cr m \cr} \right)} \sum\limits_{k = 1}^n {{k^m}}$$

or

$${(n + 1)^{p + 1}} - 1 = \sum\limits_{m = 0}^{p - 1} {\left( \matrix{ p + 1 \cr m \cr} \right)} \sum\limits_{k = 1}^n {{k^m}} + \left( {p + 1} \right)\sum\limits_{k = 1}^n {{k^p}}$$ Now, our inductive hypothesis is that

$$\sum\limits_{k = 1}^n {{k^m}} = {{{n^{m + 1}}} \over {m + 1}} + {P_m}\left( n \right)$$

This gives us that

$${{{{(n + 1)}^{p + 1}}} \over {p + 1}} - {1 \over {p + 1}} - {1 \over {p + 1}}\sum\limits_{m = 0}^{p - 1} {\left( \matrix{ p + 1 \cr m \cr} \right)} \left( {{{{n^{m + 1}}} \over {m + 1}} + {P_m}\left( n \right)} \right) = \sum\limits_{k = 1}^n {{k^p}}$$

Now, let's look at that big mess above. Observe that by the binomial theorem, we can write $${{{{(n + 1)}^{p + 1}}} \over {p + 1}} = {{{n^{p + 1}}} \over {p + 1}} + {Q_p}\left( n \right)$$ where the degree of $Q_p$ is $p$. Note also that

$$\sum\limits_{m = 0}^{p - 1} {\left( \matrix{ p + 1 \cr m \cr} \right)} \left( {{{{n^{m + 1}}} \over {m + 1}} + {P_m}\left( n \right)} \right) = \sum\limits_{m = 0}^{p - 1} {\left( \matrix{ p + 1 \cr m \cr} \right)} \left( {{{{n^{m + 1}}} \over {m + 1}}} \right) + \sum\limits_{m = 0}^{p - 1} {\left( \matrix{ p + 1 \cr m \cr} \right)} {P_m}\left( n \right)$$

The first term on the right is a polynomial of degree $p$. On the other hand, the sum of all the polynomials on the left is of degree $\leq p$, since it's a sum of polynomials of degree at most $p$. All in all, we may write $${{{{(n + 1)}^{p + 1}}} \over {p + 1}} - {1 \over {p + 1}} - {1 \over {p + 1}}\sum\limits_{m = 0}^{p - 1} {\left( \matrix{ p + 1 \cr m \cr} \right)} \left( {{{{n^{m + 1}}} \over {m + 1}} + {P_m}\left( n \right)} \right) = {{{n^{p + 1}}} \over {p + 1}} + {W_p}\left( n \right)$$ where $W$ has degree at most $p$. Thus $$\sum\limits_{k = 1}^n {{k^p}} = {{{n^{p + 1}}} \over {p + 1}} + {W_p}\left( n \right)$$ and the proposition is proven.

Now, we look at our integral approximation, which is $${1 \over n}\sum\limits_{k = 1}^n {{{\left( {{{ak} \over n}} \right)}^p}}$$

Because of the above, we have that $${1 \over n}\sum\limits_{k = 1}^n {{{\left( {{{ak} \over n}} \right)}^p}} = {{{a^{p + 1}}} \over {p + 1}} + {a^{p + 1}}{{{W_p}\left( n \right)} \over {{n^{p + 1}}}}$$

Since $W_p(n)$ has degree at most $p$, it follows that $${{{W_p}\left( n \right)} \over {{n^{p + 1}}}}\to 0$$

when $n\to \infty$, so we conclude that

$$\mathop {\lim }\limits_{n \to \infty } {1 \over n}\sum\limits_{k = 1}^n {{{\left( {{{ak} \over n}} \right)}^p}} = {{{a^{p + 1}}} \over {p + 1}}$$

-

We use the fact that $$a^p-b^p=(a-b)\sum_{k=0}^{p-1}a^kb^{p-k-1}$$ Because of that, we have $$\tag 1 n^p<\frac{(n+1)^{p+1}-n^{p+1}}{p+1}<(n+1)^p$$

Indeed, by the above $${\left( {n + 1} \right)^{p + 1}} - {n^{p + 1}} = \sum\limits_{k = 0}^p {{n^k}} {\left( {n + 1} \right)^{p - k}}$$

that is $${\left( {n + 1} \right)^{p + 1}} - {n^{p + 1}} = \sum\limits_{k = 0}^p {{{\left( {{n \over {n + 1}}} \right)}^k}} {\left( {n + 1} \right)^p}$$

but for any choice of $n$ $${n \over {n + 1}} < 1$$ so that$${\left( {n + 1} \right)^{p + 1}} - {n^{p + 1}} = \sum\limits_{k = 0}^p {{{\left( {{n \over {n + 1}}} \right)}^k}} {\left( {n + 1} \right)^p} < \sum\limits_{k = 0}^p {{{\left( {n + 1} \right)}^p} = \left( {p + 1} \right)} {\left( {n + 1} \right)^p}$$ and one side is done. But similarily, $${{n + 1} \over n} > 1$$ for any choice of $n$ so $$\left( {p + 1} \right){n^p} = \sum\limits_{k = 0}^p {{n^p}} < \sum\limits_{k = 0}^p {{{\left( {{{n + 1} \over n}} \right)}^{p - k}}{n^p}} = \sum\limits_{k = 0}^p {{{\left( {n + 1} \right)}^{p - k}}{n^k}} = {\left( {n + 1} \right)^{p + 1}} - {n^{p + 1}}$$ and we get what we wanted.

What you want follows from summing telescopically the inequalities in $(1)$.

-
Could you not just say that $n^p\le n^k(n+1)^{p-k}\le(n+1)^p$? Otherwise, it looks good (+1) –  robjohn Mar 16 '13 at 16:39

For $p>0$ this can be proved easily,

$\sum _{k=1}^{n-1}k^p < \frac {n^{p+1}} {p+1} < \sum _{k=-1}^{n}k^p$

Suppose this is true for $n=m$

Then for $n=m+1$ we have,

$\sum _{k=1}^{m}k^p = \sum _{k=1}^{m-1}k^p+m^p$

If we can show that $m^p<\displaystyle \frac{(m+1)^{p+1}-m^{p+1}}{p+1}$ then we are done.

This can easily be proved using mean value theorem,

Consider the function $f(x)=x^{p+1}$,

Applying mean value theorem,

$\exists c\in(m,m+1)$ such that ,

$\displaystyle \frac{(m+1)^{p+1}-m^{p+1}}{m+1-m}=f'(c)$

$\displaystyle \frac{(m+1)^{p+1}-m^{p+1}}{m+1-m}=(p+1)c^p>(p+1)m^p$

$\displaystyle \Rightarrow \frac{(m+1)^{p+1}-m^{p+1}}{p+1}>m^p$

The right side can also be proved similarly.

-