zurück zur Liste

Vollständige Induktion

Das Beweisen der Aussage A(n) durch vollständige Induktion wird in folgende Schritte eingeteilt:

Induktionsanfang A(0)
Wenn der Induktionsanfang abgesichert ist, dann weiß man, daß die Aussage für ein bestimmtes n (meistens nimmt man 0 oder 1) stimmt.

Induktionsvoraussetzung A(n)
ist die eigentliche Aussage, bei der wir für die folgenden Schritte annehmen, dass sie stimmt.

Induktionsbehauptung A(n+1)
müssen wir im nächsten Schritt beweisen, damit wir wissen, dass die Aussage wahr ist.

Induktionsschritt Beweis von A(n+1) durch A(n)
Hier formen wir die Formel A(n+1) so um, dass wir A(n) einsetzen können und eine wahre Aussage entsteht.


Verdeutlichung an einem simplen Beispiel:
Eine natürliche Zahl n heißt geraden wenn n = 2x und ungerade, wenn n = 2x + 1, wobei x ∈ N. Wir beweisen, dass eine natürliche Zahl n entweder gerade oder ungerade sein muss.

Induktionsanfang A(0): 0 ist gerade ∨ 0 ist ungerade, da 2⋅0 = 2 → 0 ist gerade
Induktionsvoraussetzung A(n): n ist gerade ∨ n ist ungerade
Induktionsbehauptung A(n+1): n+1 ist gerade ∨ n+1 ist ungerade
Induktionsschritt 1. Fall: n ist gerade
Es gibt ein x ∈ N, so dass n = 2x. Dann ist n+1 = 2x + 1 → n+1 ist ungerade.
2. Fall: n ist ungerade
Es gibt ein x ∈ N, so dass n = 2x + 1. Dann ist n+1 = (2x + 1) + 1 = 2x + 2 = 2⋅(x+1) → n+1 ist gerade.

Links

Beweis von rev (rev xs) = xs