Thread: product of primes

If p are primes and m any integer, show that $\displaystyle \prod_{p\leq m+1} p \leq 4^m$, i was told it can be done by induction but still can't prove it...

Originally Posted by vincent

If p are primes and m any integer, show that $\displaystyle \prod_{p\leq m+1} p \leq 4^m$, i was told it can be done by induction but still can't prove it...

I'll let you verify the base case.

So assume true for all $\displaystyle i\leq m $ and let's use this to show the case for $\displaystyle m+1 $ is true too.

Now, we have that $\displaystyle 2^{m+1}\geq{m+1 \choose \lfloor (m+1)/2 \rfloor} \geq \prod_{\lfloor (m+1)/2 \rfloor \leq p <m+1} p $

By our inductive hypothesis, $\displaystyle \prod_{p\leq\lfloor (m+1)/2\rfloor} p \leq 4^{\lfloor (m+1)/2\rfloor-1} = 2^{2\lfloor (m+1)/2\rfloor-2} $

So $\displaystyle 2^{m+1}\cdot2^{2\lfloor (m+1)/2\rfloor-2}\geq\prod_{p\leq m+1} p $

Notice that $\displaystyle m+1+2\lfloor (m+1)/2\rfloor-2 \leq m+1+2 (m+1)/2-2 = 2m $

Thus $\displaystyle 2^{m+1}\cdot2^{2\lfloor (m+1)/2\rfloor-2}\leq 2^{2m} = 4^m $.

This beautiful theorem and proof are due to Erdös.

wow thanks, it wasn't simple after all!

Originally Posted by vincent

wow thanks, it wasn't simple after all!

Somebody gave you this problem as a challenge? That's mean!