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

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.

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.

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.

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 :-)

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 :-)

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.

ReplyDeleteThanks

DeleteDirect 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.

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

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.

DeleteThanks.

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

ReplyDelete?? Wrong solution!

DeleteJust 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 :-)

DeleteI 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.

DeleteSo, I wrote it wrong, Thank you for pointing out :-)

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

ReplyDeleteThanks

DeleteBertrand's postulate it is !!!

ReplyDeletehttp://en.wikipedia.org/wiki/Bertrand%27s_postulate