6
$\begingroup$

Evaluate $\lim\limits_{n\to\infty} \dfrac{1^{99} + 2^{99} + \cdots + n^{99}}{n^{100}}$

This is the question I remembered from my high school textbook (I remembered it while reading about something related). Now I know how to do it using Faulhaber's formula (at least the first coefficient, which is required). But the textbook used this method which I didn't and don't understand. $$\lim\limits_{n\to\infty} \dfrac{1^{99} + 2^{99} + \cdots + n^{99}}{n^{100}} = \lim\limits_{n\to\infty}\dfrac{\large\int\limits_{0}^n x^{99} dx}{n^{100}} = \lim\limits_{n \to \infty}\dfrac{\dfrac{n^{100}}{100}}{n^{100}}= \dfrac{1}{100}$$

What I don't understand how is converting from sum to integral is justified (the textbook didn't justify) and when is it allowed to replace sum by integral?

$\endgroup$
  • $\begingroup$ See math.stackexchange.com/questions/478344/… and also other posts shown there among linked questions. $\endgroup$ – Martin Sleziak Sep 28 '14 at 10:17
  • 1
    $\begingroup$ @MartinSleziak As I mentioned, I knew what answer is, and I know one method of arriving at the answer. I was specific in asking about a specific method of working the example. $\endgroup$ – taninamdar Sep 28 '14 at 10:20
5
$\begingroup$

Since for $x\in(k,k+1)$ we have $$k^{99} \le x^{99} \le (k+1)^{99}$$ we get $$k^{99} = \int_k^{k+1} k^{99} \,\mathrm{d}x \le \int_k^{k+1} x^{99}\,\mathrm{d}x \le \int_k^{k+1} (k+1)^{99} \,\mathrm{d}x = (k+1)^{99}.$$ This yields $$\sum_{k=0}^{n-1} k^{99} \le \int_0^{n} x^{99}\,\mathrm{d}x \le \sum_{k=0}^{n-1} (k+1)^{99}\\ 1^{99}+2^{99}+\dots+(n-1)^{99} \le \int_0^{n} x^{99}\,\mathrm{d}x \le 1^{99}+2^{99}+\dots+{n}^{99}.$$ Dividing by $n^{100}$ we get $$\frac{1^{99}+2^{99}+\dots+(n-1)^{99}}{n^{100}} \le \frac{\int_0^{n} x^{99}\,\mathrm{d}x}{n^{100}} \le \frac{1^{99}+2^{99}+\dots+{n}^{99}}{n^{100}}.$$

Since $$\left(\frac{1^{99}+2^{99}+\dots+{n}^{99}}{n^{100}}-\frac{1^{99}+2^{99}+\dots+(n-1)^{99}}{{n}^{100}}\right) = \frac1n \to 0$$ we get that all three expression above have the same limit for $n\to\infty$. (Provided that the limit exists at least for one of them.)


What we did above is basically comparing integral (area under the curve) with a sum (area given by the steps in the following image):

enter image description here

I have taken this picture from this answer.

Basically the same derivation is given in this answer

$\endgroup$
  • $\begingroup$ It should be obvious from algebra, but I can't somehow understand the transition from first to second step. How is $x^{99}$ converted to integral, and why does the inequality still hold? $\endgroup$ – taninamdar Sep 28 '14 at 10:56
  • $\begingroup$ @taninamdar We use the fact that $k^{99} = \int_k^{k+1} k^{99} \,\mathrm{d}x$, i.e., we can understand a constant as integral of the constant function over interval of unit length. (I.e., for any real number $C$ we have $C= \int_k^{k+1} k^{99} C\,\mathrm{d}x$. In this case we used it for the constant $C=k^{99}$.) I have also added the equality $k^{99} = \int_k^{k+1} k^{99} \,\mathrm{d}x$ to my answer. $\endgroup$ – Martin Sleziak Sep 28 '14 at 11:00
  • $\begingroup$ Aha, this answer makes more sense than the rest of the answers. Am I allowed to change my accepted answer? $\endgroup$ – taninamdar Sep 28 '14 at 11:04
  • $\begingroup$ Relevant threads on meta: Is it rude to change which answer you accept? and Length of time to wait before accepting an answer. My personal opinion is that there is no need to hurry too much with accepting an answer. $\endgroup$ – Martin Sleziak Sep 28 '14 at 11:06
  • $\begingroup$ Thanks, I'll keep that in mind from next time onwards. $\endgroup$ – taninamdar Sep 28 '14 at 11:07
