# Prove the bounds of Log-Sum-Exp function

Let $f(x) = \log \sum_i^n \exp x_i$, where $x \in \mathbb R^n$, I read that the following inequlities hold:

$$\max\{x_1, x_2, \ldots, x_n\} \le f(x) \le \max\{x_1, x_2, \ldots, x_n\} + \log n$$

, but I have no idea how to prove this conclusion.

I can see that the first inequality is tight when there's only one non-zero element in $x$, and the second inequality is tight when all of the elements of $x$ are equal, but I don't know how to prove that these two cases form the lower bound and upper bound or the function.

• When there's only one non-zero element $x_{i},$ don't you get $\log((n-1)+\exp(x_{1}))$? – RideTheWavelet Nov 15 '17 at 4:53
• @carmichael561 thanks! Edited. – hklel Nov 15 '17 at 5:23

For any positive real numbers $y_1,\dots,y_n$, we have $$\max\{y_1,\dots,y_n\}\leq y_1+\dots+y_n\leq n\max\{y_1,\dots,y_n\}$$ Taking $y_i=e^{x_i}$ and using the fact that the exponential function is increasing, we get $$\exp(\max\{x_1,\dots,x_n\})\leq \sum_{i=1}^ne^{x_i}\leq n\exp(\max\{x_1,\dots,x_n\})$$ and then taking logs yields $$\max\{x_1,\dots,x_n\}\leq \log\sum_{i=1}^ne^{x_i}\leq \max\{x_1,\dots,x_n\}+\log n$$