Rekursion und Induktion

Rekursion

Eine Definition oder Funktion ruft sich selbst auf — mit kleineren Eingaben.

Klassische Beispiele

Fakultät:     n! = n · (n-1)!,  0! = 1
Fibonacci:    F(n) = F(n-1) + F(n-2),  F(0)=0, F(1)=1
Türme von Hanoi:  H(n) = 2·H(n-1) + 1,  H(1) = 1

Vollständige Induktion — der Beweistool

Um für alle n zu beweisen: zeige Basis (n = 1) und Schritt (n → n + 1).

Beispiel — Summenformel

Behauptung: 1 + 2 + ... + n = n(n+1)/2

Basis n=1:  1 = 1·2/2 = 1   ✓

Schritt n → n+1:
Annahme:  1 + 2 + ... + n = n(n+1)/2
Z.z.:     1 + 2 + ... + (n+1) = (n+1)(n+2)/2

Beweis:
1 + 2 + ... + n + (n+1)
= n(n+1)/2 + (n+1)               (Annahme)
= (n+1) · (n/2 + 1)
= (n+1) · (n+2)/2                ✓

⛓️

Domino-BildInduktion = Dominos. Du beweist: erstes fällt (Basis) UND wenn n-tes fällt, fällt auch (n+1)-tes (Schritt). Dann fallen alle.