# Evaluating $\lim\limits_{n\to\infty} \left(\frac{1^p+2^p+3^p + \cdots + n^p}{n^p} - \frac{n}{p+1}\right)$

Evaluate $$\lim_{n\to\infty} \left(\frac{1^p+2^p+3^p + \cdots + n^p}{n^p} - \frac{n}{p+1}\right)$$

-
This is Problem 2.3.12 (g) from Kaczor-Nowak: Problems in Mathematical Analysis I. The problem is stated on p.37 and a solution is given on p.184. This solution uses Stolz-Cesaro Theorem. –  Martin Sleziak May 25 '12 at 10:36

This is a nice little question. I am assuming that $p \in \mathbb{Z}^+$, though same could be said about it when $p \notin \mathbb{Z}^+$. Before getting to the answer lets experiment a bit for small positive integers $p$. To start off, you could try for some values $p$.

For $p=1$, we get $$\lim_{n \rightarrow \infty} \left(\frac{ \dfrac{n(n+1)}{2}}{n} - \frac{n}{1+1} \right) = \lim_{n \rightarrow \infty} \frac12 = \frac12$$

For $p=2$, we get $$\lim_{n \rightarrow \infty} \left(\frac{ \dfrac{n(n+1)(2n+1)}{6}}{n^2} - \frac{n}{2+1} \right) = \lim_{n \rightarrow \infty} \left(\frac{(n+1)(n+1/2)}{3n} - \frac{n}3 \right)\\ = \lim_{n \rightarrow \infty} \left(\frac{n}3 + \frac12 + \frac1{6n} - \frac{n}3 \right)= \frac12$$

For $p=3$, we get $$\lim_{n \rightarrow \infty} \left(\frac{ \dfrac{n^2(n+1)^2}{4}}{n^3} - \frac{n}{3+1} \right) = \lim_{n \rightarrow \infty} \left(\frac{n^2 + 2n + 1}{4n} - \frac{n}4 \right)\\ = \lim_{n \rightarrow \infty} \left(\frac{n}4 + \frac12 + \frac1{4n} - \frac{n}4 \right)= \frac12$$

Hence, we would guess that it is $\dfrac12$ independent of $p$. And this turns out to be right.

Let us denote $1^p + 2^p + \cdots n^p = P_p(n)$. This is a polynomial of degree $p+1$ and is given by $$P_p(n) = \frac1{p+1} \sum_{k=0}^p \dbinom{p+1}{k} B_k n^{p+1-k}$$ where $B_k$ are the Bernoulli numbers. These polynomials are related to the Bernoulli polynomials and there are some really nice results on these polynomials and more can be found here.

Hence, $$\dfrac{P_p(n)}{n^{p}} = \dfrac1{p+1} \sum_{k=0}^p \dbinom{p+1}{k} B_k n^{1-k} = \dfrac1{p+1} \left(B_0 n + (p+1) B_1 + \mathcal{O} \left(\frac1n\right) \right)$$ where $B_0 = 1$ and $B_1 = \frac12$. What you are looking for is $$\lim_{n \rightarrow \infty} \left(\dfrac{P_p(n)}{n^{p}} - \dfrac{n}{p+1} \right) = \lim_{n \rightarrow \infty} \left(\dfrac1{p+1} \left(n + (p+1) B_1 + \mathcal{O} \left(\frac1n\right) \right) - \dfrac{n}{p+1} \right)\\ = \lim_{n \rightarrow \infty} \left(B_1 + \mathcal{O} \left(\dfrac1n \right)\right)= B_1 = \frac12$$ independent of $p$.

Didier and Ragib Zaman have provided excellent solutions. You might also want to look at Euler–Maclaurin formula which is of significance in this context.

