A property of unimodal sequences

Question

It is well-known that $(-1)^j \sum_{i=0}^j (-1)^i\binom{n}{i} \geq 0$. This inequality can be used to prove Bonferroni's inequalities for example. Recently I noticed that a similar inequality applies to non-negative unimodal sequences with alternating zero sum: if $a_0 \leq a_1 \leq \ldots \leq a_k \geq a_{k+1} \geq \dots \geq a_{n}$ with $\sum_{i=0}^n (-1)^i a_i = 0$ then $(-1)^j \sum_{i=0}^j (-1)^i a_i \geq 0$ for $j=0 \ldots n$. Of course the binomial sequence is just a special case. My question is if anyone has any knowledge of this property of unimodal sequences having appeared or having been used anywhere in the literature? Thanks.

Jose A Rodriguez

Answer 1

Closely related ideas come up in discrete Morse theory too, in proving the Morse inequalities.

You can prove your inequality combinatorially by a sign-reversing involution argument, i.e. a type of matching argument, as follows. Make a graded partially ordered set with $a_i$ elements at rank $i$, i.e. in the $i$-th level of the poset, for each $i$. Now include all possible edges between ranks $i$ and $i+1$ for each $i$. I am assuming the $a_i$'s are integers, but you can do a weighted version otherwise.

Greedily start at rank $0$, taking each element of rank $i$ for $i < k$ which hasn't already been matched with an element of rank $i-1$ and matching it with an element of rank $i+1$. Likewise, start at rank $n$ and proceed downwards through the poset, greedily taking element of rank $n-i$ for $n-i > k$ which hasn't already been matched with an element of rank $n-i+1$ and matching it with an element of rank $n-i-1$. When we get to rank $k+1$, we must only match with those elements of rank $k$ that weren't already matched with elements of rank $k-1$. The fact that the alternating sum is 0 tells us we can get a complete matching this way.

Now we can interpret $(-1)^j\sum_{i=0}^j (-1)^i a_i$ as the number of elements at rank $j$ that have been matched with elements at rank $j+1$, so in particular as a nonnegative integer. To see this, assign weight $+1$ to each element at rank $j$ or at any other rank of the same parity as $j$; assign weight $-1$ to the elements whose rank differs from $j$ by an odd number. The alternating sum you consider is now the sum of the weights for ranks $0$ to $j$. Each matching edge completely contained in the lowest $j$ ranks contributes 0 to this alternating sum, whereas each element of rank $j$ that is matched with an element of rank $j+1$ contributes 1 to this alternating sum.

I agree with Vladimir that this is a very nice observation you've made!

Answer 2

For $k=0$ (a decreasing sequence), the proof is more or less the key idea that makes Leibniz convergence test work, for instance. Since the total alternating sum is zero, you are always reduced to the case $k=0$ (if you go past the mode, you can replace your sum with the "better half" of the total alternating sum), so it is not much of a generalisation. It's a very cute observation though!

Answer 3

I'm digging out an old post...

Does anyone know a reference for the property enunciated by Jose A Rodriguez in 2012?

I thought it was a well-known properties of unimodal sequence. Nevertheless, Louis Comtet does not speak about it in his books "Advanced Combinatorics: The Art of Finite and Infinite Expansions" (1974). Nor are Knuth, Patashnik and Graham in "Concrete Mathematics" (1988)

Thanks for the help