Sufficient conditions for bound

Question

Let $m\leq n$ be nonnegative integers and $x > 0$. I would like to find sufficient conditions on $m,n,x$ (as tight as possible) s.t.

$$\frac{ \binom{n}{m} \sum_{j=0}^m j\binom{n}{m-j}x^j }{ x \left( \sum_{j=0}^m \binom{n}{m-j} x^j \right)^2 } < 1$$

Answer 1

So we have

$$ \binom{n}{m} \sum_{j=0}^m j\binom{n}{m-j}x^j < x \left( \sum_{j=0}^m \binom{n}{m-j} x^j \right)^2 $$

or

$$ \binom{n}{m} \sum_{j=0}^m j\binom{n}{m-j}x^j < x \left( \sum_{j=0}^m\sum_{k=0}^m \binom{n}{m-j} \binom{n}{m-k} x^j x^k\right) $$

or

$$ \binom{n}{m} \sum_{j=0}^m j\binom{n}{m-j}x^j < x\left( \sum_{j=0}^m\sum_{k=0}^m \binom{n}{m-j} \binom{n}{m-k} x^{j+k}\right) $$

On the right let $j=s+t$ and $k=t-s$ so $2t=j+k$ and $2s=j-k$.

$$ \binom{n}{m} \sum_{j=0}^m j\binom{n}{m-j}x^j < x\left( \sum_{t=0}^m\sum_{s=-m}^m \binom{n}{m-s-t} \binom{n}{m-t+s} x^{t}\right) $$

Moving the $x$ into the summation and noting that for $j=0$ the summation on the right vanishes,

$$ \binom{n}{m} \sum_{j=1}^m j\binom{n}{m-j}x^j < \left( \sum_{t=0}^m\sum_{s=-t}^t \binom{n}{m-s-t} \binom{n}{m-t+s} x^{t+1}\right) $$

Making the substitution $j=j-1$,

$$ \binom{n}{m} \sum_{j=0}^{m-1}(j+1)\binom{n}{m-j}x^{j+1} < \sum_{t=0}^m x^{t+1}\left( \sum_{s=-t}^t \binom{n}{m-s-t} \binom{n}{m-t+s}\right) $$

Linear independence of $x^j$ tells us that we require the following for all $j=0,...,m-1$

$$ \binom{n}{m}(j+1)\binom{n}{m-j} < \left( \sum_{s=-j}^j \binom{n}{m-s-j} \binom{n}{m-j+s}\right) $$

Rewriting this,

$$ \frac{n!}{m!(n-m)!}(j+1) \frac{n!}{(m-j)!(n-m+j)!} < \sum_{s=-j}^j \frac{n!}{(m-s-j)!(n-m+s+j)!}\frac{n!}{(m+s-j)!(n-m-s+j)!}$$

And this is exact. You can try to put this in MATLAB or excel to play around with various m and n.

One more simplification can be performed $$ \frac{(j+1)}{m!(n-m)!(m-j)!(n-m+j)!} < \sum_{s=-j}^j \frac{1}{(m-s-j)!(n-m+s+j)!(m+s-j)!(n-m-s+j)!}$$

Answer 2

Note: This is only a rudimentary answer to your question together with some additional information at the end.

A short overview:

• We transform the inequality to gain some insight in the structure
• Results for a few special values
• Some references related to this question

First step Transformation of the inequality

The idea is to transform the inequality so that we can better see, which parts are responsible to invalidate it.

\begin{align*} 0<x\left(\sum_{j=0}^{m}\binom{n}{m-j}x^{j}\right)^2-\binom{n}{m}\sum_{j=0}^{m}\binom{n}{m-j}jx^j\tag{1} \end{align*}

Regrettably we hardly have a chance to find a closed formula for \begin{align*} \sum_{j=0}^{m}\binom{n}{j}x^j \qquad 0\leq m\leq n\tag{2} \end{align*} since as you can read e.g. in the second edition of

Concrete Mathematics from Graham, Knuth and Patashnik

There is no closed form for the partial sum of a row of Pascal's triangle.

But we find another interesting hint in section 5.1 for a closed formula in case (2) is multiplied by it's distance to the center:

\begin{align*} \sum_{j=0}^{m}\binom{n}{j}\left(\frac{n}{2}-j\right)=\frac{m+1}{2}\binom{n}{m+1} \tag{3} \end{align*}

We use a similar technique to transform the inequality and so unify the sums from (1).

Let \begin{align*} A_{m,n}(x)&=\sum_{j=0}^{m-1}\binom{n-1}{j}x^{m-j}\qquad 1\leq m\leq n \end{align*} then \begin{align*} \sum_{j=0}^{m}\binom{n}{m-j}x^{j}&=\binom{n-1}{m}+(1+x)A_{m,n}(x)\\ \sum_{j=0}^{m}\binom{n}{m-j}jx^{j}&=m\binom{n-1}{m}+\left(m-(n-m)\frac{1}{x}\right)A_{m,n}(x)\\ \end{align*}

Note: We use the convention, that the empty sum and binomial coefficient $\binom{n}{j}$ with $n<0$ is considered to be $0$.

The statement above is valid since \begin{align*} \sum_{j=0}^{m}&\binom{n}{m-j}x^{j}=\sum_{j=0}^{m}\binom{n}{j}x^{m-j}\\ &=\sum_{j=0}^{m}\binom{n-1}{j}x^{m-j}+\sum_{j=1}^{m}\binom{n-1}{j-1}x^{m-j}\\ &=\sum_{j=0}^{m}\binom{n-1}{j}x^{m-j}+\frac{1}{x}\sum_{j=0}^{m-1}\binom{n-1}{j}x^{m-j}\\ &=\binom{n-1}{m}+(1+x)A_{m,n}(x)\\ \end{align*}

