proof of criterion for convexity

Theorem 1.

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

$$f\left(\frac{x+y}{2}\right)\le \frac{f(x)+f(y)}{2}.$$

Then $f$ is convex.

Proof.

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

$$f\left(\frac{mx+(2^n-m)y}{2^n}\right)\le \frac{mf(x)+(2^n-m)f(y)}{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(\frac{m^{\prime }x+(2^n-m^{\prime })y}{2^n}\right)\le \frac{m^{\prime }f(x)+(2^n-m^{\prime })f(y)}{2^n}$$

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

$f\left({\displaystyle \frac{1}{2}}{\displaystyle \frac{mx+(2^n-m)y}{2^n}}+{\displaystyle \frac{y}{2}}\right)$ $\le {\displaystyle \frac{1}{2}}\left(f\left({\displaystyle \frac{mx+(2^n-m)y}{2^n}}\right)+f(y)\right)$

$\le {\displaystyle \frac{1}{2}}{\displaystyle \frac{mf(x)+(2^n-m)f(y)}{2^n}}+{\displaystyle \frac{f(y)}{2}}$

$={\displaystyle \frac{mf(x)+(2^{n+1}-m)f(y)}{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 \mathrm{\infty }}{m}_n/2^n=s$. If $0\le s\le 1$, then we also have $0\le m_n\le 2^n$ so, by what we proved above,

$$f\left(\frac{m_{n}x+(2^n-m_n)y}{2^n}\right)\le \frac{m_{n}f(x)+(2^n-m_n)f(y)}{2^n}.$$

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

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

which implies that $f$ is convex. ∎

Title	proof of criterion for convexity
Canonical name	ProofOfCriterionForConvexity
Date of creation	2013-03-22 17:00:23
Last modified on	2013-03-22 17:00:23
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	5
Author	rspuzio (6075)
Entry type	Proof
Classification	msc 52A41
Classification	msc 26A51
Classification	msc 26B25