Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $n\in N. $ Which of the following inequalities are TRUE.
$(a)$ For every $n>1$, $ \quad {{2n}\choose{n}}^{1/n}> 2.$
$(b)$ For every $n\geq1$ , $\quad {{2n}\choose{n}}< \frac{1}{\sqrt{2n+1}}.$
$(c)$For every $n>1$,$ \quad n!{{2n}\choose{n}}< (2n)^n.$
Kindly help I have no idea how to solve these type of combinatorial inequalities. Thank you.
The the first, moving terms around gives us $${2n\choose n}\geq 2^n$$ Try proving this by induction.
The second is clearly false, since the RHS is never greater than $1$.
For the third, it's a specific case of the important general inequality $${a \choose b}\leq \frac{1}{b!}a^{b}$$This is true for all $a,b$ and is easily obtained from the definition of the choose function: just increase the values of the terms in the numerator!
$$\frac{1\cdot2\cdot\ldots\cdot (a-1)\cdot a}{(1\cdot\ldots\cdot b)(1\cdot\ldots\cdot (a-b))} =\frac{(a-b+1)\cdot(a-b+2)\cdot\ldots\cdot (a-1)\cdot a}{(1\cdot\ldots\cdot b)} \leq\frac{a\cdot\ldots\cdot a}{(1\cdot\ldots\cdot b)}=\frac{1}{b!}a^b$$
Mostly, cleared by Stella Biderman, I just explain option (a) By induction: Let ${{2k}\choose{k}}\geq 2^k$ holds for all $k\leq n$, then ${{2n+2}\choose{n+1}}=\frac{(2n+2)(2n+1)}{(n+1)^2}{{2n}\choose{n}}\geq \frac{(2n+2)(2n+1)}{(n+1)^2}2^n= \frac{(2n+1)}{(n+1)} 2^{n+1}\geq2^{n+1}$
