what can be some methods to prove and explain $$n<{2n \choose n}$$ is true , Iam having diffuculty is proving and explain it though it seems easy . please can anyone help me with my small problem on sets?
Asked
Active
Viewed 53 times
1
-
Hint , induction !! – alkabary May 27 '15 at 07:52
-
Well sir its under sets and combinations... the question is about true and false ...the question is like this Let n=10^{10^{1000000000000}} .It then holds that n<{2n \choose n} <2^{2n}<n^{2n} ......... I actually know that is is true but i cant fully understand the n<{2n \choose n} part and how to explain it – avi nand May 27 '15 at 08:04
2 Answers
4
The right hand $\;\binom{2n}n\;$ is the number of sets with $\;n\;$ elements that a set with $\;2n\;$ elements has. Suppose we take the set $\;X=\{1,2,...,n,n+1,...,2n\}\;$ for simplicity, and then we have
$$\{1,2,...,n\}\,,\,\,\{1,2,..,n-1,n+1\}\;,\;\;\{1,2,...,n-1,n+2\}\,,\;\ldots,\{1,2,..,n-1,2n\}$$
The above are already $\;n+1\;$ subsets with $\;n\;$ elements in $\;X\;$ , and from here you get a combinatorial proof of what you want.
Timbuc
- 34,191
3
Let $A$ and $B$ be two disjoint sets with $n$ elements, and $C=A\cup B$.
Consider subsets of $C$ of the form $\lbrace a \rbrace \cup (B \setminus \lbrace b \rbrace)$ for $(a,b)\in A\times B$. There are $n^2$ such subsets, so $\binom{2n}{n} \geq n^2$.
Ewan Delanoy
- 61,600