Es ist mir peinlich: Vollständige Induktion: Kontradiktion im Schritt -> ?

[gastacc]

Hallo,
wenn ich für alle n >= 4 beweisen will, dass A(n) ilt.
Dann prüfe ich für 4. Läuft.
Dann prüfe ich für n -> n+1.
Und dann bekomme ich im Induktionsschritt raus :
x = 2*(wurzel(x))+1

Oder sowas.
Kann ich daraus jetzt folgern, dass nicht(A(n)) für alle n gilt? Edith:
Ich meinte natürlich, dass es mindestens ein n gibt, sodass (nicht(A(n))?

Bitte erklärt mir, warum und wieso etc.

[Nomschta]

x kann schon mal nicht sein weil es A(n) ist. außerdem willst du ja immer irgendwas der form A(n) = B(n) beweisen. poste mal die original aufgabe.

[gastacc]

x kann schon mal nicht sein weil es A(n) ist. außerdem willst du ja immer irgendwas der form A(n) = B(n) beweisen. poste mal die original aufgabe.

Ja, aber ich will halt nicht die Lösung der Aufgabe, sondern verstehen, ob das geht und wenn ja, warum (oder nicht).

zz:
Es gelte für alle n Element N, n<=4: Es existiert ein p, p prim, so dass gilt (ich kann übrigens schon sagen, dass das nicht gilt. ich will nur wissen, ob ich das so zeigen kann):
n*n = p-1


So.
Basisfall:
4*4 = p-1 | +1
17 = p
Haken dran.

n -> n+1

n² + 2n +1 = p-1 | IV einsetzen
(p-1) + 2(wurzel (p-1)) +1 = p-1 | +1
p + 2(wurzel (p-1)) + 1 = p
Kontradiktion, Widerspruch zu Annahme, dass p element N, p prim.
Es folgt (nicht(A)), da Satz vom ausgeschlossenene Dritten.

Edith: Ich habe eine Theorie, muss dazu aber noch was überprüfen, was ich wohl erst heute Abend oder so machen kann.
Dennoch wäre ich weiter für Input dankbar.

[wildtollwut]

Für einen Widerspruch braucht man keine Induktion. Es genügt zu zeigen, dass es für ein n nicht gilt und schon gilt es nicht für alle

[gastacc]

Für einen Widerspruch braucht man keine Induktion. Es genügt zu zeigen, dass es für ein n nicht gilt und schon gilt es nicht für alle

Das weiß ich. Ich will aber wissen, ob das so wie ich mir das vorstelle, generell geht oder nicht. Genau deswegen frage ich, die Antwort auf die Aufgabe hatte ich schon bevor ich überhaupt mit Induktion rangegangen bin.

[wildtollwut]

"Kann ich daraus jetzt folgern, dass nicht(A(n)) für alle n gilt?."

Nein, es geht so nicht. Dein Induktionsanfang (n=4) steht im Gegensatz zu dem was du beweisen willst. Mit Induktion schließt du von einem Schritt auf den nächsten, betrachtest nen 'n+1'-ten Schritt unabhängig von einem konkreten 'n' und schaust, ob er (z.B. durch Umformung) deiner Behauptung entspricht. Wenn er das nicht tut, kannst du nichts weiter aussagen als dass deine Behauptung falsch ist.

Deine Behauptung ist: Es gelte A(n) für alle n. Du hast also gezeigt, dass es ein n gibt, für das A(n) nicht gilt (die "Umkehrung").

Wenn du zeigen wolltest, dass deine Behauptung A(n) für alle n _nicht_ gilt, müsste dein Anfang anders aussehen, z.B. n = 5, aber mit n = 6 passt es dann schon wieder nicht.

[gastacc]

Nein, es geht so nicht. Dein Induktionsanfang (n=4) steht im Gegensatz zu dem was du beweisen willst. Mit Induktion schließt du von einem Schritt auf den nächsten, betrachtest nen 'n+1'-ten Schritt unabhängig von einem konkreten 'n' und schaust, ob er (z.B. durch Umformung) deiner Behauptung entspricht. Wenn er das nicht tut, kannst du nichts weiter aussagen als dass deine Behauptung falsch ist.

Deine Behauptung ist: Es gelte A(n) für alle n. Du hast also gezeigt, dass es ein n gibt, für das A(n) nicht gilt (die "Umkehrung").

Wenn du zeigen wolltest, dass deine Behauptung A(n) für alle n _nicht_ gilt, müsste dein Anfang anders aussehen, z.B. n = 5, aber mit n = 6 passt es dann schon wieder nicht.

Also kann ich damit beweisen, dass es mindestens ein n gibt, so dass (nicht(A(n))?
Das ist genau das, was ich wissen will! Ist das wirklich so möglich und kann man das auch sonst so benutzen? Also ist das "logisch einwandfrei"?
Das würde mir schonmal sehr weiterhelfen.

Außerdem: Das wollte ich auch Hab grade gesehen, dass ich Scheiße geschrieben habe oben /o\.
Tut mir sehr Leid, damit hätte ich die ganze Diskussion verkürzen können. :/
Das Ding ist, dass ich aber immer noch nicht ganz zufrieden bin. Ich verstehe Deine Erklärung, habe auch meinen Fehler im Induktionsbeweis gefunden (mehr dazu unten), aber da könnte trotzdem noch was rausspringen:

Und zwar steht in der Aufgabenstellung nirgends, dass das p gleich sein soll, also habe wir p_1 und p_2. Das war mein Fehler im Beweis.

Aber: Damit hätte ich wieder ein Problem, denn dann KÖNNTE der Induktionsschritt passen.
Ich müsste jetzt noch zeigen, dass es kein p_2, p_1 gibt, so dass p_2 = p_1 + 2(wurzel ((p_1)-1)) + 1.
Geht das irgendwie oder habe ich wieder einen Fehler in meiner Überlegung, und es ist einfach nicht möglich, das zu zeigen, wie ich das will.

[wildtollwut]

Meines Erachtens geht da einiges durcheinander Durch deinen "Beweis" steige ich nicht durch, vermutlich auch, weil du (wie geschrieben) das gleiche p verwendest, obwohl p beliebig ist. Wenn du ein n findest, das einen Widerspruch erzeugt bist du fertig und hast den Widerspruch 'bewiesen'.

Generell zeigt man z.B. Teilbarkeit durch 2 per Induktion indem man soweit umformt bis man 2 ausfaktorisieren ("ausklammern") kann oder eben nicht. In deinem Fall könnte man sich vorstellen, von der Teilbarkeit von n^2 auf die Teilbarkeit von (n + 1)^2 zu schließen und damit zu folgern daß... Im Prinzip ist dein Ansatz der erste Schritt dafür. Allerdings wird das nicht funktionieren, denn das verwandte vierte Problem Landaus (https://en.wikipedia.org/wiki/Landau's_problems) ist seit über hundert Jahren ungelöst

Als einfache(re) Übung für deinen Ansatz: Zeige per Induktion, daß für alle n \in N n^2+n eine gerade Zahl ist (= durch zwei teilbar ist).