Primzahlen/Induktion

03.04.2012, 01:01

öPus

Primzahlen/Induktion

$\begin{eqnarray*} p_n \end{eqnarray*}$ bezeichnet die n-te Primzahl
Zeige: $\begin{eqnarray*} p_n \leq {2^2}^{n-1} \end{eqnarray*}$
soll heißen 2 hoch 2 hoch n-1

I.Anfang:
n=1 $\begin{eqnarray*} p_1=2 \leq 2 \end{eqnarray*}$
I.Annahme n=k gilts $\begin{eqnarray*} p_k \leq {2^2}^{k-1} \end{eqnarray*}$
I.S k -> k+1
ZZ: $\begin{eqnarray*} p_{k+1} \leq {2^2}^{k+1-1} \end{eqnarray*}$

Danke für jegliche Hinweise!

03.04.2012, 01:24

Integralos

Auf diesen Beitrag antworten »

Ich denke ich würde mit dem binären Logarithmus argumentieren.

03.04.2012, 01:26

öPus

Auf diesen Beitrag antworten »

Könntest du die Antwort etwas ausführen?
Ich komme damit nicht weiter,

LG

03.04.2012, 08:07

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von öPus
Könntest du die Antwort etwas ausführen?
Ich komme damit nicht weiter,
LG

Mit dieser Antwort könnte ich auch nichts anfangen... geschockt

Ich würde mich hier doch eher an Euklids Beweis für die Unendlichkeit der Primzahlmenge halten, um die richtige Idee zu haben...

03.04.2012, 08:56

öPus

Auf diesen Beitrag antworten »

okay
Betrachte $\begin{eqnarray*} t=1+p_1*..*p_k (\geq 2) \end{eqnarray*}$
Sei $\begin{eqnarray*} p_0 :=min\{m \in \mathbb Z: m > 1,m|n\} \end{eqnarray*}$
Dann ist $\begin{eqnarray*} p_0 \end{eqnarray*}$ eine Primzahl die nicht in $\begin{eqnarray*} t \end{eqnarray*}$ vorkommt (beweis analgo zu Euklids Beweis für die Unendlichkeit der Primzahlmenge)

Nach I.Annahme
$\begin{eqnarray*} t=1+p_1*..*p_k \leq 1+ \sum\limits_{i=1}^n {2^2}^{i-1} \end{eqnarray*}$

schaue ich mir getrennt mal an: $\begin{eqnarray*} \sum\limits_{i=1}^n 2^{i-1}=\sum\limits_{i=1}^{n-1} 2^{i}=\frac{1-2^n}{1-2}=2^n-1 \end{eqnarray*}$

$\begin{eqnarray*} t \leq 1+ \sum\limits_{i=1}^n {2^2}^{i-1}=1+2^{2^n-1} \end{eqnarray*}$

welche ist aber die k+1-primzahl ?
Ich muss jetzt die k+1-Primzahel nach $\begin{eqnarray*} 2^{2^n} \end{eqnarray*}$ abschätzen.

03.04.2012, 09:42

Mystic

Auf diesen Beitrag antworten »

Ja, du bist offensichtlich jetzt auf "dem richtigen Weg", aber rein formal ist so unglaublich viel falsch, dass man dir nur den dringenden Rat geben kann, vor dem Abschicken deine Postings nochmals genau durchzulesen... Ich nenne hier mal beispielhaft einige Fehler, damit du siehst, dass ich nicht übertrieben habe...

Zitat:

Original von öPus
okay
Betrachte $\begin{eqnarray*} t=1+p_1*..*p_k (\geq 2) \end{eqnarray*}$
Sei $\begin{eqnarray*} p_0 :=min\{m \in \mathbb Z: m > 1,m|n\} \end{eqnarray*}$

Offensichlich meintest du in Wahrheit $\begin{eqnarray*} p_0 :=min\{m \in \mathbb Z: m > 1,m|t\} \end{eqnarray*}$ , denn eine Variable n gibt es zu diesem Zeitpunkt gar nicht...

Zitat:

Original von öPus
Nach I.Annahme
$\begin{eqnarray*} t=1+p_1*..*p_k \leq 1+ \sum\limits_{i=1}^n {2^2}^{i-1} \end{eqnarray*}$

Anscheinend meintest du hier

$\begin{eqnarray*} t=1+p_1*..*p_k \leq 1+ \prod\limits_{i=1}^k {2^2}^{i-1} \end{eqnarray*}$

d.h., du hast (wieder einmal!) Summen mit Produkten verwechselt und auch hier taucht ein n wie aus dem Nichts auf, das hier nichts zu suchen hat...

Zitat:

Original von öPus
schaue ich mir getrennt mal an: $\begin{eqnarray*} \sum\limits_{i=1}^n 2^{i-1}=\sum\limits_{i=1}^{n-1} 2^{i}=\frac{1-2^n}{1-2}=2^n-1 \end{eqnarray*}$

Und in dieser Art geht es auch hier weiter... Richtig wäre natürlich