and \begin{align*} \sum_{j=0}^{m}&\binom{n}{m-j}jx^{j}=\sum_{j=0}^{m}\binom{n}{j}(m-j)x^{m-j}\\ &=m\sum_{j=0}^{m}\binom{n}{j}x^{m-j}-\sum_{j=1}^{m}\binom{n}{j}jx^{m-j}\\ &=m\sum_{j=0}^{m}\binom{n}{j}x^{m-j}-n\sum_{j=1}^{m}\binom{n-1}{j-1}x^{m-j}\\ &=m\left(\sum_{j=0}^{m}\binom{n-1}{j}x^{m-j}+\sum_{j=1}^{m}\binom{n-1}{j-1}x^{m-j}\right)\\ &\qquad-\frac{n}{x}\sum_{j=0}^{m-1}\binom{n-1}{j}x^{m-j}\\ &=m\left(\sum_{j=0}^{m}\binom{n-1}{j}x^{m-j}+\frac{1}{x}\sum_{j=0}^{m}\binom{n-1}{j}x^{m-j}\right)\\ &\qquad-\frac{n}{x}\sum_{j=0}^{m-1}\binom{n-1}{j}x^{m-j}\\ &=m\binom{n-1}{m}+\left(m-(n-m)\frac{1}{x}\right)A_{m,n}(x)\\ \end{align*}

Now putting all together gives

\begin{align*} 0<&x\left(\sum_{j=0}^{m}\binom{n}{m-j}x^{j}\right)^2-\binom{n}{m}\sum_{j=0}^{m}\binom{n}{m-j}jx^j\\ &=x\left(\binom{n-1}{m}+\left(1+\frac{1}{x}\right)A_{m,n}(x)\right)^2\\ &\qquad-\binom{n}{m}\left(m\binom{n-1}{m}+\left(m-(n-m)\frac{1}{x}\right)A_{m,n}(x)\right)\\ \end{align*}

And after some rearrangement we finally get the

Resulting inequality: \begin{align*} A_{m,n}&=\sum_{j=0}^{m-1}\binom{n}{m-j}x^{m-j}\qquad 1\leq m \leq n,\quad x> 0\\ \\ 0<&(1+x)^2A_{m,n}^2(x)\\ &+\binom{n-1}{m}\left(2x^2+\left(2-\frac{nm}{n-m}\right)x+n\right)A_{m,n}(x)\\ &+\binom{n-1}{m}^2x\left(x-\frac{nm}{n-m}\right)\\ \end{align*}

Observe, that the only factors which could become negative in the equality above are \begin{align*} 2x^2+\left(2-\frac{nm}{n-m}\right)x+n\qquad\text{and}\qquad x-\frac{nm}{n-m}\tag{4} \end{align*} We see, that in case of fixed $x$ and growing $n$ the terms become more and more negative as $m$ is approaching $n$. But we also know that $A_{m,n}^2$ grows very fast, when $m$ approaches $n$. This is immediately clear if we consider $$\sum_{j=0}^{n}\binom{n}{j}=2^n\qquad\text{and}\qquad\sum_{j=0}^{m}\binom{2m+1}{j}=\frac{1}{2}2^{2m+1}$$

So, a further elaboration could have a look at the zeroes of (4) and try to analyse the resulting regions with negative values together with the growing behaviour of $A_{m,n}$.

Step 2: Some special values

Which I did only for curiosity to get a first impression of the inequality. In the following we always assume $x>0$.

m=0 valid for $n\geq0$

You can see immediately that the inequality (1) is valid for all $x>0$ and $n\geq0$.

m=1 valid for $n>0$

This leads to the inequality $(n+x)^2-n>0$ which is also valid for all $n>0$.

m=2 valid for $n>4$

With the help of Wolfram Alpha we find $n\geq 4.69858$ and $x>0$.

The corresponding inequality is

$$x^4+2nx^3+n(2n-1)x^2+n^2(n-1)x+\frac{1}{4}n^2(n-1)^2>0$$

m=n valid for $n>0$.

with inequality

$$(x+1)^{n+1}-n>0$$

m=n-1 valid for $n>0$.

with inequality

$$\frac{1}{x}\left((x+1)^{n}-1\right)^2-\frac{n}{x}\left((x+1)^{n-1}\left(nx+(x+1)\right)+1\right)>0$$

Step 3: Some additional info

Here is some related information which may be helpful when estimating the sum $\sum_{j=0}^{m}\binom{n}{m}$ for large values of $n$.

• A question from mathOverflow
• Another question from MSE
• and an interesting paper about lower and upper bounds for sums of binomial coefficients from Thomas Worsch.

Answer 3

For what it's worth, Mathematica gives a closed form in terms of the hypergeometric functions, which may or may not be helpful if you are proficient with them:

$$ \sum_{j=0}^m j \binom{n}{m-j} x^j = x \binom{n}{m-1} {}_2F_1(2, 1-m; -m+n+2; -x) $$

$$ \sum_{j=0}^m x^j \binom{n}{m-j} = \binom{n}{m} {}_2F_1 (1, -m; -m+n+1; -x) $$

http://www.wolframalpha.com/input/?i=sum+j+binomial%28n%2C+m-j%29+x%5Ej+for+j%3D0..m

http://www.wolframalpha.com/input/?i=sum+binomial%28n%2C+m-j%29+x%5Ej+for+j%3D0..m