Induktion: die Dominokette

Ein direkter Beweis gelingt, wenn Sie das ganze Argument auf einmal sehen, wie die Fallunterscheidung in der vorigen Lektion. Er bricht in dem Moment zusammen, in dem die Behauptung drei Punkte enthält. Die Summe von eins bis n hat unendlich viele Instanzen, und keine Seite fasst unendlich viele Zeilen. Und so weiter zu schreiben ist kein Beweis, sondern ein Versprechen, dass es irgendwo einen gibt. Die Induktion löst dieses Versprechen mit endlich vielen Worten ein, und sie hat genau zwei Teile.

claim: for every integer n >= 1,

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

n = 1    1            = 1
n = 2    1 + 2        = 3
n = 3    1 + 2 + 3    = 6
n = 4    1+2+3+4      = 10

base case:      n = 1
inductive step: if it holds for n, it holds for n + 1

Der Basisfall ist die Behauptung mit dem kleinsten zulässigen n, von Hand geprüft. Der Induktionsschritt ist eine Wenn-dann-Aussage: unter der Annahme, dass die Behauptung für ein n gilt, zeige, dass sie dann auch für n plus eins gilt. Beachten Sie, was der Schritt nicht tut. Er sagt nichts darüber, ob die Behauptung für irgendein bestimmtes n gilt. Er ist eine Maschine, die eine Wahrheit bei n in eine Wahrheit bei n plus eins verwandelt, und eine Maschine ohne Eingabe liefert keine Ausgabe. Zusammen ergeben beide Teile alles: der Basisfall startet die Kette, und der Schritt trägt sie für immer weiter.

Hier ist, warum beide Hälften nötig sind, und es lohnt sich, je einen echten Fehlschlag zu sehen, statt es einfach zu glauben. Zuerst der Schritt allein. Wenn Sie annehmen, n plus eins sei gleich n, und auf beiden Seiten eins addieren, erhalten Sie n plus zwei gleich n plus eins, also dieselbe Behauptung mit n ersetzt durch n plus eins. Der Schritt ist völlig gültig. Die Behauptung bleibt trotzdem für jedes n falsch, weil kein erster Stein je gefallen ist.

claim A: for every integer n >= 1,  n + 1 = n

step: n + 1 = n
      (n + 1) + 1 = n + 1          holds

base: n = 1  ->  1 + 1 = 1       false

step = T, base = F

Nun der andere Fehlschlag: ein Basisfall ohne funktionierenden Schritt. Das Polynom unten wurde tatsächlich für alle n für prim gehalten, und bei n gleich eins besteht es. Es überlebt sogar bis n gleich 39. Bei n gleich 40 zerfällt es, und dort endet die Kette. Das ist der Fehlschlag, der Sie im Code findet: hundert Array-Indizes verhalten sich brav, und Index null oder der letzte lagen nie im getesteten Bereich.

claim B: for every integer n >= 1,  n^2 + n + 41  is prime

base: n = 1   ->  43              prime
step: n = 39  ->  1601            prime
      n = 40  ->  1681 = 41 * 41   composite

base = true, step broken at 39 -> 40

Manchmal genügt die Annahme nur für den Fall n nicht. Wenn Sie eine Zahl in zwei kleinere Faktoren zerlegen, müssen Sie wissen, dass beide in Primzahlen zerfallen, und beide sind kleiner als n statt gleich n minus eins. Die starke Induktion nimmt die Behauptung für jeden Wert unterhalb von n an, was mehr Material gibt und trotzdem keine stärkere Anforderung ist: alles, was sich mit starker Induktion beweisen lässt, lässt sich auch mit gewöhnlicher beweisen, nur mit unhandlicherer Formulierung. In der Praxis ist der Unterschied wichtig, weil die starke Induktion die richtige Form für Teile und herrsche ist.

claim: every integer n >= 2 factors into primes

base:        n = 2 is prime
strong step: assume the claim for every k, 2 <= k < n

  n prime    ->  done
  n = a * b  ->  a < n and b < n
                 T(k) holds for 2 <= k < n

T(n) = T(a) and T(b)

Damit sind wir beim Grund, warum diese Lektion in einem Programmierkurs steht. Mergesort ruft sich zweimal auf Hälften auf und mischt die Ergebnisse. Studierende akzeptieren meist, dass es funktioniert, weil sie gesehen haben, dass es funktioniert. Der eigentliche Grund ist der Induktionsbeweis. Basisfall: ein Feld der Länge null oder eins ist sortiert, und die Funktion gibt es zurück. Schritt: angenommen, Mergesort liefert für jede kürzere Eingabe als n ein sortiertes Feld. Dann kommen beide Hälften sortiert zurück, und das Mischen zweier sortierter Felder ist sortiert. Per Induktion ist die Funktion für Felder jeder Länge korrekt. Das ist keine Verzierung: der Basisfall unten ist genau die Bedingung im if, und der Schritt ist genau die Korrektheit von merge.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

# T(1) = c
# T(n) = 2 * T(n / 2) + O(n)
# depth = log2(n), work per level = O(n) -> O(n log n)Rekursives Mergesort. Der Basisfall der Induktion ist die erste Zeile, der Induktionsschritt ist das Mischen.

Dieselbe Form liefert die Laufzeit, und hierher kommt O(log n) endlich, statt eine Form zu sein, die man aus einem Diagramm auswendig lernt. Auf jeder Rekursionsebene ist die Gesamtarbeit n, und die Zahl der Ebenen ist, wie oft man n halbieren kann, bis ein Element übrig bleibt, also der Logarithmus von n zur Basis 2. Arbeit pro Ebene mal Zahl der Ebenen ergibt n log n. Die binäre Suche ist der schärfere Fall: sie leistet konstante Arbeit pro Ebene und wirft die Hälfte der Daten weg, also ist der Aufwand genau die Zahl der Halbierungen. Eine Verdopplung der Eingabe fügt einen Schritt hinzu, und deshalb braucht eine Suche über eine Million Elemente zwanzig Vergleiche und nicht eine Million. Die Induktion macht diesen Satz wahr statt bloß beobachtet.

/* sorted array, search space halved */

  1000000  ->  500000  ->  250000  ->  125000  ->  ...

  2^10  = 1024             10 halvings
  2^20  = 1048576          20 halvings

T(1) = 1
T(n) = T(n / 2) + c   ->   T(n) = O(log n)

/* loop invariant over a[0 .. n - 1] */

init:  i = 0,  m = a[0]
test:  while i < len(a):
step:    if a[i] > m: m = a[i]
         i = i + 1
exit:  i == len(a)  ->  m = max(a)