I suspect this is a homework question somewhere, but I've not seen it elsewhere and it seems like it should be easy: let $f(x)$ be a concave function from $[0,1]$ to the reals such that $f(0) = f(1) = 0$. Consider the obvious upper bound for $\int\_0^1 f(x) dx$ obtained by dividing $[0,1]$ into $n$ sub-intervals of the same length and measuring the area of the rectangles whose heights are given by the maximum value of $f(x)$ along that sub-interval. What's the maximum relative error that this can introduce, as a function of $n$? (I'm guessing $2/n$?)



Approximation of an integral of a concave function
Since $f$ is concave, it is continuous in $(0,1)$. I will assume that it is continuous in $[0,1]$. The graph of $f$ is above the secants, so that $f(x)\ge 0$. Let $M$ be the maximum of $f$. If $M=0$ there is nothing to prove, so that we we may assume that $M > 0$ (and hence $f(x) > 0$ for $0 < x < 1$.) Assume by now that the maximum is achieved at a unique point $x\_M\in(0,1)$. Given $n\ge 1$, let $k$ be the smallest integer such that $x\_M\in(k/n,(k+1)/n)$ (the case $x\_M=k/n$ is treated similarly.) Let $A\_i=\int\_{x\_i}^{x\_{i+1}}f(x)dx$. Then, because of the concavity
$$
\frac{1}{2n}(f(\frac{i}{n})+f(\frac{i+1}{n}))\le A\_i \le \frac{1}{n}f(\frac{i+1}{n})
$$
for $0\le i < k$, so that
$$
0\le\sum\_{i=0}^{k-1}f(\frac{i+1}{n})-\int\_{0}^{x\_{k}}f(x)dx\le \frac{1}{2n}f(\frac{k}{n})\le\frac{M}{2n}.
$$
Similarly, we get
$$
0\le\sum\_{i=k+1}^{n-1}f(\frac{i}{n})-\int\_{x\_{k+1}}^{1}f(x)dx\le \frac{1}{2n}f(\frac{k+1}{n})\le\frac{M}{2n}.
$$
Finally, it is easily seen that
$$
0\le \frac{M}{n}-A\_k\le\frac{M}{2n}-\frac{1}{2}(f(\frac{k}{n})(x\_M-\frac{k}{n})+f(\frac{k+1}{n})(\frac{k+1}{n}-x\_M))\le \frac{M}{2}.
$$
Thus, the total error is at most $3M/2n$. On the other hand, $\int\_0^1f(x)dx$ is larger than the area of the triangle with vertices at $(0,0)$, $(1,0)$ and $(x\_M,M)$, which is $M/2$. Thus, the relative error is at most $3/n$.


Using the fact that $f(k/n)$ converges to $M$, you can probably get all the way down to $(2+\epsilon)/n$ for any $\epsilon>0$ provided $n$ is sufficiently large.


The case in which the maximum is achieved on an interval is treated in a similar way.


