2
$\begingroup$

why does it follow from convexity that

$\sum^n_{i=1} 2^{k_i} \geq n2^{k/n}$, where $k_1 +...+k_n = k$

holds?

2 Answers 2

2

The function $x \rightarrow 2^x$ is convex. That means that if you draw a line between two points $(x,2^x)$ and $(y,2^y)$, then the line will be above the function. In particular, the midpoint $(2^x+2^y)/2$ is above $2^{(x+y)/2}$. More generally, for any $0 \leq p \leq 1$ we have $p 2^x + (1-p) 2^y \geq 2^{px + (1-p)y}$.

Using this inequality, you can prove inductively that given $n$ points $x_i$ and $n$ non-negative coefficients $p_i$ summing to $1$, we have $\sum p_i 2^{x_i} \geq 2^{\sum p_i x_i}.$ Now put $x_i = k_i$ and $p_i = 1/n$.

2

If the function $f(x)$ is convex then Jensen's inequality $f\left(\frac{\sum_i x_i}{n}\right) \leq \frac{\sum_i f(x_i)}{n}$ holds.

Use this with $f(x) =2^x$...