Math Challenge: Prove that the product of all primes less than or equal to n is at most 4^n?

Question

Prove that the product of all primes less than or equal to n is at most 4^n.

This is tough so I will suggest the following strategy: use induction and consider the case where n is even and n is odd separately. One case is very easy, the other is quite tricky and may require strong induction.

Since there is no way I would have solved this on my own, let me offer an additional hint for the way I have seen this done. For the case, when n is odd and of the form 2k+1, you can use strong induction to assume that the product of the primes less than or equal to k+1 is at most 4^(k+1). Hmmm, or her's one more hint, there is a suprising appearance by combinations in the rest of the proof.

By the way, this can be use to prove part of a weak version of the prime number theorem.

Answer 1

i knew this is a classical result
A proof can be found here( theorem 1.6.3):
http://www.maths.lancs.ac.uk/~jameson/chebweb/index.html

p.s. i was the one that i gave thumb down to kyle. Sorry.

Answer 2

a² + b² = c² a + b + c = ab Multiply the two factors by 2 and upload a² + b² on the two factors. a² + b² + 2a + 2b + 2c = a² + 2ab + b² a² + b² + 2a + 2b + 2c = (a + b)² a² + b² + 2c = (a + b)(a + b - 2) c² + 2c = (a + b)(a + b - 2) c(c + 2) = (a + b)(a + b - 2) keep in mind that a + b > c for any triangle. as a result c + 2 > a + b - 2. c + 4 > a + b > c c² + 8c + sixteen > a² + b² + 2ab > c² 4c + 8 > ab > 0 8 > ab - 4?(a² + b²) > -4?(a² + b²) With this constraint, we are able to wager each and all the achieveable values and notice that are the only ones that artwork. it can be a = 3, b = 4 or a = 4, b = 3. of direction, there's a great form of guessing in touch right here. however the suitable factor right here is that ?(a² + b²) is an integer. we will additionally ought to apply fee of replace as element of the failings we will use for the guessing. ----- EDIT: d = a + b From our final equation: (c + d) / (d - 2) = (c + d) / c (c + d)(a million / (d - 2) - a million / c) = 0 a million / (d - 2) = a million/c c = a + b - 2 the only awesome triangle with this high quality is (3, 4, 5).

Answer 3

To Kyle,
I didn't give you a thumb down, but I do see some things I don't understand in your proof.
Look for ****
n even
Base case: n=2
4^2 = 16
2*3 = 6 < 16
**** You don't need 3 since you want primes less than or equal to n = 2.
Assume true for n=k
*****therefore p_1*p_2*. . . *p_r < or = to 4^k
Where r is the number of primes less than n.
Show true for n=k+2
4^(k+2)
= 16*4^k
If, by the assumption, the product of primes is less than 4^k, then it is also less than 16*4^k.
**** You might have introduced a new prime in the product.
so that you have to prove:
p_1* . . . *p_r*p_(r+1)< or = 4^(k + 1)

I don't think this statement is true. For each new n you're multiplying by 4 or 16 or 64, . . ., but that's opposed to multiplying by a prime which could be whopping big. Have to think. Back later.
If I'm wrong: [e-mail]

Answer 4

its very simple. i will carry forward what rrswc left for us....

we have to prove that (this is the one for odd number of primes)
p_1* . . . *p_r*p_(r+1) < = 4^(k + 1)

therefore

p1 * .......p(r + 1) < = 4*4^k
p1*....*pr <= 4*4^k / p(r + 1)

therefore

p1*.....pr < = 4/p(r + 1) 4^k

but we know that p1*........pr is always less or equal to 4^k
therefore it follows that
p1*.......pr is also less than 4/p(r + 1) 4^k
this is because there is only 2 and 3 primes that will give a fraction greater than 1. all other primes if divide 4 will give a fraction lesser than 1.......I hope u get this

rest all is easy

Answer 5

n even
Base case: n=2
4^2 = 16
2 < 16

Assume true for n=k
Show true for n=k+2
4^(k+2)
= 16*4^k
If, by the assumption, the product of primes is less than 4^k, then it is also less than 16*4^k.


n odd
Base case n = 1
4^1 = 4
No primes less the 1 so the product is essentially 0.
0 < 4

Assume true for n=k
Show true for n=2k+1
4^(2k + 1)
= 4*4^2k = 4 * (4^k)^2
By the assumption, the product of primes is less than 4^k
4^k < (4^k)^2 < 4*(4^k)^2
So the product of primes is less than 4*(4^k)^2.

QED


edit:
I really don't think it's this easy. Someone prove me wrong (for instance, whoever gave me a thumbs down).

edit:
rrsvvc, I corrected the base case error. Thanks. I will take a look at the other stuff you said.

edit:
Lobosito, thanks for confessing. I'm not mad - I just think people who give a thumbs down should have a better answer.

Answer 6

a prime number can only be divided by itself or 1. anyway I am still coming up with 2-1 and giving consideration I am also getting 1^4 is still =1
which can bring me back to =0
so n =1/4 thats the only I can see uless again unless it 1.1
1.2.
1.3
9+9=18=19 9=1=10=1