Jensen's Inequality

Jensen's inequality is an inequality involving convexity of a function. We first make the following definitions:

• A function is convex on an interval $I$ if the segment between any two points taken on its graph $($in $I)$ lies above the graph. An example of a convex function is $f(x)=x^2$.

• A function is concave on an interval $I$ if the segment between any two points on the graph $($in $I)$ lies below the graph. An example of a concave function is $f(x)=-x^2$.

Now, Jensen's inequality is the following:

Jensen's Inequality

Let a real-valued function $f$ be convex on the interval $I$. Let $x_1,...,x_n\in I$ and $\omega_1,...,\omega_n\ge 0$. Then we have

$$\dfrac{\omega_1 f\left(x_1\right)+\omega_2 f\left(x_2\right)+\cdots+\omega_n f\left(x_n\right)}{\omega_1+\omega_2+\cdots+\omega_n} \ge f\left(\dfrac{\omega_1x_1+\omega_2x_2+\cdots+\omega_nx_n}{\omega_1+\omega_2+\cdots+\omega_n}\right).$$

If $f$ is concave, the direction of inequality is flipped.

In particular if we take weights $\omega_1=\omega_2=\cdots=\omega_n=1$, we get the inequality

$$\dfrac{f\left(x_1\right)+f\left(x_2\right)+\cdots+f\left(x_n\right)}{n} \ge f\left(\dfrac{x_1+x_2+\cdots+x_n}{n}\right). \ _\square$$

This proof is a little long. As it doesn't help much in the problem-solving aspect, you may skip it.

Note that we need only to prove the statement for convex functions. This is due to the following result:

If $g$ is a concave function, then $-g$ is a convex function.

We first prove the following statement :

$P \iff Q,$ where $P$ and $Q$ are as follows:

$P$ : $\forall x_1,...,x_n\in I$ and $\forall \omega_1,...,\omega_n\ge 0$ the following holds :

$$\dfrac{\omega_1 f\left(x_1\right)+\omega_2 f\left(x_2\right)+\cdots+\omega_n f\left(x_n\right)}{\omega_1+\omega_2+\cdots+\omega_n} \ge f\left(\dfrac{\omega_1x_1+\omega_2x_2+\cdots+\omega_nx_n}{\omega_1+\omega_2+\cdots+\omega_n}\right).$$

$Q$ : $\forall x_1,...,x_n\in I$ and $\forall \lambda_1, \dots, \lambda_n \geq 0 \text{ and } \displaystyle \sum_{i=1}^n \lambda_i = 1$ the following holds :

$$\sum_{i=1}^n \lambda_i f(x_i) \geq f \left(\sum_{i=1}^n \lambda_i x_i \right).$$

Proof:

Simply put $\lambda_i = \dfrac{\omega_i}{\displaystyle \sum_{r=1}^n \omega_r},$ where $i = 1,2, \dots n.$

This means that we've reduced the problem to just showing that $Q$ is true. To do this, we use induction.

The base case $n = 1$ is trivially true.

The case $n = 2$ is the definition of a convex function (the proof of this is left to the interested reader).

For $n \geq 3$, we shall assume that $\lambda_n \in (0,1)$ $($if $\lambda_n = 1,$ the assertion trivially holds, and if $\lambda_n = 0,$ we appeal to the induction hypothesis).

Now, we proceed assuming that the cases $k = 2$ and $k = n-1$ are true :

$$\begin{aligned} f \left( \sum_{i = 1}^n \lambda_i x_i \right) &= f \left( (1-\lambda_n) \left(\sum_{i = 1}^{n-1} \mu_i x_i \right) + \lambda_n x_n \right)\qquad \left(\text{where }\ \mu_i = \frac{\lambda_i}{1-\lambda_n}, \ i = 1,2,\dots,n-1,\ \sum_{i=1}^{n-1} \mu_i = 1\right) \\ & \leq (1-\lambda_n)f \left(\sum_{i = 1}^{n-1} \mu_i x_i \right) + \lambda_n f(x_n)\\ & \leq \left( \sum_{i=1}^{n-1} (1-\lambda_n)\mu_i f(x_i) \right) + \lambda_n f(x_n)\\ & = \sum_{i = 1}^n \lambda_if(x_i). \end{aligned}$$

So, the proof is complete via induction. $_\square$

The last form is the form that is most frequently encountered and used in various Olympiad level problems.

How do we check if a function is convex or concave? We can't always plot the graph and check. The best (and often quicker) way is using calculus. A function $f$ is convex on the interval $I$ if and only if $f''(x) \geq 0$ for all $x\in I$ and concave if $f''(x) \leq 0$ for all $x\in I$. The precise statement is given below:

Let $f: I \to \mathbb{R}$ be a twice-differentiable function.

Then

• $f$ is convex on $I$ if and only if $f''(x) \geq 0 \ \forall x \in I;$
• $f$ is concave on $I$ if and only if $f''(x) \leq 0 \ \forall x \in I.$

The proof of this can be found here.

