Hello,

I don't particularly want this problem to be solved for me but I was hoping that you could give me some pointers on how to start it off.

How can it be proved that there is always a prime number that lies between n and 2n (where n is a member of the natural numbers, and n is greater than or equal to 2).

AlexB.

Alex,

I know the formula n Choose r = (n!) / r!(n-r)!
so I would expect 2n Choose n to be (2n)! / (n!)²

Sorry... I was trying to give as little away as possible because you asked to do it yourself!

Quite right - 2n Choose n is (2n)! / (n!)² . Now you have to look at how many times each prime p divides the numerator (2n)! and how many times they divide the denominator (n!)² . Then the number of times p divides 2n Choose n will be the difference between these two numbers.

So do this for p in the range 2n/3 < p< = n and hopefully you'll get 0.

For example let n=6 then 12 Choose 6 = 924.
Pick a prime in the range 4 < p< = 6 - ie. p=5. And see that 5 does not divide 924.

Now why? The numerator is 12! = 12x11x10x9x... and so 5 divides the 5 factor and the 10 factor both exactly once. So there are 2 factors of 5 in the numerator. The denominator is 5!² and we see that 5 divides this exactly two times. So overall there is no factor of 5 left.

Does this make the (2) bit clearer??

For the (1) bit --- can you see that all the primes between a and b divide b Choose a?? Again do it like above - count how many times a prime divides the numerator and the denominator.

After this we are trying to work out something to do with the product of the primes less than n. The above trick shows you that all the primes between n/2 and n divide n Choose n/2. So the product of the primes between n/2 and n divide n Choose n/2. So, in particular we know that the product of the primes between n/2 and n is not any more than n Choose n/2.

Can you show that n Choose n/2 is not more than 2ⁿ ??

Can you now see how to do the (1) bit?

I hope that that gives you some more pointers... again let me know if you want more.

AlexB.

Alex,

This is a lot more complicated than I imagined!!!

The extra pointers have helped, but after trying a few things out, I have some more questions.

I understand what you said about the (2) bit, and it helped. Firstly, why does p have to be between n and 2n/3? And secondly, related to this, what about when n=2 and n=3; there would not be any prime, p between n and 2n/3.
If say n=2, 4 Choose 2 = (4x3x2x1) / (2x1)² = 6. For p between 2n and n (i.e. p=3) p DOES divide 2n choose n. This is confusing me more now.

I have been advised to look at factors of (n+1) in the numerator and denominator of 2n choose n, so I was hoping you might be able to throw some light onto this option.
I can see that (2n)! will have one factor of (n+1) in it - but it may well have more. How can I show this?
Also, I have no idea how to show that (n!)² has a factor of (n+1) in it. So could you show me how to prove this.


Anthony

Alex,

For the 1 bit, I am even more confused.
Please can you give me some more help.
It would be more than welcome.

Anthony.

Don't worry that you are finding it a little difficult - my history at the top should show you that it really isn't an easy thing to do!!

---------------

I'll concentrate on the second bit for now - the 2/3n < p< = n not dividing 2n Choose n.

You are right that there is a problem for p=2 --- I forgot to say that n> 2. But there isn't a problem after this... So I'll write it out again:

If n> 2 then we want to show that primes p such that 2n/3 < p < = n do not divide 2n Choose n.

The reason why it is 2n/3 is because it isn't true anymore if I change this!

Okay now let's look at what 2n Choose n looks like. It is (2n)! / (n!)² . But this can also be written as 2n x (2n-1) x (2n-2) x ... x (n+1) / 1 x 2 x ... x n. Is this okay??

So I want to show that for p in the range I said above it divides the numerator the same number of times as it divides the denominator.

Well, how many times does it divide the denominator? The multiples of p are p,2p,3p,4p,... So how many of these occur in the denominator.

Because p< = n it is certainly true that p is in the denominator.

Is 2p in the denominator? Remember that 2n/3 < p... So 2p > 4n/3...

So 2p is not in the denominator and so none of the higher ones are in either. Thus, p divides the denominator EXACTLY once. Is this okay??

