Hi !
Let $\displaystyle f$ $\displaystyle C^0$ increasing.
How can I prove that the sequence defined by $\displaystyle u_n=\frac{1}{n}\sum_{k=0}^{n-1}f(\frac{k}{n})$ (Riemann sum) is increasing ?
Thanks
I think (I'm even almost sure) this is wrong. Are you sure this is what the exercise is asking? This could be true if the Riemann sum was defined with respect to a sequence of "increasing" subdivisions, i.e. such that the subdivision for $\displaystyle n+1$ is finer than that for $\displaystyle n$ ; for instance, at the points $\displaystyle \frac{1}{2^k}$.
It's the case no ? The step is 1/n for u_n and 1/(n+1) for u_(n+1) (finer subdivision than for u_n).
In my exercice I have f(x)=xexp(x), but I suppose this is true for all increasing function.
I verify with Maple for this f.
Finer means that the subdivision from one step to the next is obtained by subdividing it: we only add points in the subdivision.
Consider the following example: $\displaystyle f(x)=0$ if $\displaystyle 0<x<1/2$, $\displaystyle f(x)=1$ if $\displaystyle 1/2\leq x<1$ (yes, I know, it is not continuous). Then for $\displaystyle n=2$ the Riemann sum is $\displaystyle \frac{1}{2}$. And for $\displaystyle n=3$ it is $\displaystyle \frac{1}{3}$. To get a continuous example, just consider $\displaystyle f$ going quickly from 0 to 1 just before $\displaystyle 1/2$.
In your example, f is convex; this could help.
Sufficient conditions are $\displaystyle f(0)=0$ and $\displaystyle f$ is convex on $\displaystyle [0,1]$.
Proof sketch: for $\displaystyle 1\leq k< n$, we have $\displaystyle \frac{k}{n+1}< \frac{k}{n}< \frac{k+1}{n+1}$ and the convex combination $\displaystyle \frac{k}{n}=\left(1-\frac kn\right)\frac{k}{n+1}+\frac{k}{n}\frac{k+1}{n+1}$. Using convexity and value at 0, we get
$\displaystyle \sum_{k=0}^{n-1}f\left(\frac kn\right) \leq \sum_{k=1}^{n-1} \left(\left(1-\frac kn\right)f\left(\frac{k}{n+1}\right)+\frac{k}{n+1} f\left(\frac{k+1}{n+1}\right)\right)$ $\displaystyle =\sum_{k=1}^{n}\left(1-\frac 1n\right)f\left(\frac{k}{n+1}\right)$.
Furthermore, $\displaystyle \frac{1}{n}\left(1-\frac 1n\right)\leq \frac{1}{n+1}$, hence $\displaystyle \frac 1n\sum_{k=0}^{n-1}f\left(\frac kn\right) \leq\frac{1}{n+1}\sum_{k=0}^n f\left(\frac{k}{n+1}\right)$. QED.
Does it seem false because you don't understand it or for more sound reasons? If you look at the sum globally, each term $\displaystyle f\left(\frac{k}{n+1}\right)$ appears twice (once for index $\displaystyle k$ and once for index $\displaystyle k-1$), except for $\displaystyle f(0),f\left(\frac{n}{n+1}\right)$ which appear once. The coefficient in front of $\displaystyle f\left(\frac{k}{n+1}\right)$ is the sum of the two corresponding coefficients. I can't ensure my computation is correct but I let you check it.