Beweise mit Rekursion und Induktion

Wenn man mit rekursiven Definitionen und Algorithmen arbeitet, ist es wichtig, beweisen zu können, dass sie tatsächlich das Richtige tun. Die natürliche Methode dafür ist die mathematische Induktion. Induktion ähnelt der Rekursion: man beginnt mit einem Basisfall und zeigt dann, dass wenn die Aussage für einen Schritt gilt, sie auch für den nächsten gilt.

Beispiel 1: Fakultät

Wir wollen beweisen, dass die rekursive Definition der Fakultät der üblichen Produktformel entspricht:

$$ \large n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \quad n \geq 1 $$

Basis

Für $ \large n = 1 $:

$$ \large 1! = 1 \quad \text{gilt} $$

Induktionsschritt

Angenommen, die Aussage gilt für ein bestimmtes $ \large n $, das heißt

$$ \large n! = 1 \cdot 2 \cdot \ldots \cdot n $$

Dann gilt für $ \large n+1 $:

$$ \large (n+1)! = (n+1) \cdot n! $$

Nach der Induktionsannahme können wir $ \large n! $ ersetzen:

$$ \large (n+1)! = (n+1) \cdot (1 \cdot 2 \cdot \ldots \cdot n) $$

Damit erhalten wir genau das Produkt bis $ \large n+1 $. Die Aussage gilt also für alle $ \large n $.

Beispiel 2: Fibonacci

Die Fibonacci-Folge ist definiert durch

$$ \large F_{0} = 0, \quad F_{1} = 1, \quad F_{n} = F_{n-1} + F_{n-2} \;\; (n \geq 2) $$

Eine bekannte Formel besagt, dass die Summe der ersten $ \large n $ Fibonacci-Zahlen ist:

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

Basis

Für $ \large n = 0 $ haben wir links die Summe $ \large F_{0} = 0 $.

Rechts steht $ \large F_{2} - 1 = 1 - 1 = 0 $.

Beide Seiten ergeben dasselbe, also gilt die Aussage im Basisfall.

Induktionsschritt

Angenommen, die Aussage gilt für ein bestimmtes $ \large n $:

$$ \large F_{0} + F_{1} + \ldots + F_{n} = F_{n+2} - 1 $$

Wir zeigen es für $ \large n+1 $:

$$ \large F_{0} + F_{1} + \ldots + F_{n} + F_{n+1} $$

$$ \large = (F_{n+2} - 1) + F_{n+1} \quad \text{(nach Induktionsannahme)} $$

$$ \large = F_{n+1} + F_{n+2} - 1 $$

$$ \large = F_{n+3} - 1 $$

Damit gilt die Aussage auch für $ \large n+1 $. Nach Induktion gilt die Formel für alle $ \large n $.

Beispiel 3: Korrektheit eines rekursiven Algorithmus

Zuvor sahen wir den Algorithmus, der das Maximum in einer Liste findet:

function max(list):
    if list has length 1:
        return list[0]            // Basis
    else:
        m = max(rest of list)     // rekursiver Schritt
        return the larger of list[0] and m

Wir wollen beweisen, dass der Algorithmus immer das größte Element in der Liste zurückgibt.

Basis

Hat die Liste die Länge 1, gibt der Algorithmus das einzige Element zurück. Das ist korrekt, da ein einzelnes Element selbstverständlich das Maximum ist.

Induktionsschritt

Angenommen, der Algorithmus funktioniert korrekt für alle Listen der Länge $ \large n $. Wir müssen zeigen, dass er auch für eine Liste der Länge $ \large n+1 $ funktioniert.

Sei die Liste $ \large [x_0, x_1, \ldots, x_n] $. Der Algorithmus ruft sich auf der Teilliste $ \large [x_1, \ldots, x_n] $ auf, die die Länge $ \large n $ hat. Nach der Induktionsannahme liefert dieser Aufruf korrekt das Maximum der Teilliste.

Schließlich vergleicht der Algorithmus dieses Maximum mit dem ersten Element $ \large x_0 $. Damit wird das größte aller Elemente $ \large x_0, x_1, \ldots, x_n $ zurückgegeben, also das Maximum der ganzen Liste.

Schlussfolgerung

Nach Induktion liefert der Algorithmus max immer das größte Element einer Liste, unabhängig von ihrer Länge.

Zusammenfassung

Induktion ist die natürliche Methode, um die Korrektheit rekursiver Definitionen zu beweisen. Man zeigt, dass der Basisfall gilt, und dass, wenn die Aussage für einen Schritt gilt, sie auch für den nächsten gilt. Damit ist die gesamte unendliche Konstruktion abgedeckt. Dies macht die Induktion zu einem grundlegenden Werkzeug in der Arbeit mit Rekursion.