Zahlentheorie Induktion n-te Primzahl < 2^2^(n-1)

Neue Frage »

muff-in Auf diesen Beitrag antworten »
Zahlentheorie Induktion n-te Primzahl < 2^2^(n-1)
Hallo,

ich soll mit einem Induktionsbeweis zeigen, dass wenn p_n die n-te Primzahl ist (p_1=2, p_2=3, ...) es kleiner gleich als 2^2^(n-1) ist.

Induktionsanfang:
Fuer p_1 = 2 gilt: 2 =< 2^2^(1-1) = 2

Induktionsschritt von n nach n+1:

p_(n+1) =< 2^2^(n+1-1)
p_(n+1) =< 2^2^n

Wie kann ich jetzt weiter vorgehen? Waere fuer einen kleinen Tipp sehr dankbar smile
HAL 9000 Auf diesen Beitrag antworten »

Grundlage des Induktionsschrittes kann der Euklid-Beweis zur Unendlichkeit der Primzahlmenge sein.
muff-in Auf diesen Beitrag antworten »

Hmm, ich kenne den Euklid-Beweis, aber ich verstehe nicht wie ich ihn hier anwenden kann :/

Edit: koennte ich sagen, p_n+1 = das Produkt aller Primzahlen bis p_n + 1 und das ganze ist nach der Induktionsannahme kleiner als 2^2^(n-1) + 1?

Edit2: Und da 2^2^(n-1) +1 kleiner ist als 2^2^n ist der Induktionsbeweis fertig?

Edit3: Nein moment, wenn p_n+1 das Produkt alle Primzahlen bis p_n +1 ist, ist ja p_n +1 nicht die naechst hoehere Primzahl bzw. sie ist sowieso keine Primzahl.
Also streich alles was in Edit und Edit2 steht, das ergibt keinen Sinn :/
HAL 9000 Auf diesen Beitrag antworten »

Da ist richtiges dabei, aber es ist nicht konsequent zuende gedacht:

ist nach Konstruktion durch keine der Primzahlen teilbar, demnach gilt für den kleinsten Primteiler von auf jeden Fall und somit . Andererseits ist natürlich auch , so dass insgesamt gilt

,

letzteres nach Induktionsvoraussetzung. Der Rest sollte dann nicht mehr so schwer sein.
muff-in Auf diesen Beitrag antworten »

Habs verstanden, dankeschoen. Man muss dann noch nach oben abschaetzen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »