Question

let \[p_{n}\] denote the n-th prime in ascending order. Use induction to prove the following proposition.

\[p_{n} \le 2^{2^{n-1}}\] let \[p_{n}\] denote the n-th prime in ascending order. Use induction to prove the following proposition.

\[p_{n} \le 2^{2^{n-1}}\] @Mathematics

Answer 1

how do we know
\[p_1 \le 2^{2^{1-1}}\]
i'm not totally sure what p_1 means

Answer 2

p_1=2

Answer 3

the first prime number

Answer 4

oh

Answer 5

lol

Answer 6

p_1 = 2
p_2 = 3
p_3 = 5 etc

Answer 7

\[2 \le 2 \text{ is true!}\]

Answer 8

right

Answer 9

so let's assume it is true for some integer k now
so we have
\[p_k \le 2^{2^{k-1}} \]

Answer 10

now we need to show it is true for n=k+1

Answer 11

\[p_{k+1} \le 2^{2^{k}}\]

Answer 12

I just can't figure out how to go from the inductive hypothesis to that

Answer 13

\[2^{2^{(k+1)-1}}=2^{2^{k-1} \cdot 2^{1}}=2^{2^{k-1}} \cdot 2^2 \ge p_k \cdot 2^2=2^2p_k\]

Answer 14

thinking ...

Answer 15

so we just showed

\[2^2 p_k \le 2^{2^{(k+1-1)}}\]

\[p_k \le \frac{2^{2^{k+1-1}}}{2^2}\]


and now i'm stuck

Answer 16

\[2^2^k=2^{2^{k-1}\cdot 2}=2^{2^{k-1}\cdot2^{2^{k-1}\]

Answer 17

not displaying nice for me

Answer 18

\[2^{2^k}=2^{{2^{k-1}} \cdot 2}=2^{2^{k-1}}\cdot2^{2^{k-1}}\]

Answer 19

yes

Answer 20

\[2^{2^k}=2^{{2^{k-1}} \cdot 2}=2^{2^{k-1}}\cdot2^{2^{k-2}2}=2^{2^{k-1}}\cdot2^{2^{k-2}}\cdot2^{2^{k-2}}=\cdots\]

Answer 21

\[=\prod_{n=0}^{k}2^{2^n}\]

Answer 22

what is that?

Answer 23

product

Answer 24

oh so it's like the sigma notation

Answer 25

\[\text{ example of that notation \in use }\prod_{i=1}^{4}i=1 \cdot 2 \cdot 3 \cdot 4\]

Answer 26

k-1 not k

Answer 27

yes except you multiply

Answer 28

so how does that help in this case?

Answer 29

\[=\prod_{n=0}^{k-1}2^{2^n}\]

Answer 30

\[p_1 \cdot p_2 \cdot \cdot \cdot p_k \le =\prod_{n=0}^{k-1}2^{2^n}\]

Answer 31

up to k-1

Answer 32

i put two many equal signs
i copy what you have and didn't change it

Answer 33

no ...it is k

Answer 34

too*

Answer 35

I'm getting lost

Answer 36

I think @Zarkon means:\[p_1 \cdot p_2 \cdot \cdot \cdot p_{k-1} \le =\prod_{n=0}^{k-1}2^{2^n}\]

Answer 37

on yeah he does

Answer 38

\[p_1 \cdot p_2 \cdot \cdot \cdot p_k\geq p_{k+1}\]

Answer 39

I was wrong...it is up to k

Answer 40

lol

Answer 41

:-)

Answer 42

zarkon is wrong?

Answer 43

is that the product of those primes?

Answer 44

\[p_1 \cdot p_2 \cdot \cdot \cdot p_{k} \le \prod_{n=0}^{k-1}2^{2^n}\]

Answer 45

the Universe will soon end --- how can Zarkon make a MISHTAKE???
;-)

Answer 46

its horrifying

Answer 47

zarkon use to be alien looking
i wonder if that something to with it

Answer 48

I've gotten very confused lol

Answer 49

\[p_1 \le 2^{2^{1-1}}\]
right?

Answer 50

\[p_2 \le 2^{2^{2-1}}\]
right?

Answer 51

\[p_{k+1}\le p_1 \cdot p_2 \cdot \cdot \cdot p_{k} \le \prod_{n=0}^{k-1}2^{2^n}=2^{2^k}\]

Answer 52

\[p_3 \le 2^{2^{3-1}}\]

Answer 53

yes since \[3\le32\] I think

Answer 54

...
\[p_{k-3} \le 2^{2^{(k-3)-1}}\]
\[p_{k-2} \le 2^{2^{(k-2)-1}}\]
\[p_{k-1} \le 2^{2^{(k-1)-1}}\]
\[p_{k} \le 2^{2^{k-1}}\]

