# Proving that $\lim\limits_{n\to\infty}n\left( \int_0^1 f(t)\, dt -\frac1n\sum_{k=0}^{n-1}f\left(\frac k n\right) \right)=\frac{f(1)-f(0)}{2}$

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?

-
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
Please avoid using \displaystyle in the title. – Asaf Karagila Aug 12 '12 at 21:04
@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

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])$

-
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 – Norbert 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}

-

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,

-
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.

-
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