Zahlentheorie: n-te Primzahl < exp(2^(n-1))?
Hallo, ich soll obige Ungleichung mittels Induktion unter Verwendung von Euklids Beweis zur Unendlichkeit der Primzahlen zeigen. (Also der Beweis mit dem Produkt aller "endlichen" Primzahlen +1 wobei man dann zeigt, dass dieser Term einen Primteiler hat, der nicht in der endlichen Abzählung vorkommt)
If p_n denotes the n-th prime (in ascending order), deduce by induction from Euclid’s proof of Theorem 1.2 that p_n < exp(2^(n−1)).
Ich habe diese Ungleichung auch bewiesen, aber ehrlich gesagt finde ich meinen Beweis sehr unschön, finde aber keine Verbesserung, auch wenn ich schon mehrere Stunden an der Aufgabe sitze. Mein Beweis per Induktion:
Indunktionsvoraussetzung mit n=1 ist klar. Induktionsannahme auch. Zum Induktionsschluss:
Sei p1,..,pn eine Abzählung der ersten n Primzahlen. Es gilt, dass p1p2..pn+1 einen Primteiler q hat, der noch nicht in dieser Abzählung vorkommt (das ist gerade der Beweis von Euklid zur Unendlichkeit). Da p1,..,pn die ersten n Primzahlen repräsentiert, folgt dass p(n+1) die kleine Primzahl ist, die ein Teiler von p1..pn+1 sein kann (insbesondere kann p1..pn+1 selbst prim sein).
Daraus folgt insgesamt p(n+1)<=p1..pn+1
Nun setze ich die Induktionsvoraussetzung ein und fasse zusammen:
p1..pn + 1 < exp(2^0)exp(2^1)...exp(2^(n-1)) + 1 =
exp(2^0 + 2^1 + ... + 2^(n-1)) +1
Nun erkennt man, dass im Exponenten gerade die geometrische Summe mit x=2 von k=0 bis n-1 steht. Diese Summe entspricht (1-2^n)/(1-2). Das lässt sich vereinfachen zu (2^n - 1 )
Insgesamt folgt bis hierhin:
p(n+1) < 1 + exp(2^n - 1)
Nun zu dem Schritt, der mir selbst absolut nicht gefällt.
Ich zeige, dass das weglassen der +1 vorne und der -1 in der e-Funktion sich so wegheben, dass die ungleichheit erhalten bleibt, also explizit zeige ich dass gilt:
1 + exp(2^n - 1) < exp(2^n) (womit ich fertig wäre)
Ich zeige das so:
1 + exp(2^n - 1) = 1 + exp(2^n)/e = 1/e * (e + exp(2^n))
Es folgt also :
1/e * (e + exp(2^n)) < exp(2^n)
Mit Äquivalenzumformung erhalte ich:
e + exp(2^n) < e * exp(2^n)
Da diese Aussage für n=1 gilt und die Ableitung der e-Funktion die e-Funktion selbst ist, also insbesondere die Ableitung monoton steigt, vergrößert sich der Abstand sogar für alle n>1.
Wie gesagt, dieser letzte Teil gefällt mir gar nicht und ich wäre froh, wenn mir jemand eine alternative und schönere Argumentation bereitstellen könnte.
MfG
Und natürlich hat gf alle * geschluckt, zwischen denen kein Leerzeichen war ...
Natürlich heißt es p(n+1) = p1 * p2 * ... * pn +1
und
exp(2^0) * exp(2^1) * ... * exp(2^(n-1)) + 1
p(n+1) <= p1 * p2 * ... * pn +1 ... doppelt vertippt
5 Antworten
Es gilt:
exp(2^n) = e * exp(2^n - 1)
= ((e - 1) + 1) * exp(2^n - 1)
= (e-1) * exp(2^n - 1) + exp(2^n - 1)
> 1 + exp(2^n - 1), weil sowohl (e - 1) als auch exp(2^n - 1) größer als 1 sind.
Hey ich bin zwar nur ein Anfänger aber wollte es aus spass auch mal probieren, kannst du mir sagen, wie du auf p(n+1) = p(1) *... * p(n) + 1 kommst? Wenn man das einfach mal für die ersten beiden Primzahlen versucht bekommt man 2 * 3 + 1 = 7, und 7 ist zwar eine Primzahl, aber 7 ist die 4te Primzahl und nicht die 3te
Kannst du mir vielleicht kurz sagen wie du gezeigt hast dass sich die -1 und die +1 da wegheben? Bis zum "Es folgt also:" verstehe ich es noch, aber wieso folgt das danach? Ich hab vielleicht eine Idee, weiss aber nicht wie gut die ist. Man kann das +1 auch mit exp(2^n-1) abschätzen, weil die Funktion immer wächst und nur für n=0 1 wird, für jedes weitere n ist das also größer als 1. Dann hat man:
exp(2^n-1) + 1 <= exp(2^n-1) + exp(2^n-1) = 2exp(2^n-1)
Jetzt kann man zeigen:
2exp(2^n-1) < exp(2^n) | ln
ln(2) + 2^n -1< 2^n | -2^n
ln(2) - 1 < 0 | +1
ln(2) < 1
Und das ist eine wahre Aussage, aber ich bin mir grad nicht sicher ob ln eine Äquivalenzumformung ist?
Ich würde die Ungleichung 1 + exp(2^n - 1) < exp(2^n) mit der Konvexität der Exponentialfunktion begründen, auch wenn man damit letztlich Anleihen in der Analysis macht.
für n>0.
Ist das im Zusammenhang mit figurierten Zahlen?
Alles Gute.
gar nicht haha
in meiner Originalfrage hab ich geschrieben p(n+1)<=p1 * ... * pn +1
Beim Ergänzen weil die * gefehlt haben hab ich fälschlicherweise dann ein = statt <= geschrieben.