$\begin{eqnarray*} \sum\limits_{i=1}^k 2^{i-1}=\sum\limits_{i=0}^{k-1} 2^{i}=\frac{2^k-1}{2-1}=2^k-1 \end{eqnarray*}$

Tja, und natürlich ist auch das hier falsch

Zitat:

Original von öPus
$\begin{eqnarray*} t \leq 1+ \sum\limits_{i=1}^n {2^2}^{i-1}=1+2^{2^n-1} \end{eqnarray*}$

und muss richtig heißen

$\begin{eqnarray*} p_{k+1} \le t \leq 1+ \prod\limits_{i=1}^k {2^2}^{i-1}=1+2^{2^k-1} \end{eqnarray*}$

Zitat:

Original von öPus
welche ist aber die k+1-primzahl ?
Ich muss jetzt die k+1-Primzahel nach $\begin{eqnarray*} 2^{2^n} \end{eqnarray*}$ abschätzen.

Ja, das musst du, und das sollte nun auch leicht sein...Allerdings bringst du auch zum Schluß noch die Variablen k und n durcheinander... Eine gewisse Konsequenz kann man dir also hierin nicht absprechen... Big Laugh

03.04.2012, 10:15

öPus

Auf diesen Beitrag antworten »

Verstehe deinen Ärger Augenzwinkern

Gelobe besserung.

$\begin{eqnarray*} p_{k+1} \le t \leq 1+ \prod\limits_{i=1}^k {2^2}^{i-1}=1+2^{2^k-1} \end{eqnarray*}$

Ist die Primzahl $\begin{eqnarray*} p_{k+1} \end{eqnarray*}$ das $\begin{eqnarray*} p_0 \end{eqnarray*}$ ?? Oder woher weißt du dass $\begin{eqnarray*} p_{k+1} \le t \end{eqnarray*}$ ist?

$\begin{eqnarray*} 1+2^{2^k-1} \le 2^{2^k-1}+2^{2^k-1}=2*2^{2^k-1}=2^{2^k} \end{eqnarray*}$

03.04.2012, 10:27

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von öPus
Ist die Primzahl $\begin{eqnarray*} p_{k+1} \end{eqnarray*}$ das $\begin{eqnarray*} p_0 \end{eqnarray*}$ ?? Oder woher weißt du dass $\begin{eqnarray*} p_{k+1} \le t \end{eqnarray*}$ ist?

Mit deinen Bezeichnungen (auch wenn sie unpassend sind, denn dein $\begin{eqnarray*} p_0 \end{eqnarray*}$ hängt ja von t ab!) gilt

$\begin{eqnarray*} p_{k+1}<=p_0<=t \end{eqnarray*}$

03.04.2012, 10:35

öPus

Auf diesen Beitrag antworten »

Ich geh dir sicher auf die Nerven aber-
Ich verstehe noch immer eine sache nicht, wieso gilt :
$\begin{eqnarray*} p_{k+1} \leq p_0 \end{eqnarray*}$
Also aus welcher Definition nehme ich das?

03.04.2012, 10:43

Mystic

Auf diesen Beitrag antworten »

Naja, die Primzahl $\begin{eqnarray*} p_0 \end{eqnarray*}$ ist ja Teiler von $\begin{eqnarray*} t=1+p_1p_2 \ldots p_k \end{eqnarray*}$ und kommt somit unter den ersten k Primzahlen $\begin{eqnarray*} p_1,p_2, \ldots ,p_k \end{eqnarray*}$ nicht vor...

03.04.2012, 10:49

öPus

Auf diesen Beitrag antworten »

ja das $\begin{eqnarray*} p_0 \leq t \end{eqnarray*}$ ist ist klar.
Aber was hat hier $\begin{eqnarray*} p_{k+1} \end{eqnarray*}$ damit zu tun?

Ich weiß nur $\begin{eqnarray*} p_{k+1} \end{eqnarray*}$ kommt ebenfalls nicht in den ersten k Primzahlen $\begin{eqnarray*} p_1,p_2, \ldots ,p_k \end{eqnarray*}$ vor

03.04.2012, 10:55

Mystic

Auf diesen Beitrag antworten »

Hm, denk dir mal die Primzahlfolge in aufsteigender Reihenfolge hingeschrieben:

$\begin{eqnarray*} p_1,p_2,\ldots,p_k,p_{k+1}, \ldots \end{eqnarray*}$

Wir wissen, dass unser $\begin{eqnarray*} p_0 \end{eqnarray*}$ unter den ersten k Primzahlen nicht vorkommt (hast du diesen wichtigen Schritt von oben akzeptiert?) und daher rechts von $\begin{eqnarray*} p_k \end{eqnarray*}$ liegt ... Dann muss doch auch gelten $\begin{eqnarray*} p_{k+1} \le p_0 \end{eqnarray*}$ , oder etwa nicht?

03.04.2012, 11:16

öPus

Auf diesen Beitrag antworten »

Ah, jetzt hab ich es .

Ich dank dir.
LG

Neue Frage »

Antworten »

Primzahlen/Induktion

Verwandte Themen