Show that $\binom{m+1}{2} - \binom{m-k+2}{2} \ge 2k.$

Question

EDIT:

Let $m$ and $k$ be integers such that $2 \le k \le\frac{m+1}2$ and $m>3.$ Show that $$\binom{m+1}{2} - \binom{m-k+2}{2}\ge 2k.$$

I know that it is suffices to show that $$m \ge \frac{k^2+k+2}{2(k-1)}.$$ But, I have no idea to show this. What I know was I have to show that $$2k-1 \ge \frac{k^2+k+2}{2(k-1)},$$ since $m\ge 2k-1$ from the given range of $m$ in the problem. But, this would yields $k \ge \frac73$, while the range of $k$ was given from $2$ to $\lfloor \frac{m+1}{2} \rfloor$.

Attempt: We want to show by strong induction on $k$.

Base Step: Since $m > 3$ and $m$ is an integer, then $m \ge 4$.

For $k=2$, we have $$\binom{m+1}{2} - \binom{m-2+2}{2} = m \ge 4 = 2 \cdot 2,$$ so the base step is done.

Induction Step: Assume that the inequality holds for any integers between $3$ (inclusive) and $k$ (exclusive). We want to show that the inequality holds for $k$. Since $k \ge 3$, then $k \ge \frac73$. Now, notice that \begin{align*} k \ge \frac73 \implies k(3k-7) &\ge 0 \\ 3k^2 - 7k & \ge 0 \\ 4k^2-6k+2 & \ge k^2+k+2 \\ (2k-1)(2k-2) & \ge k^2+k+2 \\ 2k-1 & \ge \frac{k^2+k+2}{2k-2}. \end{align*} Since $k \le \frac{m+1}{2}$, then $m \ge 2k-1$. Hence, $$m \ge \frac{k^2+k+2}{2k-2}.$$ Therefore, \begin{align*} km-m &\ge \frac{k^2+k+2}{2} \\ km-m - \frac{k^2+k+2}{2} & \ge 0 \\ \frac{m^2+m}{2} - \frac{m^2-2km+k^2+3m-3k+2}{2} - 2k & \ge 0 \\ \binom{m+1}{2} - \binom{m-k+1}{2} & \ge 2k. \end{align*} Thus, the induction step is complete.

Hence, proved.

Any ideas? Thanks in advance.

Answer 1

As you already noticed, $$\binom{m+1}2-\binom{m-k+2}2\ge 2k\Longleftarrow m\ge\frac{k^2+k+2}{2(k-1)}$$ (It is in fact an equivalence, since $\binom{m+1}2-\binom{m-k+2}2=\frac{2m(k-1)-(k^2-3k+2)}2$)

and for every integer $k\ge3,$ $m\ge2k-1\ge\frac{k^2+k+2}{2(k-1)}.$

You also proved separately that your inequality holds for $k=2.$

Hence you were done. You need no induction.

Answer 2

Alternative (direct) approach.

$$~k,m \in \Bbb{Z}, ~2 \leq k \leq \frac{m+1}{2}, ~m > 3. \tag1 $$

First, consider the case of $k=2, m \geq 4.$

$$\binom{m+1}{2} - \binom{m-2+2}{2} = \frac{[(m+1)(m)] - [m(m-1)]}{2} = \frac{2m}{2} \geq 2k.$$

Therefore, without loss of generality, $k \geq 3.$

Therefore :

• $(k - 1) \geq 2.$

• $2k \leq m+1.$

Therefore,

$$(m+1) - k \geq 0 \implies (2m+2 - k) \geq m+1 \geq 2k. \tag1 $$

Using (1) above, and the first bullet point above,

$$(k-1) \times [2m + 2 - k] \geq 4k \implies $$

$$(k-1) \times [(2m+1) - (k-1)] \geq 4k \implies $$

$$[(2m+1)(k-1)] - (k-1)^2 \geq 4k \implies $$

$$(m+1)(m) - \left\{ ~[(m+1)(m)] - (m+1)(k-1) - m(k-1) + (k-1)^2 ~\right\} \geq 4k.$$

This implies that

$$(m+1)(m) - \left\{ ~[(m+1) - (k-1)] \times [(m) - (k-1)] ~\right\} \geq 4k \implies $$

$$(m+1)(m) - \left[ ~(m + 2 - k) \times (m + 1 - k) ~\right] \geq 4k \implies $$

$$\frac{(m+1)(m)}{2} - \frac{(m+2 - k)(m+1-k)}{2} \geq 2k \implies $$

$$\binom{m+1}{2} - \binom{m+2-k}{2} \geq 2k.$$