proof of criterion for convexity

Theorem 1.

Suppose $f\colon(a,b)\to\mathbb{R}$ is continuous and that, for all $x,y\in(a,b)$,

 $f\left({x+y\over 2}\right)\leq{f(x)+f(y)\over 2}.$

Then $f$ is convex.

Proof.

We begin by showing that, for any natural numbers $n$ and $m\leq 2^{n}$,

 $f\left({mx+(2^{n}-m)y\over 2^{n}}\right)\leq{mf(x)+(2^{n}-m)f(y)\over 2^{n}}$

by induction. When $n=1$, there are three possibilities: $m=1$, $m=0$, and $m=2$. The first possibility is a hypothesis of the theorem being proven and the other two possibilities are trivial.

Assume that

 $f\left({m^{\prime}x+(2^{n}-m^{\prime})y\over 2^{n}}\right)\leq{m^{\prime}f(x)+% (2^{n}-m^{\prime})f(y)\over 2^{n}}$

for some $n$ and all $m^{\prime}\leq 2^{n}$. Let $m$ be a number less than or equal to $2^{n+1}$. Then either $m\leq 2^{n}$ or $2^{n+1}-m\leq 2^{n}$. In the former case we have

 $\displaystyle f\left({1\over 2}{mx+(2^{n}-m)y\over 2^{n}}+{y\over 2}\right)$ $\displaystyle\leq{1\over 2}\left(f\left({mx+(2^{n}-m)y\over 2^{n}}\right)+f(y)\right)$ $\displaystyle\leq{1\over 2}{mf(x)+(2^{n}-m)f(y)\over 2^{n}}+{f(y)\over 2}$ $\displaystyle={mf(x)+(2^{n+1}-m)f(y)\over 2^{n+1}}.$

In the other case, we can reverse the roles of $x$ and $y$.

Now, every real number $s$ has a binary expansion; in other words, there exists a sequence $\{m_{n}\}$ of integers such that $\lim_{n\to\infty}m_{n}/2^{n}=s$. If $0\leq s\leq 1$, then we also have $0\leq m_{n}\leq 2^{n}$ so, by what we proved above,

 $f\left({m_{n}x+(2^{n}-m_{n})y\over 2^{n}}\right)\leq{m_{n}f(x)+(2^{n}-m_{n})f(% y)\over 2^{n}}.$

Since $f$ is assumed to be continuous, we may take the limit of both sides and conclude

 $f(sx+(1-s)y)\leq sf(x)+(1-s)f(y),$

which implies that $f$ is convex. ∎

Title proof of criterion for convexity ProofOfCriterionForConvexity 2013-03-22 17:00:23 2013-03-22 17:00:23 rspuzio (6075) rspuzio (6075) 5 rspuzio (6075) Proof msc 52A41 msc 26A51 msc 26B25