-
I very much doubt the above very nice proof is appropriate for high school level. I don't think there are many education systems around the globe that include big "o" notation, Bernoulli numbers and polynomials in their H.S. curriculum... –  DonAntonio May 24 '12 at 11:38
@DonAntonio The big O notation was only used as a short hand. It could have as well been written out. Also, Bernoulli numbers and polynomials are taught in high school. –  user17762 May 24 '12 at 11:51
Why are you vandalizing your answer? –  Potato Dec 9 '13 at 6:18
@Potato If people (both the users and those who run stack-exchange) are not nice, then why should I waste my time in answering questions and providing answers? –  user17762 Dec 9 '13 at 6:25
@user17762 I'm sorry people have not been nice. That is unfortunate. But why deprive others, many of them quite nice people, of your answers? –  Potato Dec 9 '13 at 6:26

The result is more general.

Fact: For any function $f$ defined on $[0,1]$ and regular enough, introduce $$A_n=\sum_{k=1}^nf\left(\frac{k}n\right),\quad B=\int_0^1f(x)\mathrm dx,\quad C=f(1)-f(0).$$ Then, $$\lim\limits_{n\to\infty}A_n-nB=\frac12C.$$

For any real number $p\gt0$, if $f(x)=x^p$, one sees that $B=\frac1{p+1}$ and $C=1$, which is the result in the question.

To prove the fact stated above, start from Taylor formula: for every $0\leqslant x\leqslant 1/n$ and $1\leqslant k\leqslant n$, $$f(x+(k-1)/n)=f(k/n)-(1-x)f'(k/n)+u_{n,k}(x)/n,$$ where $u_{n,k}(x)\to0$ when $n\to\infty$, uniformly on $k$ and $x$, say $|u_{n,k}(x)|\leqslant v_n$ with $v_n\to0$. Integrating this on $[0,1/n]$ and summing from $k=1$ to $k=n$, one gets $$\int_0^1f(x)\mathrm dx=\frac1n\sum_{k=1}^nf\left(\frac{k}n\right)-\frac1n\int_0^{1/n}u\mathrm du\cdot\sum_{k=1}^nf'\left(\frac{k}n\right)+\frac1nu_n,$$ where $|u_n|\leqslant v_n$. Reordering, this is $$A_n=nB+\frac12\frac1n\sum_{k=1}^nf'\left(\frac{k}n\right)-u_n=nB+\frac12\int_0^1f'(x)\mathrm dx+r_n-u_n,$$ with $r_n\to0$, thanks to the Riemann integrability of the function $f'$ on $[0,1]$. The proof is complete since $r_n-u_n\to0$ and the last integral is $f(1)-f(0)=C$.

-
+1. The all powerful Euler–Maclaurin!(en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula) –  user17762 May 24 '12 at 11:47

If we draw the graph of $x^p$ from $x=1$ to $x=n,$ divide it into unit length intervals and approximate each segment of area by a trapezium (this is known as the trapezoidal rule) then we see that $$\int^n_1 x^p dx \approx \sum_{k=1}^n k^p - \frac{n^p+1}{2}.$$ The integral on the left is precisely $\displaystyle \frac{n^{p+1} -1}{p+1},$ so for large $n$ (where the major contribution is from the dominant terms) we have $$\sum_{k=1}^n k^p \approx \frac{n^{p+1}}{p+1} + \frac{n^p}{2}$$ so your limit is $1/2.$

For a precise solution, we need the error term along with the trapezoidal rule, which is derived here. It gives : $$\int^b_a f(x) dx = \frac{b-a}{2} ( f(a) + f(b) ) - \frac{(b-a)^3 }{12} f''(\zeta)$$ for some $\zeta \in [a,b].$ For $f(x)=x^p$ we have $f''(x) = p (p-1)x^{p-2}$ which is largest at $x=b$, the right end point. So the sum of the error terms in our application of the trapezoidal rule is at largest $$\frac{p(p-1)}{12} (2^{p-2} + 3^{p-2} + \cdots + n^{p-2}).$$ The sum in the brackets is overestimated by $\int^{n+1}_1 x^{p-2} dx= \frac{(n+1)^{p-1}-1}{p-1},$ so we get that $$\sum_{k=1}^n k^p = \frac{n^{p+1}}{p+1} + \frac{n^p}{2} + E_n$$ where $E_n$ is an error term that satisfies $\displaystyle \lim_{n\to\infty} \frac{E_n}{n^p} = 0$ which proves your limit.

