<s>[INST] Prove that $\binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m$ for $m\in \mathbb{N}\backslash \{0,1\}$ Prove the following inequality for every $m\in \mathbb{N}\backslash \{0,1\}$:
$$ \binom{13+m}{m}-(m+1)\binom{6+m}{m}\geq m.$$
By some computational arguments, the inequality seems to be true and in particular the difference between the first term $\binom{13+m}{m}$ and the second one $(m+1)\binom{6+m}{m}$ is very large, so obviously is more that $m$. Hence the use of the induction technique, in order to find a way to give a formal proof, leads to a disaster consequence.
In fact, for $m=2$ the inequality is trivial. Fix $m> 2$ and suppose the the inequality is true for $m$. We want to prove that
$$ \binom{14+m}{m+1}-(m+2)\binom{7+m}{m+1}\geq m+1.$$
Start from the first member and apply Stifiel's formula
$$ \binom{14+m}{m+1}-(m+2)\binom{7+m}{m+1}=\binom{13+m}{m+1}+\binom{13+m}{m}-(m+1+1)\Big[\binom{6+m}{m+1}+\binom{6+m}{m}\Big]=
\binom{13+m}{m}-(m+1)\binom{6+m}{m}+\binom{13+m}{m+1}-(m+1)\binom{6+m}{m+1}-\binom{6+m}{m+1}-\binom{6+m}{m}\geq...
$$
Applying the inductive hypothesis we have:
$$...\geq m+\binom{13+m}{m+1}-(m+1)\binom{6+m}{m+1}-\binom{6+m}{m+1}-\binom{6+m}{m},$$
but this is less than $m+1$. Therefore we don't get the desired conclusion.
Which can be an useful stategy to prove this inequality?
 [/INST] I agree that the problem has been reduced to proving that for all $m \in \Bbb{Z_{\geq 2}}$,
$$\binom{13+m}{m+1}-(m+1)\binom{6+m}{m+1}-\binom{6+m}{m+1}-\binom{6+m}{m} \geq 1. \tag1 $$
In (1) above, on the LHS, the two rightmost terms may be collapsed into
$$\binom{13+m}{m+1}-(m+1)\binom{6+m}{m+1}-\binom{7+m}{m+1} \geq 1. \tag2 $$
Empirically, (2) above holds for $m = 2$.  Induction may be used to show that (2) above holds for all $m \in \Bbb{Z_{\geq 2}}.$
This is done by showing that for all $m \in \Bbb{Z_{\geq 2}}$, you have that
$$\binom{14+m}{m+2} - \binom{13+m}{m+1} \tag{A-1}$$
$$\geq \left[(m+2)\binom{7+m}{m+2} - (m+1)\binom{6+m}{m+1} \right] \tag{A-2}$$
$$+ \binom{8+m}{m+2} - \binom{7+m}{m+1}. \tag{A-3}$$
(A-1) above collapses into $~\displaystyle \binom{m+13}{m+2}.$
(A-2) above collapses into $~\displaystyle \left[(m+1)\binom{m+6}{m+2}\right] + \binom{m+7}{m+2}.$
(A-3) above collapses into $~\displaystyle \binom{m+7}{m+2}.$
So, the inequality in (A-1),(A-2) and (A-3) above is equivalent to the assertion that for all $m \in \Bbb{Z_{\geq 2}},$
$$\binom{m+13}{m+2} \geq \left[(m+1)\binom{m+6}{m+2}\right] + \binom{m+7}{m+2} + \binom{m+7}{m+2} $$
which is equivalent to the assertion that
$$\binom{m+13}{m+2} \geq \left[(m+1)\binom{m+6}{m+2}\right] + 2\binom{m+7}{m+2}. \tag3 $$
The exploration of (3) above may be simplified by dividing each term by $~\displaystyle \binom{m+6}{m+2}.$
This yields the equivalent assertion of
$$\frac{[(m+13)!]~~(4!)}{[(m+6)!]~~ (11!)} \geq (m+1) + (2)\frac{m+7}{5} = \frac{7m + 19}{5}. \tag4 $$
Empirically, (4) above is true for $m=2$.
Assume that (4) above is true for $m$.
As $m \to (m+1)$, the LHS of (4) above is multiplied by
$~\displaystyle \frac{m+14}{m+7}$,
while the RHS of (4) above is multiplied by
$~\displaystyle \frac{7m+26}{7m+19}.$
Note that $~\displaystyle (m+14)(7m+19) = 7m^2 + 117m + 266$
while $~\displaystyle (m+7)(7m+26) = 7m^2 + 75m + 182.$
Therefore, in (4) above, as $m \to (m+1)$, the LHS is multiplied by a larger factor than the RHS.
Therefore, (4) above is true for any $m \in \Bbb{Z_{\geq 2}}$, as required.
</s>