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.

  • $\begingroup$ The title and question have the inequalities in opposite directions. $\endgroup$ – carmichael561 May 11 '16 at 23:17
  • 3
    $\begingroup$ 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. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.