4 added 88 characters in body

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

You can prove this 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$. Below, I assume 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!

3 added 95 characters in body

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

You can prove this 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$. Below, I assume 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.

2 added 89 characters in body

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

You can prove this 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$.

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 {n\choose 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$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.

1