Binomial coefficients inequality

Question

It seems to me that there should be a simple way to prove that $$ \binom{n}{s+1+a} + \binom{n}{a} \leq \binom{n}{s} $$

For $s > n/2$ and $a < n-s$.

However it looks like I'm missing it. Any suggestions?

Answer 1

I proved it a couple of month ago, but as no one else provided an answer I'll just write my own. I'll prove the following claim: $$ \binom{n}{k-1-a} + \binom{n}{a} \leq \binom{n}{k} $$ for every $ k \leq n/2$ and every $0\leq a < k$ (this is the same as the original proposition but with $k = n-s$).

proof

Because $\binom{n}{k-1-a} + \binom{n}{a}$ is symmetric for $a$ around $(k-1)/2$ we suppose $a \leq (k-1)/2$. We have $$ {n \choose k}-{n \choose k-1}={n \choose a}\frac{(n-a)\cdots(n-k+2)(n-2k+1)}{k\cdots(a+1)} $$

and since $\frac{n-a}{k}\geq1.5$ and $\frac{n-2k+1}{a+1}\geq\frac{2}{k+1}$ we get that $$ {n \choose k}-{n \choose k-1}\geq{n \choose a}(1.5)^{k-a-1}\frac{2}{k+1}\geq{n \choose a}(1.5)^{(k-1)/2}\frac{2}{k+1} $$ and since $(1.5)^{(k-1)/2}\frac{2}{k+1}\geq1$ for $k\geq9$ we get that $$ {n \choose k}\geq{n \choose k-1}+{n \choose a}\geq{n \choose k-1-a}+{n \choose a}\;. $$ If $k\leq8$ and $n\geq21$ we get that $\frac{n-2k+1}{a+1}\geq1$ and the stronger claim, ${n \choose k}-{n \choose k-1} \geq {n \choose a}$, holds. For $n<21$ we can easily verify using a computer that the proposition (not the stronger claim) indeed holds.