Vollständige Induktion

[Jester]

adonis schrieb:

Ja, das ist mir schon klar.

aber der Beweis soll doch zeigen, dass $6^{n+2}+7^{2n+1}$
durch 43 teilbar ist. Dann kann ich doch nicht genau damit begründen.
Das 6fache davon durch 43 teilbar ist, weil $6^{n+2}+7^{2n+1}$ durch 43 teilbar ist.

Naja, im Prinzip schon. Du nimmst ja an, dass a_n durch 43 teilbar ist und zeigst dann, dass daraus folgt dass a_n+1 auch durch 43 teilbar ist. Zusammen mit dem Induktionsanfang beweist das genau die gewünschte Aussage.

Versuch nochmal das ganz in Ruhe aufzuschreiben und mach Dir jeweils klar, was Induktionsvoraussetzung ist, also als wahr angenommen wird und was jeweils genau zu beweisen ist.

[adonis]

Wenn der Umstand das $6^{n+2}+7^{2n+1}$ wieder da steht
der Beweis ist, dann ist klar dass, das 6Fache davon auch durch 43 teilbar
ist.
Also ich setzte das ganze auf n+1 und mit ein paar Umformungstricks
kommt man hoffentlich wieder auf den Anfang. Und das ist dann der Beweis?

Wie sieht denn ein Beweis aus wo, das nicht funktioniert?
wir hatten dahmals im LK Mathe einen, ich finde den nur nicht.
Da ging es um Primzahlen. Man sah der Formel schon an, das irgendwann die
Zahl ein vielfaches von sich selbst wird. Die formel galt nur für ein paar
Zahlen aber nicht für alle.Kennt einer vielleicht dieses Beispiel?
Es war ne recht einfache Formel.

Ich muss mal einen sehen, wo es nicht für alle gilt.

[adonis]

Acho und noch eine Frage.
Ich sehe die Beweise immer nur mit Formel aus einer expliziten
Bildungsvorschrift. Funktioniert der Beweis auch mit Rekursiven?

[Tobiking2]

adonis schrieb:

Also ich setzte das ganze auf n+1 und mit ein paar Umformungstricks kommt man hoffentlich wieder auf den Anfang. Und das ist dann der Beweis?

Genau, man zeigt im Induktionsschritt A(n)->A(n+1).

adonis schrieb:

Wie sieht denn ein Beweis aus wo, das nicht funktioniert?

Du kommst mit dem Verfahren nicht zwangsläufig darauf das es nicht funktioniert. Du wirst es halt einfach nicht beweisen können. Der einfachste Beweis dafür das etwas nicht gilt ist immer noch ein Gegenbeispiel.

adonis schrieb:

Funktioniert der Beweis auch mit Rekursiven?

Ja, du musst nur beachten das dadurch der Induktionsanfang länger wird je mehr Vorergebnisse genutzt werden. Nehmen wir a(n) = a(n-1) + a(n-2) mit a(0) und a(1) unwichtig, dann fängt der Induktionsanfang natürlich mit n=2 an, da n-2 sonst unter 0 wäre. Die Behauptung gilt dann natürlich auch nur für n>2.

[adonis]

Tobiking2 schrieb:

Du kommst mit dem Verfahren nicht zwangsläufig darauf das es nicht funktioniert. Du wirst es halt einfach nicht beweisen können.

Wenn ich es nicht beweisen kann, muss sich das ja in meiner Formel zeigen.
Würde für mich heißen, troz aller Umformtricks, komme ich nicht wieder
beim Anfang an.

Tobiking2 schrieb:

Der einfachste Beweis dafür das etwas nicht gilt ist immer noch ein Gegenbeispiel.

Ein Gegenbeispiel zu finden kann ja unter umständen auch recht umständlich
und langwierig sein.

Jester schrieb:

Naja, im Prinzip schon. Du nimmst ja an, dass a_n durch 43 teilbar ist und zeigst dann, dass daraus folgt dass a_n+1 auch durch 43 teilbar ist. Zusammen mit dem Induktionsanfang beweist das genau die gewünschte Aussage.

OK, ja ich zeige für $n_{0}$ dass es wahr ist, ja ich nehme an dass es auch für $a_{n}$, und ich will zeigen dass es für
$a_{n+1}$ auch gilt.

