1
$\begingroup$

As the title says, I can't prove that, no matter what I try. What I've tried so far:

  • induction: seemed the most obvious method, since we already had a lot of tasks with it, but using the esimates mentioned below and using identities of the binomial coefficient didn't get me anywhere

  • managed to show $${n \choose k} \le {\left(\frac{ne}{k}\right)^k}$$ but it didn't quite help me

  • Stirling estimates of n!: I was getting desperate, started googling

Can anyone help me out here? I really don't know how to go on with this task, since I can't even get a start. Thanks!

$\endgroup$
4
$\begingroup$

I can show the stronger statement ${20n \choose 10n}\ge {2n \choose n}^{10}$.

Suppose I have $20n$ books divided into 10 collections.

  • The first one is the number of ways to choose $10n$ books out of my $20n$ books.

  • The second one is the number of ways to choose $n$ books out of my
    $2n$ books for every collection.

The first one is larger, since there if I choose $n$ books out of my
$2n$ books for every collection, I also have $10n$ books chosen out of $20n$.

It remains to be shown that ${2n \choose n} \geq {2n-1 \choose n-1}$, which is true because $${2n \choose n} = \frac{2n}n{2n-1 \choose n-1} = 2{2n-1 \choose n-1}$$

$\endgroup$
  • $\begingroup$ Moral of this answer: Combinatorial proofs are sometimes very powerful. $\endgroup$ – wythagoras Feb 7 '16 at 13:17
  • $\begingroup$ Thanks, that's perfect! I didn't even think of going over a stronger statement first, I guess I would've helplessly tried to show it for hours without your help. Now give me a few minutes to figure out how to mark your answer as correct and the question as done. $\endgroup$ – Tom P. Feb 7 '16 at 13:22
  • $\begingroup$ @wythagoras: You’re welcome. (Nice answer.) $\endgroup$ – Brian M. Scott Feb 7 '16 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.