1. ## Riemann sum increasing

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

2. Originally Posted by Infophile
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}$.

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

4. Originally Posted by Infophile
It's the case no ?
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.

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

6. Merci Laurent ! (je n'avais pas vu que tu étais Français)

But I don't understand this equality $\displaystyle =\sum_{k=1}^{n}\left(1-\frac 1n\right)f\left(\frac{k}{n+1}\right)$, it seems false.

7. Originally Posted by Laurent
$\displaystyle \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)$.
Originally Posted by Infophile
Merci Laurent ! (je n'avais pas vu que tu étais Français)

But I don't understand this equality $\displaystyle =\sum_{k=1}^{n}\left(1-\frac 1n\right)f\left(\frac{k}{n+1}\right)$, it seems false.
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.

8. Yes I saw that each terms appears twice, but I think the coefficient in front of $\displaystyle f(\frac{k}{n+1})$ is rather $\displaystyle 1-\frac{k}{n}+\frac{k-1}{n+1}=\frac{n-k}{n+1}$.

Do you agree ?

9. Originally Posted by Infophile
Yes I saw that each terms appears twice, but I think the coefficient in front of $\displaystyle f(\frac{k}{n+1})$ is rather $\displaystyle 1-\frac{k}{n}+\frac{k-1}{n+1}=\frac{n-k}{n+1}$.

Do you agree ?
That's because I didn't copy the previous equation right: comparing with the previous convex combination, it had of course to be $\displaystyle \sum_{k=1}^{n-1} \left(\left(1-\frac kn\right)f\left(\frac{k}{n+1}\right)+\frac{k}{n}f\ left(\frac{k+1}{n+1}\right)\right)$.

10. Indeed, sorry !

Thanks !