Vollständige Induktion

Wähle eine Behauptung über jede natürliche Zahl n. Jeder Dominostein unten steht für ein n und ist danach gefärbt, ob die Behauptung dort gilt, was direkt überprüft wird. Der Pfeil aus einem Dominostein ist der Induktionsschritt von n nach n + 1. Nur ein wahrer Start-Dominostein mit einer ununterbrochenen Kette von Pfeilen dahinter ist ein Beweis. Alle Dominosteine, die diese Kette erreicht, fallen um.

Rechenbeispiel — Vollständige Induktion

Schritt von 1 nach 2	scheitert
Bewiesen für n bis 12	1
Erstes falsches n, bis 12	2

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Vollständige Induktion

Die vollständige Induktion beweist eine Aussage P(n) für jede natürliche Zahl n ab einem bestimmten n₀ in zwei Teilen: dem Induktionsanfang, bei dem P(n₀) direkt überprüft wird, und dem Induktionsschritt. Letzterer ist ein Argument, dass P(k) für jedes k ≥ n₀ zwingend P(k + 1) nach sich zieht. Zusammen erreichen sie jedes n, genau wie jeder fallende Dominostein den nächsten umwirft.

Was die einzelnen Symbole bedeuten

P(n): die Aussage über n; bei jedem n ist sie einfach wahr oder falsch
n₀: der Induktionsanfang, wo der Beweis beginnt, von Hand nachgerechnet
k: ein allgemeines n innerhalb des Schritts: das Argument setzt P(k) voraus und muss P(k + 1) erreichen

Woher die Formel kommt

Warum die beiden Teile ausreichen. Nimm an, der Induktionsanfang gilt und der Schritt funktioniert für jedes k ≥ n₀, aber P ist ab n₀ irgendwo falsch. Unter den n, wo es falsch ist, gibt es ein kleinstes. Nennen wir es m. Es ist nicht n₀, da P(n₀) geprüft wurde. Also ist m − 1 ≥ n₀, und P(m − 1) ist wahr, weil m der kleinste Fehlschlag war. Der Schritt liefert dann P(m), was im Widerspruch dazu steht, dass P(m) falsch ist. Es gibt also keinen Fehlschlag. Beide Teile werden gebraucht. Ohne den Anfang könnte m gleich n₀ sein. Würde der Schritt bei einem einzigen k fehlen, könnte m gleich k + 1 sein.
Warum n² + n + 41 scheitern musste. Bei n = 40 lassen sich die ersten beiden Terme zusammenfassen, 40² + 40 = 40 × 41. Das bedeutet 40² + 40 + 41 = 40 × 41 + 41 = 41 × 41. Bei n = 41 ist jeder Term ein Vielfaches von 41, und der Wert ist 41 × 43. Die Idee geht noch weiter. Kein Polynom mit ganzzahligen Koeffizienten, das keine Konstante ist, kann ausschließlich Primzahlen liefern, egal wie viele es am Anfang erzeugt (Lehman, Leighton und Meyer beweisen dies in Problem 1.25). Ein Induktionsschritt für diese Behauptung hätte also niemals existieren können.
2ⁿ > n² für jedes n ≥ 5, sauber durchgeführt. Induktionsanfang: 2⁵ = 32 > 25 = 5². Schritt: Sei k ≥ 5 und wir nehmen 2ᵏ > k² an. Dann ist 2ᵏ⁺¹ = 2 · 2ᵏ > 2k² = k² + k². Da k ≥ 5 ist, gilt k² ≥ 5k = 2k + 3k > 2k + 1. Es folgt 2k² > k² + 2k + 1 = (k + 1)² und damit 2ᵏ⁺¹ > (k + 1)², was genau P(k + 1) ist. Der Schritt selbst erfordert nur k ≥ 3. Der Anfang musste bei 5 liegen, da P(2), P(3) und P(4) falsch sind.

Vierzig wahre Fälle, dann 41 × 41 🖖

Klick auf n² + n + 41. Die Werte 41, 43, 47, 53, 61, … sind Primzahlen für jedes n von 0 bis 39, vierzig hintereinander. Bei n = 40 beträgt der Wert 1.681 = 41 × 41. Du kannst es vorhersehen, sobald du genau hinschaust: 40² + 40 + 41 = 40 × 41 + 41. Das Diagramm hat keine Pfeile, da es keinen Schritt gibt. Zu wissen, dass p(39) = 1.601 prim ist, sagt nichts über p(40) aus, was p(39) + 80 ist. Von den ersten tausend Werten sind 581 prim. Genau deshalb wirkt das Muster so überzeugend.

