Showing an alternating sum is positive

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.

• Is not it equivalent to $\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k \binom{n}{k} (n-2k)^{n-1}$? – user Feb 25 at 23:18
• @user Yes that's equivalent. – angryavian Feb 25 at 23:19
• Further information about these numbers can be found at oeis.org/A099765. – Ira Gessel Feb 26 at 14:33
• @IraGessel Thank you!! – angryavian Feb 26 at 17:37

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}$$.

• Nice to see that there is a way to make an inclusion-exclusion argument work out! – angryavian Mar 5 at 16:58

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.

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: $$\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: $$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$$.

• After someone posted the OEIS link, I found a source for your Proposition 2 for the case $m = n-1$ in this paper, and I used the same argument as Proposition 1 to answer my own question. I did not know about the pattern for more general $m$, so thank you for showing the general argument. – angryavian Mar 5 at 0:18