# Prove positivity of a binomial sum

Some problems appear easy on the face of it, but perhaps they are not. Here is an instance of a certain calculation which is slightly reformulated from its original encounter in a current work. I have no proof.

QUESTION. Assume we are working in a domain where the denominators do not vanish. Is this true? $$\sum_{k=0}^{2t}\frac{(-1)^k\, \binom{q+1}k}{\binom{n+k-q-1}{n-m-q}}\geq0.$$

• You wrote: "Here is an instance of a by-product of certain calculation which is slightly reformulated from their original encounter in a current work." -- It is unclear to me whether (i) you have a proof of this "by-product" and want another proof of it or (ii) you don't have a proof -- but then why is this inequality a by-product? Feb 21 at 17:11
• You are right. Let me rephrase. Feb 21 at 17:25

Let $$N$$ be a positive integer and $$c_1,\ldots,c_N$$ non-negative real numbers. Denote $$f(x)=((x+c_1)\ldots (x+c_N))^{-1}$$.

Lemma 1. For all integer $$d\geqslant 0$$ and all $$x>0$$ we have $$(-1)^df^{(d)}(x)>0$$.

Proof. Induction in $$d$$. Base $$d=0$$ is trivial. For doing an induction step it suffices to note that $$-f'$$ is a sum of $$N$$ functions of the same type.

Lemma 2. For a non-negative integer $$d$$, real $$a$$, and a continuous real function $$f(x)$$ defined on the segment $$[a,a+d]$$ and having $$d$$ derivatives on the interval $$(a,a+d)$$ ($$d$$-th derivative may be discontinuous) there exists $$\theta\in (0,d)$$ such that $$f^{(d)}(a+\theta)=\sum_{k=0}^d (-1)^{d-k}{d\choose k}f(a+k)=:c$$

Proof. Denote $$h(x)=\sum_{k=0}^d f(a+k){x\choose k}{d-x\choose d-k}$$.Then $$h(x)=\frac{c}{d!}x^d+\ldots$$ is a polynomial of degree at most $$d$$ and $$h(k)=f(a+k)$$ for all $$k=0,1,\ldots,d$$. Therefore, by Rolle's theorem, the function $$g(x):=f(a+x)-h(x)$$, which has roots at points $$0,1,\ldots,d$$, satisfies $$g^{(d)}(\theta)=0$$ for certain $$\theta\in (0,d)$$. This $$\theta$$ is what we need.

Now call a function $$f(k)$$ good if it has a type $$f(k)=\frac{C}{(k+r)(k+r+1)\ldots (k+s)}$$ for certain $$C>0$$ and positive integers $$r\leqslant s$$. These two lemmata already yield that when $$q+1\leqslant 2t$$, then $$\sum_{k=0}^{2 t} (-1)^k{q+1\choose k}f(k) \geqslant 0$$ that is your claim (is it?)

For larger values of $$q$$, we induct on $$q$$ with use of Pascal's recurrence $${q+1\choose k}={q\choose k}+{q\choose k-1}$$ which allows to write \begin{align*} \sum_{k=0}^{2t} (-1)^k {q+1\choose k}f(k) &=\sum_{k=0}^{2t} (-1)^k {q\choose k}f(k)-\sum_{k=0}^{2t-1} (-1)^k{q\choose k}f(k+1) \\ &={q\choose 2t}f(2t+1)+\sum_{k=0}^{2t}(-1)^k{q\choose k}(f(k)-f(k+1)). \end{align*} Since the function $$k\to f(k)-f(k+1)$$ is good, we reduced $$q+1$$ to $$q$$.

• Nice. Should $g^{(d)}(a+\theta)$ be $g^{(d)}(\theta)$? In the case $q+1\leq 2t$, your sum is in fact $\sum_{k=0}^{q+1}(-1)^k\binom{q+1}kf(k)$ which implies $d=q+1$. But then, although $2t$ is even $q+1$ need not be. In that case, does Lemma 1 give positivity? Feb 22 at 0:15
• I fixed the typo with $g^{(d)} (a+\theta)$, thank you. Lemma 1 gives positivity for every parity of $d$. Parity of $2t$ plays role only for the induction step. Feb 22 at 5:48

I think one can simplify Fedor's proof using the point of view of Bernstein's Theorem for completely monotone functions, together with Bonferroni's Inequalities from probability.

The given sum is $$S=(n-m-q)!\ \sum_{k=0}^{2t}(-1)^k\binom{q+1}{k}\ \frac{1}{(k+m)(k+m+1)\cdots(k+n-q-1)}$$

$$=(n-m-q)!\int_0^{\infty}\left(\sum_{k=0}^{2t} (-1)^k\binom{q+1}{k} e^{-kx}\right)\ d\mu(x)$$ where $$\mu$$ is the convolution of the measures on $$[0,\infty)$$ given by $$e^{-mx}dx$$, $$e^{-(m+1)x}dx,\ldots,\ e^{-(n-q-1)x}dx$$. All that matters is that $$\mu$$ is a positive measure. Then take $$y=e^{-x}$$ in the following lemma.

Lemma:

For all $$y\in [0,1]$$, $$\sum_{k=0}^{2t}\binom{q+1}{k} (-y)^k\ge (1-y)^{q+1}.$$

For the proof see the nice write-up by user Mike Earnest

https://math.stackexchange.com/a/4490819/244562

in relation to the Bonferroni Inequalities. I think one can also use Abel (discrete) summation by parts and reduce to the partial alternate sums of binomials which, if I remember correctly, give a sign times a binomial.

• That's better then my argument, since it works for a wider class of functions Feb 26 at 9:17
• @FedorPetrov: Thanks! It is just a reformulation of your idea which is great BTW. Is it standard for this type of positivity problem? Do you know if there is an analogue of Krattenthaler's review of methods in determinant calculus, for inequalites with alternating combinatorial sums, especially with more than one summation? I had to deal with a pretty severe example in my paper arxiv.org/abs/1903.11147 , please have a look at Proposition 6. Feb 27 at 15:41