Showing an alternating sum is positive

Question

I am trying to prove the following for $n > 1$.

$$\sum_{k=0}^n (-1)^k \binom{n}{k} \max\{0,n-2k\}^{n-1} > 0.$$

From numerical computations, this seems to be true, but I am struggling to find a simple proof.

---

Attempt: I noticed that by an inclusion-exclusion argument, one can show that the following similar expression is exactly zero. $$\sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^{n-1} = 0.$$ Since the addends of the latter sum are larger in magnitude than those of the former sum, and both sums begin with the same term $n^{n-1}$, I was hoping this would help, but it seems this is not quite enough. (Take for example $5 - 10 + 5 = 0$ vs $5 - 8 + 2 = -1$.)

I tried to interpret the original sum as an inclusion-exclusion argument itself, but the $\max\{0, n-2k\}$ is difficult to interpret in a combinatorial situation.

---

As noted in the comments, I could rewrite the first sum as $$\sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n}{k} (n-2k)^{n-1},$$ but this does not help me too much in either of my above approaches.

---

The desired inequality would hold if the addends were decreasing in magnitude. But unfortunately this is not true either: see @saulspatz's answer below along with my comments there.

Answer 1

The following observation is proved in this answer:

Let $d > 0$ and $U_1, \cdots, U_{n-1}$ be i.i.d. random variables uniformly distributed on $[0, 1]$. Write

$$U_{(1)} \leq \cdots \leq U_{(n-1)}$$

for the rearrangement of $U_1, \cdots, U_{n-1}$ in increasing order together with the convention that $U_{(0)} = 0$ and $U_{(n)} = 1$. Then

$$ \mathbb{P}\left( \max_{1\leq i \leq n} [U_{(i)} - U_{(i-1)}] \leq d \right) = \sum_{k=0}^{n} (-1)^k \binom{n}{k} \max\{0, 1-dk\}^{n-1}. $$

So the positivity of the quantity in question corresponds to the above observation with $d = 2/n$ and $n \geq 2$, which can be easily shown to be positive by geometric argument. For instance, we may bound the probability in the left-hand side from below by

$$ \mathbb{P}\left( \left| U_1 - \frac{1}{n} \right| < \epsilon, \cdots, \left| U_{n-1} - \frac{n-1}{n} \right| < \epsilon \right) $$

for sufficiently small $\epsilon > 0$, such as $\epsilon = \frac{1}{2n}$.

Answer 2

We shall prove the following more general result:

Let $$S(n,m)=\sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n}{k} (n-2k)^{m},$$ with $0<m<n$.

Then: $$ S(n,m)\begin{cases} =0,& n-m=0\mod2;\\ >0,& n-m=1\mod4;\\ <0,& n-m=3\mod4. \end{cases}\tag{*} $$

Proposition 1. $\forall m\in\mathbb Z: 0<m<n$: $$\int_0^\infty\frac{\sin^{n}x}{x^{m+1}}dx>0.\tag1 $$ Proof: The integral $(1)$ is obviously convergent. For even $n$ the statement is obvious. For odd $n$ one rewrites the integral as: $$ \int_0^\infty\frac{\sin^{n}x}{x^{m+1}}dx =\sum_{k=0}^\infty a_k\tag2 $$ with $$ a_k=\int_{k\pi}^{(k+1)\pi}\frac{\sin^{n}x}{x^{m+1}}dx, $$ so that $(1)$ immediately follows since $(2)$ is an alternating series with $a_0>0$, $|a_{k}|>|a_{k+1}|$.

Proposition 2.

$\forall m\in\mathbb Z: 0<m<n$: $$S(n,m)=i^{n-1-m}\frac{2^{n-1}m!}\pi\int_{-\infty}^\infty\frac{\sin^{n}x}{x^{m+1}}dx.\tag3 $$ Proof: $$\begin{align} \int_{-\infty}^\infty\frac{\sin^{n}x}{x^{m+1}}dx &=\int_{-\infty}^\infty\frac{1}{x^{m+1}}\left(\frac{e^{ix}-e^{-ix}}{2i}\right)^n dx\\ &=\frac{1}{(2i)^n}\sum_{k=0}^n(-1)^k\binom nk \int_{-\infty}^\infty\frac{e^{i(n-2k)x}}{x^{m+1}}dx\\ &=\frac{1}{(2i)^n}\left[\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}(-1)^k\binom nk \oint_{\Gamma_+}\frac{e^{i(n-2k)z}}{z^{m+1}}dz+\sum_{k=\left\lfloor\frac n2\right\rfloor+1}^n(-1)^k\binom nk \oint_{\Gamma_-}\frac{e^{i(n-2k)z}}{z^{m+1}}dz\right], \end{align} $$ where $\Gamma_+$ is counterclockwise-directed contour running along the real axis and then along the (large) semicircle in the upper complex half-plane, and $\Gamma_-$ is clockwise-directed counterpart of $\Gamma_+$ running along the (large) semicircle in the lower complex half-plane. The last equality holds since the corresponding integrals along the semicircles tend to $0$ due to Jordan lemma.

To facilitate the computation of the integral we displace a part of the contour in the close vicinity of $z=0$ into the lower complex half-plane. This does not affect the value of the integral since the integrand of $(3)$ has no singularities, provided that $n>m$. By this approach the point $z=0$ will be surrounded only by the contours $\Gamma_+$, so that the integrals over $\Gamma_-$ vanish and one obtains: $$\begin{align} \int_{-\infty}^\infty\frac{\sin^{n}x}{x^{m+1}}dx &=\frac{1}{(2i)^n}\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}(-1)^k\binom nk \text{Res}_{z=0}\frac{e^{i(n-2k)z}}{z^{m+1}}\\ &=\frac{1}{(2i)^n}\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}(-1)^k\binom nk 2\pi i\frac1{m!} \frac{d^{m}}{dz^{m}}e^{i(n-2k)z}\\ &=\frac{i^{m-n+1}\pi}{2^{n-1} m!}\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}(-1)^k\binom nk (n-2k)^m, \end{align} $$ so that $(3)$ follows.

One observes that if $m$ and $n$ have the same parity the integrand in r.h.s. of $(3)$ is an odd function and the integral vanishes. If $m$ and $n$ have different parity the integrand is an even function, so that $(3)$ can be rewritten as: $$ S(n,m)=(-1)^{\frac{n-1-m}2}\frac{2^{n}m!}\pi\int_{0}^\infty\frac{\sin^{n}x}{x^{m+1}}dx. $$ Since the integral is according to Proposition 1 positive, the sign of the expression is that of $(-1)^{\frac{n-1-m}2}$. Thus the claim $(\text{*})$ is proved.

As a simple corollary one obtains $S(n,n-1)>0$.