Now onto the numerator. We have to find which numbers p,2p,3p,... are in the numerator.

Is p in the numerator? No - it's too small.
Is 2p in the numerator? Yes. Can you see why??
Is 3p in the numerator? No - it's too large. Can you see why??

So only 2p is in the numerator. So as p> 2 there is EXACTLY one factor of p in the numerator.

Hence, overall these two will cancel and p can not divide 2n Choose n for p in the range 2n/3 < p < = n.

Now you might be able to see the reason for the 2n/3 condition. It was needed to make sure that 3p was not in the numerator. So if we had changed it then we would have got more factors of p in the numerator than in the denominator. Is this okay??

I hope this was even clearer than before! Let me know how you get on with this...

--------------

Now for the first bit. The problem was:

Show that the product of the primes less than n is less than 4ⁿ .

I told you to look at 2n Choose n, again. I'll get back to you later on in the day.

AlexB.

Right. Consider the number 2n Choose n. It is of the form 2n x (2n-1) x ... x (n+1) / 1 x 2 x ... x n - just like before. Can you see that if p is a prime number such that n < p < = 2n then p divides 2n Choose n??

As before we look at the multiples of p: p,2p,3p,...

Well - do any of them occur in the denominator? No because p is larger than n. Is this okay??

Do any of them occur in the numerator? Yes.

Does p occur in the numerator? Yes - because n < p < = 2n.
Does 2p occur in the numerator? No - because p> n... so 2p> 2n...

So for n < p < = 2n we now know that p divides 2n Choose n. And as each such prime divides, the product of them must also divide. So:

If I set P(n) to be the product of the primes that are in the range n < p < = 2n. Just in case of problems I'll let it be 1 if there are no such primes.

For example. P(5)=7, P(10)=11 x 13 x 17 x 19, etc...

Then P(n) divides 2n Choose n. And because of the way divisibility works we must have that P(n) is less than or equal to 2n Choose n. Is this okay??

But P(n) only gives us the 'top half' of the primes less than 2n. How can we include the ones between 2 and n? Well the previous bit [section (2)] shows us that we can NOT hope that they divide 2n Choose n. So we are going to have to do something different. And the trick is as follows:

The primes less than or equal to 2n are:
(a) the primes in the range n < p < = 2n
(b) the primes in the range n/2 < p < = n
(c) the primes in the range n/4 < p < = n/2
etc...

So combining all of these we see that the product of the primes £< = 2n is less than or equal to

(2n Choose n) x (n Choose n/2) x (n/2 Choose n/4) x ...

Don't worry about the problems of these possibly not having integer terms. You get round this by carefully rounding the terms.

So now the question is to try and simplify the above product.

Can you show that 2n Choose n is less than 4ⁿ ?? If not - what do you get if you use the binomial theorem to expand (1+1)²ⁿ ?

Hopefully one of the terms (the middle one) will be 2n Choose n. Do you see that all the terms in the expansion are positive and so the expansion is certainly bigger than 2n Choose n??

So 2n Choose n < (1+1)²ⁿ = 2²ⁿ = 4ⁿ .

Is this okay so far??

So what is (2n Choose n) x (n Choose n/2) x (n/2 Choose n/4) x ...??

It is less than:

4ⁿ x 4^n/2 x 4^n/4 x...

Okay??

Can you see that this is less than 4²ⁿ ??

So the product of primes less than 2n (which is what we were working out is less than 4²ⁿ ). So if you just half everything then you get what we wanted!

I hope that is okay!! Let me know if not...

AlexB.

PS: Can you let me know where in school you are (A-level I'm assuming) and how you came across this problem. I'm sorry this might look extremely complicated - one thing all mathematicians eventually learn is that most proofs are fairly complicated even if the idea behind them is quite neat!

Alex,

I've been busy lately so I've only just read your reply.

I get the explanation of the 2 bit, thanks for that.

I haven't had a good look at the rest yet so I'll get back to you when I have.

You were right about me doing A-Levels, for which I'm doing A-Level Applied and A-Level Pure Maths.
I came across the problem when my maths class was asked to find out as much as we could about it.