Induktionsbeweis f. Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man zeige:
Fuer alle [mm] $n\in\IN$ [/mm] gilt: Die Anzahl der Primzahlen [mm] $\leq [/mm] n$ ist
nicht groesser als [mm] $\frac{n}{3} [/mm] + 2$. |
Hallo liebes Forum,
Ich verzweifle mittlerweile an o.g. Aufgabe und hoffe, jemand kann mir hier helfen.
Zeigen will ich die Behauptung per (Abschnitts-)induktion ueber $n$. Mein Problem ist, daß ich im Induktionsschritt beim Übergang von $n$ auf $n+1$ stets bei der Abschaetzung zuviel hinzu addiere.
Mein Beweis bislang:
Fuer alle [mm] $n\in\IN$ [/mm] sei im folgenden $P(n)$ die Anzahl der Primzahlen [mm] $\leq [/mm] n$.
Die Faelle [mm] $n\in\{1, ..., 4\}$ [/mm] sind klar, und ich erspare mir etwas Schreibarbeit, da ich die Induktion ab $n=5$ beginnen will (da ab $n=5$ die Zahl $n-1$ keine Primzahl ist, was im Beweis benutzt wird).
Fuer $n [mm] \geq [/mm] 5$ zeige ich per Abschnittsinduktion die staerkere Behauptung, dass
$P(n) [mm] \leq \frac{n-1}{3} [/mm] + 2$.
Die Behauptung folgt dann.
I.A.: Fuer $n = 5$ sind die Primzahlen [mm] $\leq [/mm] n$ die Zahlen 2, 3 und 5,
also $P(n) = 3 [mm] \leq \frac{4}{3} [/mm] + 2 = [mm] \frac{n-1}{3} [/mm] + 2$.
I.V.: Sei [mm] $n\in\IN_{\geq 5}$ [/mm] so, dass fuer alle $n' [mm] \leq [/mm] n$ gilt: $P(n') [mm] \leq \frac{n'-1}{3} [/mm] + 2$.
I.S.: Fall 1: $n+1$ ist keine Primzahl. Dann gilt:
$P(n+1) = P(n) [mm] \leq_{I.V.} \frac{n-1}{3} [/mm] + 2 < [mm] \frac{n}{3} [/mm] + 2$.
Fall 2: $n+1$ ist Primzahl. Dann ist $n+1$ ungerade (da sonst durch 2
teilbar). Folglich ist $n$ gerade und keine Primzahl. Also gilt:
$P(n+1) = P(n - 1) + 1 [mm] \leq_{I.V.} (\frac{n-2}{3} [/mm] + 2) + 1 = ...$
- Tja, und hier knallt's. Es ist bereits [mm] $\frac{n-2}{3} [/mm] + 3 [mm] \geq \frac{n}{3} [/mm] + 2$ :-(
Kann jemand helfen?
Fuer einen Tipp waere ich super dankbar!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:32 Do 26.04.2007 | | Autor: | komduck |
Hallo,
wir streichen die Vielfachen von ein paar primzahlen und zählen was übrig bleibt.
z.B p=2 wir bilden Gruppen von 2 Zahlen. Jede zweite
ist gerade dann haben wir die Abschäzung < [mm] \bruch{1}{2} [/mm] * n + 1
wenn wir bei 6 Zahlen die durch 2 oder durch 3 teilbaren Zahlen streichen
bleiben 2 übrig. Bei 30 Zahlen bei denen wir vielfache von 2,3,5
streichen bleiben 9 übrig. Das wäre dann [mm] \bruch{3}{10} [/mm] * n + konst.
Die Konstante entsteht weil wir in der ersten Gruppe die Zahlen nicht
streichen. Nun muß man eine Induktion daraus machen. Es bietet
sich ein Induktionschrit von n nach n+k an. k ist die Gruppengröße.
Der Induktionsanfang ist dann n=0,1,2... k-1
mfg komduck
|
|
|
|
