Unvollständige Induktion
Die unvollständige Induktion ist ein mathematisches Beweisverfahren, welches sich an die vollständige Induktion anlehnt.
Inhaltsverzeichnis
Verfahren
Der Ablauf basiert auf der vollständigen Induktion: Wenn irgendeine Aussage P (oder Q, was auch immer) für alle n>0 gilt, gilt sie für alle n>0. Das beweist man, indem man behauptet, dass die Aussage dann gilt, wenn sie für alle n+1 gültig ist. Dadurch wird per Dominoeffekt die Gültigkeit für alle nachfolgenden Zahlen bewiesen. Klingt komisch, ist aber so.
Die unvollständige Induktion geht damit etwas schlampiger um, es wird lediglich gesagt: Wenn die Aussage P (oder Q) für irgendeine Zufallszahl (frei wählbar) gilt und auch für die nächste natürliche Zahl (= Zahl ohne Komma) gilt, ist sie damit automatisch für alle Zahlen gültig.
Das bezieht natürlich zwangsläufig nicht die Fälle vor und hinter den gewählten Zahlen mit in den Beweis ein, auch wenn er sie trotzdem als korrekt beweist. Auch wird auf solch überflüssige Sachen wie Induktionsanfang vor und nach jedem einzelnen Schritt verzichtet. Aber schließlich muss man den Namen der Methode ja irgendwie rechtfertigen.
Anwendungsbeispiel 1
- 2 ist eine Primzahl.
- Die nächste natürliche Zahl (3) ist auch eine Primzahl.
- Folglich sind alle natürlichen Zahlen Primzahlen.
Die Beweise der einzelnen Zwischenschritte ("Wieso ist 3 eine Primzahl??") kann man hierbei mit allen möglichen Quellen belegen, die man kennt, auch wenn sie mathematisch nicht unbedingt konventionell sind ("Das weiß man einfach!").
Anschließend kann man guten Gewissens behaupten, die Aussage P (oder Q) mathematisch bewiesen zu haben. Dass man die umstrittene unvollständige Induktion benutzt hat, muss ja keiner wissen - hauptsache, die Aussage wurde bewiesen! Oder?
Anwendungsbeispiel 2
Es ist zu zeigen, dass [math]2^n \leq n^2[/math] für [math]n \in \mathbb{N}[/math] gilt.
1. Zufällige Induktionsbasis [math]n = 3[/math]:
- [math]2^3 \leq 3^2[/math]
- [math]8 \leq 9[/math]
2. Unvollständiger Induktionsschritt [math]n + 1 = 4[/math]:
- [math]2^4 \leq 4^2[/math]
- [math]16 \leq 16[/math]
Es gilt daher: [math]\forall n \in \mathbb{N} : 2^n \leq n^2[/math]
Bemerkung: Die Betrachtung der Formel für [math]n = 100[/math] hat zwar nichts mit der unvollständigen Induktion zu tun, wird hier jedoch trotzdem angeführt.
Für [math]n = 100[/math] gilt wegen [math]\forall n \in \mathbb{N} : 2^n \leq n^2[/math]:
- [math]2^{100} \leq 100^2[/math]
- [math]1267650600228229500000000000000 \leq 10000[/math]
Da die Aussage [math]1267650600228229500000000000000 \lt 10000\,[/math] offensichtlich falsch ist folgt aus dem obigen Ausdruck:
- [math]1267650600228229500000000000000 = 10000\,[/math]
Trivia
Studenten kniffelten in Klausuren eine Zeitlang gerne mit der Formulierung "Induktion". Wenn auf dem Aufgabenblatt ein Induktionsbeweis verlangt würde, könne man auch die Unvollständige benutzen, hieß es. Nach einer Welle von bestandenen Prüfungen verboten die Universitäten diese Vorgehensweise jedoch landesweit und erkannten ihr die Titulierung "Beweis" ab. Daraufhin sank die Quote der Bestehenden wieder auf die üblichen 25%.