2
$\begingroup$

$\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.

$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$
    – user
    Oct 20, 2018 at 13:34
  • $\begingroup$ 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. $\endgroup$
    – Quantaurix
    Oct 20, 2018 at 17:57

1 Answer 1

0
$\begingroup$

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 $

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .