Evaluate $$\lim_{n\to\infty} \left(\frac{1^p+2^p+3^p + \cdots + n^p}{n^p} - \frac{n}{p+1}\right)$$
Evaluating $\lim\limits_{n\to\infty} \left(\frac{1^p+2^p+3^p + \cdots + n^p}{n^p} - \frac{n}{p+1}\right)$
-
2This is Problem 2.3.12 (g) from Kaczor-Nowak: Problems in Mathematical Analysis I. The problem is stated on [p.37](http://books.google.com/books?id=HrO6QzUHU-gC&pg=PA37) and a solution is given on [p.184](http://books.google.com/books?id=HrO6QzUHU-gC&pg=PA184). This solution uses [Stolz-Cesaro Theorem](http://en.wikipedia.org/wiki/Stolz%E2%80%93Ces%C3%A0ro_theorem). – 2012-05-25
5 Answers
Hint for another method:
You can use Faulhaber's formula: $$1^p+2^p+\dots+n^p=\frac1{p+1}\sum_{k=0}^p\binom{p+1}kB_k\, n^{p+1-k},$$ where $B_k$ denotes the $k$-th Bernoulli number (with the convention that $B_1=-\frac12$).
The result is more general.
Fact: For any function $f$ regular enough on $[0,1]$, introduce $$ A_n=\sum_{k=1}^nf\left(\frac{k}n\right)\qquad B=\int_0^1f(x)\mathrm dx\qquad 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 says that $$ 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+1. The all powerful Euler–Maclaurin!(http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula) – 2012-05-24
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$.
Users Did and Ragib Zaman have provided excellent solutions. You might also want to look at Euler–Maclaurin formula which is of significance in this context.
-
1I 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... – 2012-05-24
-
0@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. – 2012-05-24
-
0I agree about the big O notation. About Bernoulli numbers and pol's: I thoroughly know the education system in Israel and Mexico and, to a less extent, in USA. None of them includes anything even close to Bernoulli pol's/numbers *in general* (which means: perhaps some elite, most probably private high schools, do. I know none but I can't discard them). I also know a little about the system in Spain and it's the same as far as I know. – 2012-05-24
-
0Kudos for the indian h.s. education. In my globe's zone this kind of stuff is not even mentioned, let alone worked on. – 2012-05-24
-
0@Chris Kindly accept one of the answers if you have understood and obtained what you want. You may want to read here (http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work) on how and why to accept answers. Try to accept answers for the other questions you have asked on the site as well, if you are satisfied with the quality of answers. – 2012-05-24
-
0@Chris Often there are lot of good answers and it gets difficult for the questioner to choose which one to accept :). But do accept one, since it is over all a good thing for the entire community. – 2012-05-24
-
0@Marvis, nice answer. One nitpick: it might be more clear to write $(p+1)B_1$ instead of $B_1(p+1)$ to avoid confusion between the Bernoulli numbers and the Bernoulli polynomials you mentioned. – 2012-05-25
-
0@AntonioVargas Yes. I have changed it accordingly. – 2012-05-25
-
2Why are you vandalizing your answer? – 2013-12-09
-
0Well... its my answer. I am copying it onto my local machine. Why should stack exchange benefit out of my answers? – 2013-12-09
-
0@user17762 Why not? They clearly help people, as evidenced by the upvotes. Deleting them seems purely spiteful. – 2013-12-09
-
1@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? – 2013-12-09
-
1@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? – 2013-12-09
-
0@user17762: You need a transparent attitude, in mathematics. – 2013-12-09
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.
-
2+1 Now this looks as something an advanced student in a very good (mathematicwise) high school could grasp. – 2012-05-24
-
0@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. – 2012-05-25
-
0@RagibZaman Only the ideas are important. Yes you made a small algebraic error before but that doesn't really matter. :) – 2012-05-25
-
0I 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. – 2012-05-25
-
0@Chris Yes once again, I'll edit that too! – 2012-05-25
-
1@Ragib Zaman: i totally agree with what Marvis said: "Only the ideas are important". It's OK. – 2012-05-25
-
0You have to be more careful with your limits! What does $f(n) \approx g(n)$ mean? If you want it to mean the same as $f(n)-g(n) \approx 0$, then your statement of the trapezoidal rule is false. If it doesn't mean the same as $f(n)-g(n) \approx 0$, then your conclusion is false. – 2012-05-25
-
0@Chris: It's really up to Ragib to provide more details. What does the $\approx$ sign in the first equation mean, precisely? – 2012-05-25
-
0I thought it was understood my estimates and overall solution was not precise, merely something to satisfy a high schooler. I used $\approx$ to denote dominant behaviour in the way some might say that for large $n$, $n^{10} + n \approx n^{10}$ even though the difference goes to infinity. It doesn't matter if the error goes to infinity, as long as it does so more slowly than $n^p$ so that after dividing by $n^p$ and taking limits, that term is still $0.$ – 2012-05-25
-
0If you want to give a water tight solution that is still understandable to a high schooler, you will have to spend a bit more time to derive the error estimate that goes along with the trapezoidal rule. Use integration by parts a few times to show them how Taylor series arise, then show them [this](http://www.maths.usyd.edu.au/u/david/mc3/nm/addlectmat/3NML7.pdf). It shows the error in using the trapezoidal rule on $f$ is (up to constant factors) is $f''$, so for our application, the error is at most $n^{p-2}$, which suffices to find this limit. – 2012-05-25
-
0@Chris: Just so you understand: this is not a proof! It's just a motivation, which suggests what the correct answer might be. In particular, Ragib's "up to constant factor" (in the last comment) is wrong. The factor depends on the end-points of the integration range, so it depends on $n$. – 2012-05-25
-
0@Chris See my latest edit. – 2012-05-25
-
0Thank you for that, Ragib! I changed my downvote to an upvote. – 2012-05-25
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 } } \\ $$