-
+1 Now this looks as something an advanced student in a very good (mathematicwise) high school could grasp. –  DonAntonio May 24 '12 at 12:00
@Chris I just looked over my post and realized a horrible slip of the mind, it's no wonder why you didn't understand it before! The only wonder is how it got 7 upvotes in that condition lol. It's fine now though. Check out the edit and edit history for clarification. –  Ragib Zaman May 25 '12 at 0:56
@RagibZaman Only the ideas are important. Yes you made a small algebraic error before but that doesn't really matter. :) –  user17762 May 25 '12 at 3:50
I thought of $\int^n_1 x^p dx \approx \sum_{k=1}^n k^p - \frac{n^p+1}{2}$ but this doesn't modify the final result. –  Chris's sis the artist May 25 '12 at 10:17
@Ragib Zaman: i totally agree with what Marvis said: "Only the ideas are important". It's OK. –  Chris's sis the artist May 25 '12 at 10:21

another method, using Stolz–Cesàro theorem: let ${ x }_{ n }=\left( p+1 \right) \left( { 1 }^{ p }+{ 2 }^{ p }+...+{ n }^{ p } \right) -{ n }^{ p+1 },{ y }_{ n }=\left( p+1 \right) { n }^{ p }$ $$\lim _{ x\rightarrow \infty }{ \frac { { x }_{ n+1 }-{ x }_{ n } }{ { y }_{ n+1 }-{ y }_{ n } } = } \lim _{ x\rightarrow \infty }{ \frac { \left( p+1 \right) { \left( n+1 \right) }^{ p }-{ \left( n+1 \right) }^{ p+1 }+{ n }^{ p+1 } }{ \left( p+1 \right) \left( { \left( n+1 \right) }^{ p }-{ n }^{ p } \right) } = } \\ =\lim _{ x\rightarrow \infty }{ \left( \frac { \left( p+1 \right) \left( { n }^{ p }+p{ n }^{ p-1 }+\frac { p\left( p-1 \right) }{ 2 } { n }^{ p-2 }+...+1 \right) }{ \left( p+1 \right) \left( { n }^{ p }+p{ n }^{ p-1 }+\frac { p\left( p-1 \right) }{ 2 } { n }^{ p-2 }+...+1-{ n }^{ p } \right) } \right) + } \\ +\frac { -{ n }^{ p+1 }-\left( p+1 \right) { n }^{ p }-\frac { p\left( p+1 \right) }{ 2 } { n }^{ p-1 }-...-1+{ n }^{ p+1 } }{ \left( p+1 \right) \left( { n }^{ p }+p{ n }^{ p-1 }+\frac { p\left( p-1 \right) }{ 2 } { n }^{ p-2 }+...+1-{ n }^{ p } \right) }$$ let's cobmine all coefficients of n,then divide numerator and denominator by $n^{ p-1 }$ and define sum of the all terms no more -1 power with $o\left( \frac { 1 }{ n } \right)$ $$\\ \\ \lim _{ x\rightarrow \infty }{ \frac { { x }_{ n+1 }-{ x }_{ n } }{ { y }_{ n+1 }-{ y }_{ n } } = } \lim _{ x\rightarrow \infty }{ \frac { \frac { p\left( p+1 \right) }{ 2 } +o\left( \frac { 1 }{ n } \right) }{ p\left( p+1 \right) +\left( \frac { 1 }{ n } \right) } =\frac { 1 }{ 2 } } \\$$

-