# Proving a binomial coefficient inequality per induction

$$\left(\begin{array}{c}2n\\ n+k\end{array}\right) < \left(\begin{array}{c}2n\\ n\end{array}\right), n,k \in \mathbb{N}, 1\leq k \leq n$$

Proving this by induction on $$k$$ is no problem. However, I want to prove this by induction on $$n$$, but I am stuck because of a too "harsh" inequality estimation: $$\left(\begin{array}{c}2(n+1)\\ (n+1)+k\end{array}\right) = \frac{(2n+1)(2n+2)}{(n+1-k)(n+1+k)} \left(\begin{array}{c}2n\\ n+k\end{array}\right) < (induction \space hypothesis) \frac{(2n+1)(2n+2)}{(n+1-k)(n+1-k)} \left(\begin{array}{c}2n\\ n\end{array}\right)$$

But $$\frac{(2n+1)(2n+2)}{(n+1-k)(n+1+k)} \left(\begin{array}{c}2n\\ n\end{array}\right) \nleq \left(\begin{array}{c}2(n+1)\\ n+1\end{array}\right)$$

which ruins the inductive step.

I don't know if I am getting something wrong or one has to handle it differently. Thanks in advance.

• Not always induction works and sometimes it works on stronger conditions. I'm talking in general I didn't try with that! See for example the following case
– user
Oct 20, 2018 at 13:34
• Thx for that tip, I tried to find some "convenient" $c<1$ s.t. $\left(\begin{array}{c}2n\\ n+k\end{array}\right) < c \times \left(\begin{array}{c}2n\\ n\end{array}\right) \leq \left(\begin{array}{c}2n\\ n\end{array}\right)$ but have not been successful yet. Oct 20, 2018 at 17:57

Choose $$c$$ s.t. $$\left(\begin{array}{c}2n\\ n+k\end{array}\right) < c \times \left(\begin{array}{c}2n\\ n\end{array}\right) < \left(\begin{array}{c}2n\\ n\end{array}\right)$$ . $$c = \frac{(n+1-k)(n+1+k)}{(n+1)(n+1)}$$. The inductive step (first inequality) works. The second inequality is true since $$\frac{(n+1-k)(n+1+k)}{(n+1)(n+1)} = 1 - \frac{k^2}{(n+1)^2} < 1$$