Let $C=\dfrac{1}{k}\left [\binom{2k-1}{k}-1 \right ]$ where $k \ge 3$. Show that $C\ge 3$.

Question

I have a problem:

Let $C=\dfrac{1}{k}\left [\binom{2k-1}{k}-1 \right ]$ where $k \ge 3$. Show that $C\ge 3$.

Any help will be appreciated! Thanks!

Answer 1

Write $\frac{(2k-1)!}{k!} = (2k-1)(2k-2)(2k-3)...(k+1)$ so

$\frac{1}{k}{2k-1\choose k} = \frac{(2k-1)!}{(k!)^2} = \frac{(2k-1)}{1}\frac{(2k-2)}{2}\frac{(2k-3)}{3}\cdot\cdot\cdot \frac{k+1}{k-1}\frac{1}{k} \geq \frac{(2k-1)(2k-2)(2k-3)}{6k} \geq \frac{10}{3}$

for $k\geq 3$ (see the comment below for the last ineqality).

Answer 2

The simplest recursion works. Rewrite the inequality to prove as $$ {2k-1\choose k}\geqslant3k+1. $$ If this holds for some $k$, then $$ {2k+1\choose k+1}=\frac{4k+2}{k+1}{2k-1\choose k}\geqslant\frac{4k+2}{k+1}\frac{3k+1}{3k+4}(3k+4), $$ hence the property holds for $k+1$ as soon as $$ \frac{4k+2}{k+1}\frac{3k+1}{3k+4}\geqslant1. $$ This last condition reads $$ 9k^2+3k\geqslant2, $$ hence the implication [case $k$ $\implies$ case $k+1$] holds for every $k\geqslant1$. Case $k=3$ holds hence the recursion is complete.

Note how the approach avoids any choice of lower bound of some terms by some simpler ones, until the very end, that is, one eliminates any clever guessing. On the other hand, this leads to prove a stronger result than simply $C_n\geqslant3$ for every $n$, hence this relies on a monotonicity property, which might not hold although the final result could.