14
$\begingroup$

$$\displaystyle \lim_{n\to \infty}\sum^{n}_{k=1}\big(\frac{k}{n}\big)^{99}\cdot\frac{1}{n}=\int^1_0x^{99}dx\,=\frac{1}{100}$$

$\endgroup$
  • $\begingroup$ How does one go from sum to integral? Also how did you get the limits of integral? $\endgroup$ – taninamdar Sep 27 '14 at 19:15
  • 2
    $\begingroup$ The integral is defined to be the limit of its Riemann sums. While there are many choices for Riemann sums, one of the simplest is $n$ equal-width intervals and taking the right-hand value of the integrand on each interval. That is precisely the equality here. Yes, it took some cleverness to see that the sum is a Riemann sum for this integral! But once it's written down, you should be able to verify that it's true. $\endgroup$ – Greg Martin Sep 27 '14 at 20:05
  • 1
    $\begingroup$ This is clever, but I'm accepting the other answer because it relates the sum to $\int\limits_{0}^{n}x^{99}dx$. Learned about Riemann sums from this, though. :) $\endgroup$ – taninamdar Sep 28 '14 at 8:41
4
$\begingroup$

See Euler-Maclaurin formula. In this case it looks like $$\sum\limits_{k=0}^nk^{99}=\int\limits_0^nx^{99}dx+\sum\limits_{i=1}^{\infty}\frac{B_i99!}{i!(100-i)!}n^{100-i}$$ Second summand is actually a polynomial of degree $99$, so it is $o(n^{100})$ and $$\lim\frac{\sum\limits_{k=0}^nk^{99}}{n^{100}}=\lim\frac{\int\limits_0^nx^{99}dx}{n^{100}}$$

$\endgroup$
  • $\begingroup$ >This is the question I remembered from my high school textbook >See Euler-Maclaurin formula $\endgroup$ – Pedro Tamaroff Sep 27 '14 at 19:36
  • $\begingroup$ In my opinion, it isn't a very complicated result, to understand it you just need to know what define integral and Bernoulli numbers are(I studied it in the first year of university). $\endgroup$ – user165101 Sep 27 '14 at 19:40
  • $\begingroup$ I see, this kind of makes sense! (at least it involves the integral in question). Though where is the error term in your answer that is mentioned in the Euler-Maclaurin formula page? I understand it would be small ($o(n)$), but can you explain the steps? Thanks! $\endgroup$ – taninamdar Sep 28 '14 at 6:00
  • $\begingroup$ In the article formula is stated in the form $\sum=\int+\sum\limits_{i=1}^m+R_m$. As $j$ tends to infinity, $R_j$ tends to $0$ and we obtain formula in the answer. $\endgroup$ – user165101 Sep 28 '14 at 6:28
2
$\begingroup$

