Beispiel mit fehlendem Induktionsanfang
Wir zeigen nun an einem Beispiel, dass man eine unwahre Behauptung mit vollständiger Induktion beweisen kann, wenn man auf den Induktionsanfang verzichtet. In unserem Beispiel beweisen wir nun, dass alle ungeraden Zahlen durch \(2\) teilbar also gerade sind.
Beispiel:
Wir zeigen mit vollständiger Induktion die folgende Aussage:
\(\qquad\) | Alle ungeraden Zahlen \(2n+1\) mit \(n\in \mathbb{N}\) sind durch \(2\) teilbar. |
Fehlerhafter Beweis mit vollständiger Induktion:
Induktionsschritt: Induktionsvoraussetzung:
Induktionsbehauptung:
Induktionsbeweis:
| |||||||||||||||||||||||
\(\blacksquare\) |
Verzichten wir also auf den Induktionsanfang, dann können wir beweisen, dass alle ungeraden Zahlen gerade sind. Schauen wir uns jetzt den Induktionsanfang an:
Induktionsanfang:
Für \(n=0\) gilt:
\(\qquad\) | \(2\cdot 0+1=1\) ist nicht durch \(2\) teilbar |
Der Induktionsanfang ist somit falsch.
Da bereits der Induktionsanfang nicht korrekt ist, können wir die Behauptung nicht mit vollständiger Induktion beweisen. Mehr noch: wir haben die Behauptung sogar durch ein Gegenbeispiel widerlegt.
\(\enspace\)