Another algebra problem about prime and induction

In summary, to prove by induction that the n^th prime is less than 2^{2^n}, we can assume it is correct for all n \leq k and then compare p_{k+1} with p_1p_2...p_k+1. If p_{k+1} is larger than this suggested number, it can be proven to have no prime divisors, leading to a contradiction. The use of the Euclidean algorithm may be helpful in this proof.
  • #1
kntsy
82
0

Homework Statement



prove by induction that the [itex]n^{\text th}[/itex] prime is less than [itex]2^{2^{\text n}}[/itex]

Homework Equations


hint:assume it is correct for all [itex]n \leq k[/itex], and then compare [itex]p_{k+1}[/itex] with [itex]p_{1}p_{2}...p_{k}+1[/itex]

The Attempt at a Solution


is [itex]p_{k+1}[/itex] smaller/greater than [itex]p_{1}p_{2}...p_{k}+1[/itex] so that i can extend the use of inequality?
I attempt to use euclidean algorithm but do not know where to use.
Thank you.
 
Physics news on Phys.org
  • #2
If [tex]p_{k+1}[/tex] is larger than the suggested number, you should be able to prove that it has no prime divisors which is a contradiction
 

Related to Another algebra problem about prime and induction

1. What is the problem statement?

The problem states that we need to prove that for any prime number p, the sum of the first p consecutive integers is divisible by p.

2. How do we approach this problem?

We can use mathematical induction to prove this statement. First, we will prove that the statement is true for p = 2, then we will assume that the statement is true for some arbitrary prime number k and use that assumption to prove that it is also true for k+1.

3. Can you provide an example to illustrate the problem?

Sure. Let's take the case of p = 5. The first 5 consecutive integers are 1, 2, 3, 4, and 5. The sum of these integers is 15, which is divisible by 5. Therefore, our statement holds true for p = 5.

4. How does mathematical induction work?

Mathematical induction is a proof technique that involves proving a statement for a base case (usually the smallest possible value) and then assuming the statement is true for an arbitrary value and using that assumption to prove that it is also true for the next value.

5. Can you explain how the proof for this problem works?

Sure. We first prove that the statement holds true for p = 2, which is the base case. Then, we assume that the statement is true for an arbitrary prime number k. This means that the sum of the first k consecutive integers is divisible by k. Using this assumption, we can prove that the statement is also true for k+1, which completes our proof by mathematical induction.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
13
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
2K
Replies
2
Views
800
Back
Top