(Vollständige) Induktion

Question

Allgemeiner kann auch für eine beliebige Menge M eine Aussage A(m) für alle m∈M
bewiesen werden, indem man eine Funktion f : M → ℕ angibt und zeigt, dass für
jedes m ∈ M aus der Annahme „A(m) ist falsch“ folgt, dass es ein m' ∈ M mit
f (m') < f (m) gibt, sodass auch A(m') falsch ist. Wir sprechen hier auch von
Induktion über f.


Kann mir jemand ein konkretes Beispiel geben oder erklären, wie das genau funktioniert?

Answer 1

Hallo ACK, deine Frage ist schon 20 Tage alt. Aber so lange habe ich gebraucht, bis ich Zeit für dich hatte. :-)  Mag sein, dass dich die Antwort nicht mehr interessiert. Aber mich.

Ich setze voraus, dass du das Beweisverfahren der vollständigen Induktion kennst.

Dieses Beweisverfahren hier ist ein sehr schöner Induktionsbeweis. Diesmal umgekehrt wie sonst, nämlich als Widerspruchsbeweis. Du möchtest gerne ein Beispiel. Hier ist eines. Und zwar das klassische Beispiel für Induktionsbeweise.

Die Behauptung ist: 1 + 2 + 3 + ... + n = n * (n+1) / 2

Da wir diesmal einen Widerspruchsbeweis führen, ist jetzt unsere Behauptung:

1 + 2 + 3 + ... + n ≠ n * (n+1) / 2

Wir versuchen zu beweisen, dass für n-1 gilt:

1 + 2 + 3 + ... + (n – 1) ≠ (n-1) * n / 2

Also:

1 + 2 + 3 + ... + n ≠ n * (n+1) / 2    |   -n

Den Rest schafft der Leser vermutlich selber.

Comments

Wichtige Anmerkung: Dieses Induktionsverfahren hat meines Erachtens einen Fehler. Wenn f(m) = 0, dann gibt es kein m‘, so dass f(m‘) < f(m). Also klappt der Widerspruchsbeweis nie, und das Verfahren taugt nichts.