Nun kam ich auf das Ergebnis $6(6^{n+2}+7^{2n+1})+43*7^{2n+1}$.

Klar, wenn ich annehme das meine Annahme richtig ist, ist $a_{n+1}$
auch richtig. Aber ich will doch nichts annehmen, sondern beweisen.

Nehme ich Beweis zu wörtlich? Kann ein beweis denn widerlegt werden, oder
ist ein durchgeführter beweis unerschüttlerich?

[Tobiking2]

Du musst dir das vielleicht einfach mal etwas formaler anschauen. Du zeigst für Aussage A zwei Sachen:
1. A(0) gilt
2. A(n)->A(n+1) | Sprich: Falls Aussage A für n gilt, so gilt sie auch für n+1. Uns interessiert also nur der Fall das A(n) gilt, und können insbesondere auf diese Tatsache zurückgreifen.

Nun kannst du das einfach zusammensetzen
A(0) gilt wegen 1.
A(1) weil A(0)->A(1), denn n=0 ist ein n für das die Aussage gilt.
A(2) weil A(1)->A(2), s.o.
...

Das ist analog zu der Definition der natürlichen Zahlen, weswegen man zu dem Schluss kommt A(n) gilt für alle n der natürlichen Zahlen.

[JFB]

Dieses Prinzip lässt sich auch ein wenig verallgemeinern, auf jede Struktur, die durch gegebene Basisobjekte und Konstruktoren, die aus Objekten weitere Objekte erzeugen, besteht. Das führt einen dann zur strukturellen Induktion.
Bei den natürlichen Zahlen ist die 0 das Basisobjekt und der einzige Konstruktor ist succ: IN -> IN, n -> n + 1.

[otze]

adonis schrieb:

Wenn ich es nicht beweisen kann, muss sich das ja in meiner Formel zeigen.
Würde für mich heißen, troz aller Umformtricks, komme ich nicht wieder
beim Anfang an.

Die Menge aller Umformungstricks ist unendlich. Bis du die alle durch hast, dauert es eine Weile ;). natürlich gibt es einfache Fällen in denen du zeigen kannst, dass es nicht gilt. Aber im Allgemeinen hast du verloren.

[adonis]

Ok, also ich habe jetzt einen Beweis x gemacht.
Jetzt kommt einer auf die Idee und schreibt ein Programm,
der jede Zahl ab 1 einsetzt und prüft ob, das Ergebnis stimmt.

30 Jahre später kommt er zu mir, und sagt "Also bis zu einer
Quadrillionen ging es, aber bei einer Quadrillionenundeins ging es nicht
mehr"

Hat der recht, oder kann ich ihm sagen, er liegt flasch, weil ich hab es
ja bewiesen?

[JFB]

Du hast das Prinzip eines mathematischen Beweises nicht verstanden.
Wenn ein Gegenbeispiel zu der Aussage existiert, die du gemacht hast, dann ist sie falsch und damit auch dein "Beweis".
Ist dein Beweis richtig, ist sein Programm falsch oder der Computer hat sich verrechnet.
Bewiesene Aussagen sind Tautologien, man kann sie per definitionem nicht widerlegen.

[adonis]

mich hatte nur das verwirrt:

Du kommst mit dem Verfahren nicht zwangsläufig darauf das es nicht funktioniert. Du wirst es halt einfach nicht beweisen können. Der einfachste Beweis dafür das etwas nicht gilt ist immer noch ein Gegenbeispiel.

Der Umstand dass$6^{n+2}+7^{2n+1}$ in
$6(6^{n+2}+7^{2n+1})+43*7^{2n+1}$ enthalten ist, ist der Beweis.
a->b
Die Behaupthung war ja das es durch 43 teilbar ist, das sehe ich in diesem
Schritt und kann daraus folgern, dass es auch für n+1 gilt. ende.

Heißt für mich im umkehrschluss aber auch. wenn die Formel nicht für
alle gelten sollte, sondern nur für eine bestimmte Menge. dann kann ich
nicht zu diesem schluss kommen.

[JFB]

Naja, wenn's falsch ist, kannst du's auch nicht beweisen. Mehr ist in dem Zitat nicht gemeint.
Wenn's nämlich falsch ist, findet man ein Gegenbeispiel. Etwa bei einer Quadrillion und eins.