Answer 55

so since all those inequalities are true then
\[p_1 \cdot p_2 \cdot \cdot \cdot p_{k} \le \prod_{n=0}^{k-1}2^{2^n} \]

Answer 56

ok hold on, we started with \[p_{n} \le 2^{2^{n-1}}\]
proved it for when n=2
then assumed \[p_{k} \le 2^{2^{k-1}}\] was true
and needef to get to
\[p_{k+1} \le 2^{2^{k}}\] what happens after this?

Answer 57

what comes after

\[p_{k+1} \le 2^{2^{k}}\]
we are done
you can put something after it like
for all integers n>=1 such and such is

Answer 58

is true*

Answer 59

how do we get to that though

Answer 60

somehow we find that\[2^{2^{n-1}}\] is equal to that product somehow

Answer 61

I think you can prove it like this:\[2^{2^k}=2^{2^{k-1+1}}=2^{2^{k-1}.2}=(2^{2^{k-1}})^2=p_k^2\]therefore:\[p_{k+1}=p_k^2\]and we have assumed that:\[p_k<=2^{2^{k-1}}\]therefore:\[p_k^2<=(2^{2^{k-1}})^2\]\[p_k^2<=2^{2^k}\]therefore:\[p_{k+1}<=2^{2^k}\]

Answer 62

how do yo know that it is equal to (p_k)^2 in the first line
shouldn't it be less than?

Answer 63

yes, sorry, my mistake in the 1st line.

Answer 64

\[2^{2^k}=2^{2^{k-1+1}}=2^{2^{k-1}.2}=(2^{2^{k-1}})^2>=p_k^2\]

Answer 65

then in the second line how do you know that they are equal?

Answer 66

all we know is that they are both \[\le 2^{2^{n-1}}\] right?

Answer 67

\[p_{k+1}>=p_k^2\]

Answer 68

hmmm - needs more thought...

Answer 69

I don't think you can necessarily say that it is larger in that case

Answer 70

yes - I agree - it needs more thought - maybe Zarkon was giving a clue as to how to solve this - I will need to think over what he was trying to say.

Answer 71

I am thoroughly confused as to what I should be doing

Answer 72

\[2^{2^k}=2^{{2^{k-1}} \cdot 2}=2^{2^{k-1}}\cdot2^{2^{k-2}2}=2^{2^{k-1}}\cdot2^{2^{k-2}}\cdot2^{2^{k-2}}=\cdots\]

Answer 73

do you understand this?

Answer 74

yes I understand that

Answer 75

do you understand this?

Answer 76

ok so do you understand this
\[2^{2^k}=2^{2^{k-1}} \cdot 2^{2^{k-2}} \cdot 2^{2^{k-3}} \cdots \cdot 2^{2^0}\]

Answer 77

why is that a 0?

Answer 78

do you understand this?

Answer 79

\[2^{2^2}=2^{2^{2-1} \cdot 2} =2^{2^{2-1}} \cdot 2^{2^{2-2}2}=2^{2^{2-1}} \cdot 2^{2^0} \cdot 2^2\]
\[=2^{2} \cdot 2^{2} \cdot 2^{0}\]
what do you think about this?

Answer 80

do you understand this?

Answer 81

no wait i don't like my second line (i mean its right)
but look at the first line

Answer 82

hmm I think I get that

Answer 83

do you understand this?

Answer 84

\[2^{2^2}=2^{2^{2-1} \cdot 2} =2^{2^{2-1}} \cdot 2^{2^{2-2}2}=2^{2^{2-1}} \cdot 2^{2^0} \cdot 2^2 \]
\[=2^{2^1} \cdot 2^{2^0} \cdot 2^{2^1}=2^{2^1} \cdot 2^{2^1} \cdot 2^{2^0}\]

Answer 85

do you understand this?

Answer 86

i'm just trying to show you the end pattern

Answer 87

eventually your k will go to zero so you need to stop right?

Answer 88

do you understand this?

Answer 89

yes

Answer 90

ok

Answer 91

do you understand this?

Answer 92

so that should piece in all the puzzle pieces now

Answer 93

do you understand this?

Answer 94

\[p_{k+1}\le p_1 \cdot p_2 \cdot \cdot \cdot p_{k} \le \prod_{n=0}^{k-1}2^{2^n}=2^{2^k}\]
thats how zarkon got this

Answer 95

where did that list of products of primes come from?

Answer 96

do you understand this?

Answer 97

hey brandon ignore the extra posts
it is reposting stuff
weird

Answer 98

I'm not seeing extra posts here