Der Schritt für 2ⁿ > n² funktioniert ab k = 3, die Behauptung erst ab n = 5 🖖

Klick auf 2ⁿ > n² ab 1. Der Induktionsanfang gilt, da 2 > 1. Der Schritt besagt: Wenn 2ᵏ > k², dann ist 2ᵏ⁺¹ > 2k². Dabei gilt 2k² ≥ (k + 1)² genau dann, wenn k² ≥ 2k + 1, was ab k = 3 wahr ist. Von n₀ = 1 ausgehend sind die Pfeile aus 1 und 2 also gebrochen, und die Behauptung ist bei 2, 3 und 4 falsch. Die Pfeile aus 3 und 4 funktionieren, obwohl P(3) und P(4) beide falsch sind. Ein korrekter Schritt mit einem falschen Dominostein im Rücken stößt nichts an. Klick auf 2ⁿ > n² ab 5, und dieselben Pfeile beweisen jedes n ab 5.

Das Pferde-Argument ist in jedem Schritt richtig, bis auf einen 🖖

Klick auf Die Pferde. Der Schritt nimmt n + 1 Pferde, wendet die Behauptung auf die ersten n und auf die letzten n an und verbindet sie über die Pferde, die beide Gruppen teilen. Ab n = 2 funktioniert das, und jeder Pfeil ab 2 ist durchgezogen. Von 1 nach 2 bestehen die Gruppen jeweils aus einem Pferd und haben keine gemeinsamen. Das Argument beweist also genau an der einzigen Stelle, an der es gebraucht wird, nichts. Setze den Anfang stattdessen auf 5 und jeder Schritt funktioniert. Da aber P(5) falsch ist, hat die Kette nichts, was sie anstoßen könnte.

Aufgabe vollständig gelöst

Ab wann ist 2ⁿ dauerhaft größer als n³? 4 Schritte
Beweise, dass 2ⁿ > n³ für jedes ausreichend große n gilt. Der Schritt ist leicht aufzuschreiben. Ab wann funktioniert er, und wo muss der Induktionsanfang liegen?

Öffne diese Aufgabe im Tool
1. Nimm P(k) an: 2ᵏ > k³. Verdoppeln ist der einzige mögliche Spielzug:
  
  $2^{k} > k^{3} \Rightarrow 2^{k + 1} = 2 \cdot 2^{k} > 2 k^{3}$
2. Der Schritt funktioniert also, wenn 2k³ ≥ (k + 1)³ gilt. Teile beide Seiten durch k³:
  
  $2 k^{3} \geq (k + 1)^{3} ⟺ (1 + \frac{1}{k})^{3} \leq 2 ⟺ k \geq \frac{1}{3 2 - 1} = 3.847$
3. Der Schritt klappt ab k = 4, nicht ab 3:
  
  $k = 3 : 2 \cdot 27 = 54 < 64 = 4^{3}, k = 4 : 2 \cdot 64 = 128 \geq 125 = 5^{3}$
4. Aber die Behauptung selbst ist von n = 2 bis n = 9 falsch. Der Induktionsanfang ist das erste n, bei dem sie wieder gilt:
  
  $2^{9} = 512 < 729 = 9^{3}, 2^{10} = 1, 024 > 1, 000 = 1 0^{3}$
Antwort

2ⁿ > n³ gilt für jedes n ≥ 10 sowie bei n = 0 und 1. Der Schritt funktioniert ab k = 4. Für k = 4 bis 9 sitzt also ein korrekter Schritt hinter einer falschen Behauptung, genau wie es bei 2ⁿ > n² auf dieser Seite für 3 und 4 der Fall ist. Klick zum Vergleichen auf 2ⁿ > n² ab 5.

$2^{n} > n^{3} for every n \geq 10 (and n = 0, 1); step from k = 4, base n_{0} = 10$

Lernpfad

Beweismethoden

Quellen (3)

Both of this page's broken arguments, worked through: n² + n + 41 prime through n = 39 and 41·41 at n = 40 (§1.1), and the horses, whose failure the text pins to the one step P(1) → P(2) (§5.1): E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §1.1 and §5.1.
The primes n² + n + 41 takes, with the forty consecutive prime values from n = 0 to 39: OEIS Foundation, "A005846: Primes of the form k² + k + 41", The On-Line Encyclopedia of Integer Sequences.
Where the horses come from: George Pólya posed the argument as an induction exercise in 1954: ProofWiki, "All Horses are the Same Colour/Historical Note", citing G. Pólya, Induction and Analogy in Mathematics (Princeton University Press, 1954).

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.