Is $(n-1)+\max\limits_{1\leqslant i\leqslant n} x_i\geqslant \left(1-\left(1-\frac{1}{n}\right)^n\right)\sum\limits_{i=1}^{n}x_i$?

Let $n>0$ and $x_i>0$ for all $i\in \{1,\ldots,n\}$ be integer numbers.

I would like to compare $$(n-1)+\max\limits_{1\leqslant i\leqslant n} x_i,$$ and $$\left(1-\left(1-\frac{1}{n}\right)^n\right)\sum\limits_{i=1}^{n}x_i.$$

I think, after trying some examples, that

$$(n-1)+\max\limits_{1\leqslant i\leqslant n} x_i\leqslant \left(1-\left(1-\frac{1}{n}\right)^n\right)\sum\limits_{i=1}^{n}x_i,$$ but I can't prove this. I can't show the opposite also as I was unable to come up with a counterexample.

• The title and question have the inequalities in opposite directions. – carmichael561 May 11 '16 at 23:17
• I doubt that the inequality is true in either direction. Given that $1-(1-1/n)^n \to 1 - e^{-1} < 1$, constructing counter-examples is not too hard. – zuggg May 11 '16 at 23:21

For $n = 1$, both quantities are exactly equal to $x_1$.

Now suppose $n \ge 2$.

If $x_i = 1$ for all $i \in \{1,\ldots,n\}$, then we have:

$$(n-1)+\displaystyle\max_{1 \le i \le n}x_i = (n-1)+1 = n$$

$$\left(1-(1-\tfrac{1}{n})^n\right)\displaystyle\sum_{i = 1}^{n}x_i = \left(1-(1-\tfrac{1}{n})^n\right)n < n$$

So in this case, $(n-1)+\displaystyle\max_{1 \le i \le n}x_i > \left(1-(1-\tfrac{1}{n})^n\right)\displaystyle\sum_{i = 1}^{n}x_i$.

On the other hand, if $x_i = 4$ for all $i \in \{1,\ldots,n\}$, then we have:

$$(n-1)+\displaystyle\max_{1 \le i \le n}x_i = (n-1)+4 = n+3 \le \dfrac{5}{2}n$$

$$\left(1-(1-\tfrac{1}{n})^n\right)\displaystyle\sum_{i = 1}^{n}x_i = \left(1-(1-\tfrac{1}{n})^n\right) \cdot 4n > 4\left(1-\tfrac{1}{e}\right)n > \dfrac{5}{2}n$$

So in this case, $(n-1)+\displaystyle\max_{1 \le i \le n}x_i < \left(1-(1-\tfrac{1}{n})^n\right)\displaystyle\sum_{i = 1}^{n}x_i$.

Therefore, no comparison can be made if $n \ge 2$.

• Can we compare them if we add that $\sum_{i=1}^{n}x_i\geqslant n$ ? – Jarbou May 12 '16 at 1:28
• Both of my above examples satisfied that condition. So adding that condition won't help. – JimmyK4542 May 14 '16 at 22:25