Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $f\in C^2([0,1])$. Prove that $$ \lim_{n\to+\infty}n\left( \int_0^1 f(t)\, dt -\frac1n\sum_{k=0}^{n-1}f\Big(\frac k n\Big) \right)=\frac{f(1)-f(0)}{2}. $$

The second term is clearly the Riemann sum of the function $f$; since the function $f$ is integrable (it is continuous) $\displaystyle \frac1n\sum_{k=0}^{n-1}f\Big(\frac k n\Big)$ converges to $\displaystyle\int_0^1 f(t)\, dt$ when $n \to + \infty$.

So we have an indeterminate form, "$\infty \cdot 0$". How can we start? I thought we should use Taylor expansion ($f$ is $C^2$) but I cannot see how. Would you please help me?

Thanks in advance.

share|improve this question
1  
Note that taking the right-hand side into the second term on the left yields the trapezoidal rule, whose error is of third order. –  joriki Aug 12 '12 at 20:37
    
Euler-Maclaurin formula (en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula) –  user17762 Aug 12 '12 at 20:45
1  
Please avoid using \displaystyle in the title. –  Asaf Karagila Aug 12 '12 at 21:04
2  
@did posted an excellent proof of this here. Also, this was the main step in one of the American Math Monthly problems sometime in the last 6 months, there is another derivation there (though I'm not sure how different it is to one I linked to). –  Ragib Zaman Aug 12 '12 at 21:05

4 Answers 4

up vote 3 down vote accepted

One can check by integrating by parts that $$ f\left(\frac{k}{n}\right)-n\int\limits_{(k-1)/n}^{k/n}f(t)dt= n\int\limits_{(k-1)/n}^{k/n}f'(t)\left(t-\frac{k-1}{n}\right)dt= \int\limits_{0}^1\frac{t}{n}f'\left(\frac{t+k-1}{n}\right) $$ So using dominated convergence theorem we get $$ \lim\limits_{n\to+\infty}n\left(\int_0^1f(t)dt -\frac{1}{n}\sum_{k=0}^{n-1}f\left(\frac k n\right) \right)= \lim\limits_{n\to+\infty}\int\limits_{0}^1\frac{t}{n}\sum_{k=0}^{n-1}f'\left(\frac{t+k-1}{n}\right)= $$ $$ \int\limits_{0}^1t\lim\limits_{n\to+\infty}\frac{1}{n}\sum_{k=0}^{n-1}f'\left(\frac{t+k-1}{n}\right)= \int_{0}^{1}t\left(\int\limits_{0}^1 f'(s)ds\right)dt=\frac{f(1)-f(0)}{2} $$ Note that for this proof it is enough to require that $f\in C^1([0,1])$

share|improve this answer
    
Thanks for your proof, Norbert. If I can, I would ask you one little explanation: would you explain how you used dominated convergence theorem, please? Are the hypotesis satisfied? Thanks a lot. –  Romeo Aug 13 '12 at 7:30
    
@Romeo Let $M=\max\limits_{x\in[0,1]}|f'(x)|$ then for all $t\in[0,1]$ $$\left|\frac{t}{n}\sum\limits_{k=0}^{n-1}f'\left(\frac{t+k-1}{n}\right)\right| \leq t M$$ The function in the right hand side have a finite integral, so we can apply dominated convergence theorem –  no identity Aug 13 '12 at 7:39
    
Yes, I've understood. Thanks for your kind explanations. –  Romeo Aug 13 '12 at 9:42

Using the Taylor series for $f$, we get $$ \begin{align} &n\left(\int_0^1f(t)\,\mathrm{d}t-\frac1n\sum_{k=0}^{n-1}f(k/n)\right)\\ &=n\sum_{k=0}^{n-1}\int_{k/n}^{(k+1)/n}\left(f(t)-f(k/n)\right)\,\mathrm{d}t\\ &=n\sum_{k=0}^{n-1}\int_{k/n}^{(k+1)/n}\left(f'(k/n)(t-k/n)+O(1/n^2)\right)\,\mathrm{d}x\\ &=n\sum_{k=0}^{n-1}\left(f'(k/n)\frac1{2n^2}+O(1/n^3)\right)\\ &=\frac12\sum_{k=0}^{n-1}f'(k/n)\frac1n+O(1/n)\tag{1} \end{align} $$ Where the $O(1/n)$ term has constant bounded by the maximum of $\frac12|f''(t)|$ on $[0,1]$.

Since the sum in $(1)$ is the Riemann Sum for $\frac12\int_0^1f'(t)\,\mathrm{d}t$, we have $$ \begin{align} \lim_{n\to\infty}n\left(\int_0^1f(t)\,\mathrm{d}t-\frac1n\sum_{k=0}^{n-1}f(k/n)\right) &=\lim_{n\to\infty}\left(\frac12\sum_{k=0}^{n-1}f'(k/n)\frac1n+O(1/n)\right)\\ &=\frac12\int_0^1f'(t)\,\mathrm{d}t+0\\ &=\frac{f(1)-f(0)}{2}\tag{2} \end{align} $$

share|improve this answer

I don't know how to do it formally, but I've got the main idea ; using the fact that you can approximate an integral using the trapezes approximation method (the approximation becomes exact at the limit), your limit expression is $$ \sum_{k=0}^{n-1} \left( \int_{k/n}^{(k+1)/n} f(t) \, dt - \frac{f(k/n)}n \right) \sim \sum_{k=0}^{n-1} \left( \left( \frac{f((k+1)/n) + f(k/n)}{2n} \right) - \frac{f(k/n)}n \right) = \frac{f(1) - f(0)}{2n}. $$ If you want to prove anything you'll have to think about the trapezes method to approximate an integral since your limit is essentially telling you that if you take $n$ trapezes and choose $n$ large enough, your formula is off by the term $(f(1) - f(0)) / 2$. Recall the formula for the trapezes method : $$ \int_0^1 f(t) \, dt \sim \frac{f(0)/2 + \sum_{k=1}^{n-1} f(k/n) + f(1)/2}{n}. $$ Hope that helps,

share|improve this answer
    
To formalise this, use the integral mean value theorem on each of the subintervals $[\frac{k-1}{n}, \frac{k}{n}]$. –  Kris Aug 13 '12 at 0:27
    
@Kris : The problem with the mean value theorem is that the sum will not have lots of cancellations the same way it doesn when I don't use the mean value theorem, and that's why I'm stuck on formalizing. –  Patrick Da Silva Aug 13 '12 at 2:24

By Stone-Weierstrass theorem, we can find a sequence of polynomials $\{P_k\}$ such that $P'_k$ converge uniformly on $[0,1]$ to $f'$ and $P_k$ to $f$. We have, denoting $g_k(t):=f(t)-P_k(t)$,
\begin{align}\left|n\left(\int_0^1g_k(t)dt-\sum_{j=0}^{n-1}g_k(j/n)\right)\right|&\leq n\sum_{j=0}^{n-1}\left|\int_{j/n}^{\frac{j+1}n}(g_k(t)-g_k(j/n))dt\right|\\ &\leq n\sum_{j=0}^{n-1}\lVert g'_k\rVert_{\infty}\int_{\frac jn}^{\frac{j+1}n}\left(t-\frac jn\right)dt\\ &=n\lVert g'_k\rVert_{\infty}\sum_{j=0}^{n-1}\int_0^{\frac 1n}sds\\ &=\frac{\lVert g'_k\rVert_{\infty}}2, \end{align} hence we just have to show the result when $f$ is a polynomial. By linearity, it's enough to deal with the case $f(t)=t^p$, $p\in\Bbb N$, and this is given by Faulhaber's formula. Indeed, we have to see that $$\lim_{n\to +\infty}n\left(\frac 1{p+1}-\frac 1n\sum_{j=0}^n\left(\frac jn\right)^p\right)=-\frac 12.$$ We have $$n\left(\frac 1{p+1}-\frac 1n\sum_{j=0}^n\left(\frac jn\right)^p\right)= n\left(\frac 1{p+1}-\frac 1{p+1}\frac 1{n^{p+1}}\sum_{j=0}^p(-1)^j\binom{p+1}jB_jn^{p+1-j}\right)\\ =\frac n{p+1}(p+1)B_1/n+\frac 1{p+1}\sum_{j=2}^p\binom{p+1}j(-1)^jB_jn^{-j+1},$$ and using $B_1=-1/2$ we have the result.

share|improve this answer
1  
I think you should explain a little further how it follows from Faulhaber's formula ; I followed the link and got a little lost as to why is this relevant (i.e. I didn't manage to fill in the blanks). But very original answer though. +1 –  Patrick Da Silva Aug 13 '12 at 2:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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