In general $$ \frac{1^a+2^a+\cdots+n^a}{n^{a+1}}\to\frac{1}{a+1}, $$ for every $a>-1$, as $$ \frac{1^a+2^a+\cdots+n^a}{n^{a+1}}=\frac{1}{n}\sum_{k=1}^n\left(\frac{k}{n}\right)^a\to\int_0^1x^a\,dx=\frac{1}{a+1}, $$ To make it easier to understand $$ \frac{1}{n}\left(\frac{k}{n}\right)^a-\int_{\frac{k-1}{n}}^{\frac{k}{n}}x^a\,dx=\int_{\frac{k-1}{n}}^{\frac{k}{n}} \left(\left(\frac{k}{n}\right)^a-x^a\right)\,dx. $$ But, using Mean Value Theorem $$ \left(\frac{k}{n}\right)^a-x^a=\left(\frac{k}{n}-x\right)a\xi^{a-1}, $$ for some $\xi\in(\frac{k-1}{n},\frac{k}{n})$, and thus $$ 0\le \left(\frac{k}{n}\right)^a-x^a\le a\frac{1}{n}\left(\frac{k}{n}\right)^{a-1}, $$ and $$ 0\le\int_{\frac{k-1}{n}}^{\frac{k}{n}} \left(\left(\frac{k}{n}\right)^a-x^a\right)\,dx\le a\frac{1}{n^2}\left(\frac{k}{n}\right)^{a-1}\le \frac{a}{n^2}, $$ and finally $$ 0\le \frac{1}{n}\sum_{k=1}^n\left(\frac{k}{n}\right)^a-\int_0^1x^a\,dx\le \frac{a}{n}\to 0. $$

$\endgroup$
  • $\begingroup$ I understand that answer will be $\dfrac{1}{a+1}$ by Fallhaber's formula. What I want to know is whether and how is the method used by textbook justified. $\endgroup$ – taninamdar Sep 27 '14 at 19:20
  • $\begingroup$ See my explanation. $\endgroup$ – Yiorgos S. Smyrlis Sep 27 '14 at 19:32
2
$\begingroup$

Replacing a sum with an integral can be justified, but you actually need to justify it. It looks like your textbook didn't. For example, if the function involved something like $\sin kπ$ or $\cos 2kπ$ then for integer values of k you always get a result of 0 or 1, but for real values of k the result can be all over the place, and replacing a sum with an integral would be absolutely not justified.

If you take the constant number $k^{99}$, and compare it with the integral of $x^{99}$ taken from k-1 to k, then you are integrating over values that are all less than $k^{99}$, so the integral is less. If you compare with the integral of $x^{99}$ taken from k to k+1, you are integrating over values that are all greater than $k^{99}$, so the integral is greater.

Now you are calculating the sum of $k^{99}$ for k from 1 to n. We compared each of these n numbers with an integral, so you can also compare the sum with an integral: The whole sum is larger than the integral of $x^{99}$ from 0 to n, and less than the integral from 1 to n+1. That argument would work for any function that is increasing: If a function is increasing for real x, then the sum from 1 to n is between the integral from 0 to n-1 and the integral from 1 to n.

In this case, we can calculate the integrals and find that the sum is between $n^{100}/100$ and $((n+1)^{100} - 1)/100$ which is enough to prove the limit. Your textbook just took the limit for the integral from 0 to n. That's not enough; if you had a function where taking the limit from 1 to n+1 would give a different result, it would be wrong. So that's another thing that can be justified, but must actually be justified.

$\endgroup$
1
$\begingroup$

I would start by observing that $k^m = m!{k\choose m} + P(k)$, where $P$ is a polynomial of degree $<m$.

We will show, by induction, that $\sum_{k=1}^n k^m$ is a polynomial in $n$ with highest degree term $\frac{1}{m+1}n^{m+1}$. This is clear for $m=0$.

We have $\sum_{k=1}^n P(k)$ is a polynomial in $n$ of degree $<m+1$, by the inductive hypothesis. Also $\sum_{k=1}^n m!{k\choose m} = m!{{n+1}\choose{m+1}}$, which has highest degree term $\frac{1}{m+1}n^{m+1}$—and we're done.

To compute the limit, we can now write: $$\lim_{n\to\infty}\frac{\sum_{k=1}^n k^{99}} {n^{100}} = \lim_{n\to\infty}\frac{\frac{1}{100}n^{100} + \cdots} {n^{100}} = \frac{1}{100}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.