product of primes

**vincent** · Apr 10th 2010, 08:35 PM

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

**chiph588@** · Apr 10th 2010, 09:31 PM

Originally Posted by vincent

If p are primes and m any integer, show that $\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 $i\leq m$ and let's use this to show the case for $m+1$ is true too.

Now, we have that $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, $\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 $2^{m+1}\cdot2^{2\lfloor (m+1)/2\rfloor-2}\geq\prod_{p\leq m+1} p$

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

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

**Bruno J.** · Apr 10th 2010, 10:04 PM

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

**vincent** · Apr 12th 2010, 06:05 PM

wow thanks, it wasn't simple after all!

**Bruno J.** · Apr 13th 2010, 10:24 AM

Originally Posted by vincent

wow thanks, it wasn't simple after all!

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

Thread: product of primes

LinkBack

Thread Tools

Display

product of primes

Similar Math Help Forum Discussions

Group Order a product of primes

Prove that (product of primes between n and 2n) > 2^n

product of primes II

Product of Primes

Product of primes using induction

Search Tags