For example, for $f(x)=x^2$ we have $f'(x)=2x,$ so $f''(x)=2>0$ for all $x\in\mathbb{R}$. So the function is convex everywhere on the graph. Similarly for $f(x)=-x^2$ we have $f''(x)=-2<0$ for all $x\in\mathbb{R}$. So the function is concave everywhere on the graph.

Since we've been talking so much about $f(x)=x^2$, let's apply Jensen's on it. We've already shown that it's convex everywhere. We choose reals $x_1=1, x_2=2,...,x_n=n$. Applying Jensen's we get

$$\begin{aligned} \dfrac{f\left(x_1\right)+f\left(x_2\right)+\cdots+f\left(x_n\right)}{n} &\ge f\left(\dfrac{x_1+x_2+\cdots+x_n}{n}\right) \\ \dfrac{f\left(1\right)+f\left(2\right)+\cdots+f\left(n\right)}{n} &\ge f\left(\dfrac{1+2+\cdots+n}{n}\right) \\ \dfrac{1^2+2^2+\cdots+n^2}{n} &\ge f\left(\frac{\frac{n(n+1)}{2}}{n}\right) \\ \frac{\frac{n(n+1)(2n+1)}{6}}{n} &\ge f\left(\dfrac{n+1}{2}\right) \\ \dfrac{(n+1)(2n+1)}{6}&\ge \left(\dfrac{n+1}{2}\right)^2 \\ n &\ge 1 . \end{aligned}$$

AM-GM inequality (arithmetic mean-geometric mean inequality) is one of the special cases of Jensen's inequality:

$$\frac{\sum_{i=1}^n a_i}{n} \geq \sqrt[n]{\prod_{i=1}^n a_i}.$$

Consider the function $f(x) = \log x \ \forall x > 0.$

Observe that $f^{\prime\prime}(x) = \frac{-1}{x^2} < 0$. Then $f(x)$ turns out to be a concave function. $($Also notice that we can conclude $f(x)$ is concave using the graph of $\log x.)$ Thus, by Jensen's inequality we have

$$\begin{aligned} f\left(\frac{ \sum_{i=1}^n a_i}{n}\right) & \geq \frac{\sum_{i=1}^n f\left(a_i\right)}{n} \\ \Rightarrow \log \left(\frac{\sum_{i=1}^n a_i}{n}\right) & \geq \frac{\sum_{i=1}^n \log a_i }{n}. \end{aligned}$$

By the property of logarithms, $\log x + \log y = \log xy$ and $b\log a = \log a^b$. Therefore, we can simplify the terms on the RHS as

$$\begin{aligned} \log \left(\dfrac{\sum_{i=1}^n a_i}{n}\right) & \geq \dfrac{\sum_{i=1}^n \log a_i}{n} \\ & = \dfrac{\log a_1+\log a_2 + \cdots + \log a_n }{n} \\ & = \dfrac{\log \left(a_1 a_2 a_3 \cdots a_n\right)}{n} \\ & = \log \left(\prod_{i=1}^n a_i\right)^{\frac{1}{n}}. \end{aligned}$$

Taking antilogarithm, we get our desired result. $_\square$

Prove that for all $n\in\mathbb{N},$

$$$$ $$\sqrt{1^2+1}+\sqrt{2^2+1}+\cdots +\sqrt{n^2+1}\ge \dfrac{n}{2}\sqrt{n^2+2n+5}.$$

---

Notice that on the left side $($denoted $L)$ we have a sum of same terms with some different arguments, so we should think of applying Jensen's with the common form as a function. Define the function $f(x)=\sqrt{x^2+1}.$ We can find the second derivative, but that's not needed if we observe that for $x\to \infty$, we have $f(x)=\sqrt{x^2+1}\to |x|$. So the graph should look like that of $y=|x|$, V-shaped with a little curve at the bottom and thus convex.

Now we are ready to apply Jensen's with reals $x_1=1,x_2=2,...,x_n=n$. We get

$$\begin{aligned} \dfrac{f\left(x_1\right)+f\left(x_2\right)+\cdots+f\left(x_n\right)}{n} &\ge f\left(\dfrac{x_1+x_2+\cdots+x_n}{n}\right) \\ \dfrac{f\left(1\right)+f\left(2\right)+\cdots+f\left(n\right)}{n} &\ge f\left(\dfrac{1+2+\cdots+n}{n}\right) \\ \dfrac{\sqrt{1^2+1}+\sqrt{2^2+1}+\cdots+\sqrt{n^2+1}}{n} &\ge f\left(\dfrac{n(n+1)/2}{n}\right) \\ &= f\left(\dfrac{n+1}{2}\right) \\ &= \sqrt{\left(\dfrac{n+1}{2}\right)^2+1} \\ &= \dfrac{1}{2}\sqrt{n^2+2n+5}. \end{aligned}$$

Hence, $L\ge \dfrac{n}{2}\sqrt{n^2+2n+5},$ completing the proof. $_\square$

• Arithmetic Mean - Geometric Mean
• Wilson's Theorem