0
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @ Stella Biderman Thank you very much! $\endgroup$ Commented Jan 12, 2017 at 10:24
0
$\begingroup$

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}$

$\endgroup$

You must log in to answer this question.

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