Inequality $\binom{n+m}{k}+\binom{n-m}{k}\ge 2\binom{n}{k}$

Question

Is it true that $\binom{n+m}{k}+\binom{n-m}{k}\ge 2\binom{n}{k}$?

I've been checking this for many cases in the Pascal triangle ($n,m,k\in\mathbb{N}^*$ such that $n-m\ge k$) but cannot prove formally.

Answer 1

Claim. The inequality $$\binom{n+m}k+\binom{n-m}k \ge 2 \binom nk$$ holds for any integers such that $0\le m,k \le n$.

Proof. It is clear that this is true for $k=0$. So we will assume from now on that $k\ge1$.

Let us denote $$a_j=\binom{n+j}k+\binom{n-j}k$$ for $j=0,1,\dots,n$. We have $a_0=2\binom nk$. It suffices to show that the sequence $a_j$ is non-decreasing.

For this, we just compute \begin{align*} a_{j+1}-a_j&=\binom{n+j+1}k-\binom{n+j}k-\binom{n-j}k+\binom{n-j-1}k\\ &=\binom{n+j}{k-1}-\binom{n-j-1}{k-1} \ge 0. \end{align*} So we get $a_{j+1}-a_j\ge0$ and thus $a_{j+1}\ge a_j$ whenever $j \le n-1$ (and $k-1 \ge 0$.

---

You can find other approaches to this problem (or generalizations) here:

• How can we show binomial function is convex without calculus?
• Convexity of Binomial Term
• Prove that $\binom{a_1}{2} + \binom{a_2}{2} + \cdots + \binom{a_n}{2} \ge r\binom{k+1}{2} + \left(n-r\right)\binom{k}{2}$

Answer 2

As an alternative, by induction, after the base case, we can proceed as follows for the induction step assuming true that $\binom{n+m}{k}+\binom{n-m}{k}\ge 2\binom{n}{k}$, then

$$\binom{n+m+1}{k}+\binom{n-m-1}{k}=\binom{n+m}{k}+\binom{n+m}{k-1}+\binom{n-m}{k}-\binom{n-m-1}{k-1}\ge $$

$$\ge 2\binom{n}{k}+\binom{n+m}{k-1}-\binom{n-m-1}{k-1}\ge 2\binom{n}{k}$$

since $\binom{n+m}{k-1}-\binom{n-m-1}{k-1}\ge0$

---

Edit

This answer is related to the following deleted question from the user Andrew.

Answer 3

Let us prove that for a fixed $k$, the function $f(a)=\binom{a}{k}$ defined on $[k,+\infty)$ is convex. Clearly

$$ f(a) = \frac{a!}{k!(a-k)!} = \frac{1}{k!}\cdot\frac{\Gamma(a+1)}{\Gamma(a+1-k)} $$

so it is enough to show that $$ \frac{d^2}{da^2}\left(\frac{\Gamma(a+1)}{\Gamma(a+1-k)}\right)\geq 0. $$ Since $\Gamma'(z)=\Gamma(z)\psi(z)$, the chain rule ensures

$$ \frac{d^2}{da^2}\binom{a}{k} = \binom{a}{k}\left(\psi(a+1)-\psi(a+1-k)\right)^2+\binom{a}{k}\left(\psi'(a+1)-\psi'(a+1-k)\right)$$ and we have to prove $$ \left(\sum_{n\geq 1}\frac{1}{n+a-k}-\frac{1}{n+a}\right)^2+\sum_{n\geq 1}\left(\frac{1}{(n+a)^2}-\frac{1}{(n+a-k)^2}\right)\geq 0 $$ or $$ \left(\sum_{n\geq 1}\frac{k}{(n+a)(n+a-k)}\right)^2\geq \sum_{n\geq 1}\left(\frac{k}{(n+a)^2 (n+a-k)}+\frac{k}{(n+a) (n+a-k)^2}\right). $$ This is not trivial, but since $k\in\mathbb{N}^+$ it simplifies into $$ \left(\sum_{n=1}^{k}\frac{1}{n+a-k}\right)^2 \geq \sum_{n=1}^{k}\frac{1}{(n+a-k)^2} $$ which is fairly obvious. Now that the convexity of $\binom{a}{k}$ is proved the inequality $$ \binom{n-m}{k}+\binom{n+m}{k} \geq 2\binom{n}{k} $$ simply follows from the midpoint-convexity. Additional remark: the sequence $\left\{\binom{n}{k}\right\}_{n\geq k}$ is convex but not log-convex. Actually it is log-concave, since $\frac{d^2}{da^2}\log f(a) =\psi'(a+1)-\psi'(a-k+1)\leq 0.$