Proof of Jensen's Inequality for Finite Convex Combinations

Sums of real numbers are the finite sums of the field $\mathbb{R}$, and $0\,t=0$ for every $t\in\mathbb{R}$, since $0\,t=(0+0)\,t=0\,t+0\,t$ by distributivity and claim 2 of Additive Cancellation and Elementary Additive Identities in a Field applies. As in Small Cases, Reduction, and Membership for Convex Combinations, $N+1$ denotes the successor of $N$, so claim 1 of Properties of Finite Sums may be used in the form $\sum_{k=1}^{N+1}a_k=\sum_{k=1}^{N}a_k+a_{N+1}$.

We use the induction principle for the natural numbers. Let $\mathcal{P}$ be the set of natural numbers $N$ with $1\le N$ such that the asserted inequality holds for every convex $C\subseteq\mathbb{R}^n$, every $f:C\to\mathbb{R}$ that is convex on $C$, every $x:[N]\to\mathbb{R}^n$ taking all of its values in $C$, and every system of convex weights $t$ of length $N$.

Base. Let $N=1$. By claim 1 of Small Cases, Reduction, and Membership for Convex Combinations, $t_1=1$ and $\sum_{k=1}^{1}t_kx_k=x_1$, so the left-hand side is $f(x_1)$; and claim 1 of Properties of Finite Sums gives $\sum_{k=1}^{1}t_kf(x_k)=t_1f(x_1)=f(x_1)$. The two sides are equal, so the inequality holds by reflexivity of the total order $\le$. Hence $1\in\mathcal{P}$.

Step. Suppose $N\in\mathcal{P}$, and let $C$, $f$, a map $x:[N+1]\to\mathbb{R}^n$ with values in $C$, and a system $t$ of convex weights of length $N+1$ be given. Adopt the notation $t'$, $x'$, $s$, $\tau$ and $y$ of claim 2 of Small Cases, Reduction, and Membership for Convex Combinations.

Suppose first that $t_{N+1}=1$. By claim 2 of Small Cases, Reduction, and Membership for Convex Combinations we have $s=1-t_{N+1}=0$, and since $\sum_{k=1}^{N}t'_k=s=0$ with $0\le t'_k$ for every $k\in[N]$, claim 5 of Properties of Finite Sums gives $t'_k=0$ for every $k\in[N]$. Claim 2(a) of Small Cases, Reduction, and Membership for Convex Combinations gives $\sum_{k=1}^{N+1}t_kx_k=x_{N+1}$, so the left-hand side is $f(x_{N+1})$. On the right, claim 1 of Properties of Finite Sums gives

$$\sum_{k=1}^{N+1}t_kf(x_k)=\sum_{k=1}^{N}t'_kf(x'_k)+t_{N+1}f(x_{N+1}),$$

and every summand of the first sum equals $0\,f(x'_k)=0$, so that sum is $0$ by claim 7 of Properties of Finite Sums. Both sides therefore equal $f(x_{N+1})$ and the inequality holds.

Suppose now that $t_{N+1}\ne1$. By claim 2(b) of Small Cases, Reduction, and Membership for Convex Combinations, $\tau$ is a system of convex weights of length $N$, $s\,\tau_k=t'_k$ for every $k\in[N]$, $0\le s$, $s\le1$, and

$$\sum_{k=1}^{N+1}t_kx_k=s\,y+(1-s)\,x_{N+1},\qquad y=\sum_{k=1}^{N}\tau_kx'_k .$$

The restriction $x'$ takes all of its values in $C$, so $y\in C$ by claim 3 of Small Cases, Reduction, and Membership for Convex Combinations, and $x_{N+1}\in C$. Since $f$ is convex on $C$,

$$f\Bigl(\sum_{k=1}^{N+1}t_kx_k\Bigr)\le s\,f(y)+(1-s)\,f(x_{N+1}).$$

By the induction hypothesis applied to $C$, $f$, $x'$ and $\tau$, we have $f(y)\le\sum_{k=1}^{N}\tau_kf(x'_k)$. Multiplying by the nonnegative $s$ using claim 5 of Elementary Arithmetic in an Ordered Field, and then using claim 3 of Properties of Finite Sums together with $s\,\tau_k=t'_k$,

$$s\,f(y)\le s\sum_{k=1}^{N}\tau_kf(x'_k)=\sum_{k=1}^{N}t'_kf(x'_k).$$

Adding $(1-s)f(x_{N+1})$ to both sides by claims 2 and 3 of Elementary Arithmetic in an Ordered Field, and using $1-s=t_{N+1}$ together with claim 1 of Properties of Finite Sums,

$$s\,f(y)+(1-s)\,f(x_{N+1})\le\sum_{k=1}^{N}t'_kf(x'_k)+t_{N+1}f(x_{N+1})=\sum_{k=1}^{N+1}t_kf(x_k).$$

Transitivity of $\le$ combines this with the convexity inequality above and gives the asserted bound. Hence $N+1\in\mathcal{P}$, and by induction $\mathcal{P}$ contains every natural number $N$ with $1\le N$.