Prove that highest power of 2 in \(2n!\) is strictly greater than the highest power of 2 in \(n!^2\).

This is kind of a corollary from another fundamental theorem. If you know that theorem, then this problem is nothing.

And this one is original to the best of my knowledge. I got it from the theorem.

## Comments

Sort by:

TopNewestWhich theorem are u talking about ? that 2nCn is even? If thats the case we see :

Let us partition a set of 2n objects into 2 equal groups.We can definitely do such(e.g,a(1),a(2),...,a(n) in one group and others in the other.)----------------------- Let the number of ways of doing this be x(n).-------------------------- By definition x(n) is an integer. ----------------------From each of these partitions we get 2 unique ""n-combination of 2n objects"". -----------------------Conversely every ""n-combination of 2n objects"" paired with its conterpart gives one unique partition. -------------------So we form a 1-2 bijection between these 2 sets(the first of partitions and second of combinations). ----------------thus, by bijection principle ----------------------2nCn=2*x(n)=even. – Chandrachur Banerjee · 1 year, 8 months ago

Log in to reply

– Vishnu C · 1 year, 8 months ago

Nice! The logical version of what I posted. I've always found it hard to imagine scenarios in combinatorics where you get the results of what you want through the implications of the scenario. That's why I try to do things through mathematical calculation first and why I find combinatorics hard. But I always like reading solutions that are made in the way you did it : )Log in to reply

## Thanks bro. And the best part is that your and my solution combined gives us another theorem:

## Number of ways to partition a set of 2n objects into equal groups is (2N-1)C(N).

## Though i am begining to sense a bijection to prove this but really this is not a trivial result!!!!!!!!!!!

– Chandrachur Banerjee · 1 year, 8 months agoLog in to reply

Log in to reply

– Chandrachur Banerjee · 1 year, 8 months ago

Hmmm. I think according to my definition of partition above it means separating any n objects from a set of 2n objects from the others.So it is not hard to see that the #of partitions is (2nCn)/2. ------------------ the stars and bars(i know them as balls and walls,anyway) will give u parition for a particular SEQUENCE of 2n objects.Moreover it gives u all paritions(in english sense) of such a sequence into 2 parts(not necessarily equal parts).--------------------------------Now can u spot the difference?----------I think trying to obtain the #of partitions(as i have defined) from balls and walls is somewhat complicated. Nevertheless it can give u another combinatorial identity.Log in to reply

– Vishnu C · 1 year, 8 months ago

Yeah, sorry. I skipped over the equal parts part.Log in to reply

– Chandrachur Banerjee · 1 year, 8 months ago

Not only the equal part i think balls and walls works for only a particular sequence of objects,is'nt it? I mean S={1,2,3,4,5} We can never obtain the partition {2,3,4},{1,5} by balls and walls. Am i right???Log in to reply

identicalthings into a given number ofdistinctgroups. – Vishnu C · 1 year, 8 months agoLog in to reply

– Chandrachur Banerjee · 1 year, 8 months ago

there is another elegant way by counting the number of ways of reaching the point (2n,n) in the pascal triangle this gives (try and see by breaking the path at the nth line)------------ 2nCn=---- sumi=0 to n [(nCi)^{2}] -------------if n is odd the (nCi)^{2} and (nCn-i)^{2} can be grouped and so sum is even.--------------- if n is even all other terms except nC(n/2) are grouped and their sum becomes even.--------------- For nC(n/2), simply , we use induction hypothesis!!!!(strong form of mathematical induction)Log in to reply

– Chandrachur Banerjee · 1 year, 8 months ago

Is this solution Okay? Its sort of extention of the pascal triangle proofLog in to reply

Hint:

The theorem is this: \(\left(^{2n} _n\right)\) is always even. From this theorem, this corollary is pretty easy to arrive at. But can you prove this theorem? – Vishnu C · 1 year, 8 months ago

Log in to reply

\((^{n}_r)=(^{n-1}_r)+(^{n-1}_{r-1})\)

Put n=2n, r=n and you get:

\((^{2n}_n)=(^{2n-1}_{n-1})+(^{2n-1}_n)\quad and\quad (^{2n-1}_n)=(^{2n-1}_{n-1})\) – Vishnu C · 1 year, 8 months ago

Log in to reply

Hint:\( \lfloor \frac{ 2n}{2^l} \rfloor \geq 2 \lfloor \frac{n}{2^l} \rfloor \).Hint:There exists \(k\) such that \( n < 2^k \leq 2n \). – Calvin Lin Staff · 1 year, 8 months agoLog in to reply

I just got back from the exams and I've got many problems that I'm going to be posting here. It was really fun to solve all those challenging problems. And thanks to @Otto Bretscher 's problem, one more of those, I got the answer to a sub question pretty quickly. It was pretty much the same question : D – Vishnu C · 1 year, 8 months ago

Log in to reply

Yay to solving hard problems via the "done before" method! – Calvin Lin Staff · 1 year, 8 months ago

Log in to reply