Post Undeleted by Ravi Boppana
show/hide this revision's text 2 Completed the argument.

Here is

Since the single-variable optimization that David mentions still requires some work, I will present another approachsolution. Let $f(p) = p(1-p)^t$. Define a the function $g$ that is equal to $f$ on $[0, 1/t]$, and on $[1/t, 1]$ is a linear interpolation between the points $(1/t, f(1/t))$ and $(1, 0)$. Then we can check that $g$ is concave on all of $[0, 1]$ and $g \ge f$ on all of $[0, 1]$. So now we can apply Jensen's inequality to $g$ and we're done.(I learned this method concept of "concave majorants" (or "convex minorants) " from Steele's book called The Cauchy-Schwarz Master Class.) Applying Jensen's inequality, we have $\sum f(p_i) \le \sum g(p_i) \le n g(1/n)$.

We now split into two cases, $t \le n -1$ or $t \ge n$. First, suppose that $t \le n - 1$. Then $g(1/n) = f(1/n) = (1/n) (1 - 1/n)^t$. So we need to show that $(1 - 1/n)^t$ is at most $n (1 - 1/n)^n / t$. That's equivalent to showing $t(1 - 1/n)^t \le n (1 - 1/n)^n$. We can check that the left side is an increasing function of $t$ for $t \le n - 1$, and when $t = n - 1$ we have an equality. So we have established the inequality in this case.

Next suppose that $t \ge n$. Then by linear interpolation, we find $g(1/n) = (1 - 1/t)^{t-1} (1 - 1/n) / t$. So we need to show that $(1 - 1/t)^{t - 1} (n - 1) \le n(1 - 1/n)^n$. That's equivalent to $(1 - 1/t)^{t-1} \le (1 - 1/n)^{n - 1}$. By taking reciprocals, that's equivalent to $(1 + 1/(t - 1))^{t - 1} \ge (1 + 1/(n-1))^{n - 1}$. The left side is an increasing function of $t$, and we have an equality when $t = n$. So we have established the inequality in the second case too.

    Post Deleted by Ravi Boppana
show/hide this revision's text 1