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?
 A: Writing the inequality as
$$
    \binom{m+13}{13} - \binom{m+6}{6} - m \binom{m+6}{6} \ge m
$$
and then as
$$
    \binom{m+13}{13} - \binom{m+6}{6} - 7\binom{m+6}{7} \ge m
$$
we can find a combinatorial interpretation for the left-hand side. Out of $\binom{m+13}{13}$ subsets of choose $13$ elements from $\{1,2,\dots,m+13\}$, there are $\binom{m+6}{6}$ subsets that contain all of $\{1,2,3,4,5,6,7\}$ (and then $6$ elements from the rest), and $7\binom{m+6}{7}$ subsets that contain six of $\{1,2,3,4,5,6,7\}$ (and then $7$ elements from the rest).
To prove the inequality, it's enough to find at least $m$ subsets that don't look like this. For example, consider all the subsets that contain the $12$ elements $\{m+2,m+3,\dots,m+13\}$ and then one of the elements from $\{1,2,\dots,m\}$. Provided $m \ge 2$, these are disjoint from the previous cases because we include at most one of the elements $1,2,3$.
A: 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.
A: Using the identity (well-known, easy to prove)
$$\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}, $$
we have
\begin{align*}
 \binom{13 + m}{m} &= \binom{12 + m}{m} + \binom{12 + m}{m - 1}\\
 &= \binom{11 + m}{m} + \binom{11 + m}{m - 1} + \binom{11 + m}{m - 1} + \binom{11 + m}{m - 2}\\
 &\ge \binom{11 + m}{m} + 2\binom{11 + m}{m - 1}\\
 &= \binom{10 + m}{m} + \binom{10 + m}{m - 1}
 + 2\binom{10 + m}{m - 1} + 2\binom{10 + m}{m - 2}\\
 &\ge \binom{10 + m}{m} + 3\binom{10 + m}{m - 1}.
\end{align*}
After repeating the process, we have
$$\binom{13 + m}{m} \ge \binom{7 + m}{m} + 6\binom{7 + m}{m - 1}.$$
It suffices to prove that
$$\binom{7 + m}{m} + 6\binom{7 + m}{m - 1} - (m + 1)\binom{6 + m}{m} \ge m$$
or (after some simple manipulations)
$$6m(m - 1)\frac{(6 + m)!}{m!\, 8!} \ge m$$
or
$$6(m - 1)\frac{(6 + m)!}{m!\, 8!} \ge 1$$
or
$$6(m - 1)\frac{(6 + m)(5 + m)(4 + m)(3 + m)(2 + m)(1 + m)}{8!} \ge 1$$
which is true since
$$\mathrm{LHS} \ge 6(2 - 1)\frac{(6 + 2)(5 + 2)(4 + 2)(3 + 2)(2 + 2)(1 + 2)}{8!} = 3.$$
We are done.
