Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Feb 16, 2014

(2n choose n) is never a perfect power

Source: Cute problem sent by Sudeep Kanath

Problem: Prove that (2n choose n) is never a perfect power

Update ( 21 June 2014 ):
Solution: Posted by Sandeep, Dinesh Krithivasan and Vishal Khatri in comments.


12 comments:

  1. There is always atleast one prime between n and 2n. (Bertrand's postulate). These primes occur only once in factorization of 2nCn. So, 2nCn can never be a perfect power.

    ReplyDelete
  2. Direct consequence of Bertrand's postulate. After canceling out one of the n! in the denominator, the numerator will be the product of (n+1)(n+2)... up to 2n. By Bertrand's postulate, there is a prime in this group of numbers, say p. Then, (2n choose n) is divisible by p but not any powers of p and so cannot be a perfect power.

    This is probably nuking a mosquito though - there ought to be a simple proof.

    ReplyDelete
    Replies
    1. Most proofs of Bertrand's postulate (at least the ones on wiki) start by studying the prime factorization of 2nCn. So, this reasoning is likely to be circular.

      Delete
  3. It will always be some power of 2 multiplied with some odd number. So, it can't be a perfect power.

    ReplyDelete
    Replies
    1. Just saw your comment on this..I agree, I have written it wrong... just have to work out again to what i wanted to write. Thanks for bringing it to notice :-)

      Delete
    2. I meant to say that it will always be a power of 2 multiplied with some odd numbers of which at least one would a prime. And after reading the comments above and below, I noticed that the prime would be lying in n to 2n.
      So, I wrote it wrong, Thank you for pointing out :-)

      Delete
  4. There is always a prime between n and 2n. Hence!

    ReplyDelete
  5. Bertrand's postulate it is !!!
    http://en.wikipedia.org/wiki/Bertrand%27s_postulate

    ReplyDelete