Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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!

share|improve this answer

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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