Vollständige Induktion

No one believes an hypothesis except its originator, but everyone believes an experiment except the experimenter. (Anon)

Obviousness is always the enemy of correctness (Bertrand Russell 1872-1970)

Peano
(1858 - 1932)

• 1 ist eine natürliche Zahl.
• Zu jeder natürlichen Zahl n gibt es genau einen Nachfolger n‘, der ebenfalls eine natürliche Zahl ist.
• Es gibt keine natürliche Zahl, deren Nachfolger 1 ist.
• Die Nachfolger zweier natürlicher Zahlen sind voneinander verschieden.
• Eine Menge von natürlichen Zahlen enthält alle natürlichen Zahlen, wenn sie 1 enthält und mit einer natürlichen Zahl n auch stets auch deren Nachfolger n‘ enthält.

Der Nachfolger n' einer Zahl n schriebt man häufig auch n' = n+1, womit eine Rechen-Operation, die Addition in N eingeführt ist. n+2 wäre demnach (n+1)+1 und damit (n')'.
Aussagen der Form "A(n) ist wahr" für alle n aus N sollten sich mit Hilfe des Konzeptes 'Nachfolger' beweisen lassen.

Man geht so vor, dass man zunächst den Nachweis führt dass A(1) wahr ist. Dies kann man häufig durch Einsetzen von n = 1 in A(n) erledigen und ist häufig aber nicht immer leicht.  Diesen Schritt nennt man häufig Verankerung.

Im zweiten Schritt, häufig Induktionsschluss genannt, geht man davon aus, dass A(n) wahr ist und zeigt, dass dann auch A(n+1) wahr ist. ¹

• Fällt Stein Nr. n, dann fällt auch sein Nachfolger Stein Nr. n+1. (Induktionsschluss)

Stößt man den ersten Stein um (Induktionsverankerung), so weiß ich, dass alle Steine fallen (Peanosche Axiome). Gelingt es aber nicht Stein Nr. 1 zum Sturz zu bringen, werden alle stehen bleiben.

Für alle natürlichen Zahlen x und n gilt die Aussage:
A(n): xⁿ-1 ist durch x-1 ohne Rest teilbar.

Beweis:

1. Dass die Aussage für n=1,  (x-1) ist durch (x-1) ohne Rest teilbar, ist offensichtlich richtig.
2. Jetzt müssen wir zeigen, dass die Aussage für ein n+1 automatisch richtig ist, wenn sie für n richtig ist. Wir beweisen also weder die Aussage A(n), noch A(n+1). Nicht das Fallen des n-ten und nicht des (n+1)-ten Dominosteins ist zu garantieren, sondern die Eigenschaft: wenn der n-te Stein fällt, dann fällt auch automatisch der (n+1)-te.

   Was bleibt  also zu tun?

   Wir zeigen jetzt, dass unter Voraussetzung von „xⁿ-1 ist durch x-1“ teilbar,  auch „xⁿ⁺¹ durch x-1 teilbar“ ist, also A(n+1) gilt:  Wir formen dazu xⁿ⁺¹ - 1 um und erhalten
    

   xⁿ⁺¹ - 1 = x (xⁿ - 1) + (x-1),

   was sich durch einfaches Ausmultiplizieren bestätigen lässt.
   Beide Summanden der rechten Seite sind nach Voraussetzung durch x-1 teilbar, also auch die Summe und damit der Ausdruck links des Gleichheitszeichens. Also gilt auch Aussage A(n+1)

Wenn n eine natürliche Zahl, und 1+x > 0 ist, dann gilt die Abschätzung:
(1+x)ⁿ  >=  1+nx  (A(n))

Beweis:

1. Wieder ist die Aussage für n = 1 trivial: 1+x >= 1+x
2. (1+x)ⁿ⁺¹ = (1+x)(1+x)ⁿ  >= (1+x)(1+nx) = 1+ (n+1)x+nx² >= 1 + (n+1)x
   Also gilt A(n+1). An der farblich markierten Stelle wurde die Gültigkeit der Aussage A(n) vorausgesetzt.

Wo wird (1+x) >  0 vorausgesetzt?

für alle n,x,y (x¹y) aus N ist xⁿ⁺¹ + xⁿy - xyⁿ - yⁿ⁺¹ durch x-y teilbar
 

Beweis:

1. Die Aussage für n=1:
   x² + xy - xy - y² = x² - y² = (x+1)(x-1) ist durch x-1 teilbar,
   ist sicher richtig
    
2. Schluss A(n) auf A(n+1):
   Wir beginnen bei dem Term für A(n), verändern seine Gestalt so, dass man die Induktionsvoraussetzung verwenden kann.
   
   xⁿ⁺² + xⁿ⁺¹y - xyⁿ⁺¹ - yⁿ⁺² =
   x(xⁿ⁺¹ + xⁿy - yⁿ⁺¹ - xyⁿ) + x²yⁿ - yⁿ⁺² =
   x(xⁿ⁺¹ + xⁿy - yⁿ⁺¹ - xyⁿ) + yⁿ(x² - y²)
   
   Der erste Summand ist unter der Annahme der Richtigkeit von A(n) durch (x-y) teilbar, der zweite Summand wegen der 3ten binomischen Formel, damit ist die Summe durch (x-y) teilbar; also ist A(n+1), wenn A(n) richtig ist, ebenfalls richtig

aus der Geometrie

Behauptung:
n Geraden in einer Ebene, die in allgemeiner Position zueinander liegen, bilden
n·(n+1) / 2 + 1 Gebiete.

dabei verstehen wir unter einer allgemeinen Position, dass

1. keine zwei Geraden parallel sind und
2. keine 3 Geraden sich im gleichen Punkt schneiden

Mit Hilfe der Vollständigen Induktion beweisen wir zunächst den folgenden Hilfssatz:

Durch Hinzufügen einer Geraden zu n - 1 Geraden in allgemeiner Position in der Ebene erhöht sich die Anzahl der Gebiete um n.

zur Veranschaulichung:

1. n = 1
   Wir haben bei keiner (n - 1) Geraden 1 Gebiet, fügen eine Gerade hinzu und erhalten 2 Gebiete (n = 1 Gebiete kamen hinzu)
2. n = 2
   Wir haben bei einer (n - 1) Geraden 2 Gebiete, fügen eine Gerade hinzu und erhalten 4 Gebiete (n = 2 Gebiete kamen hinzu) 
3. n = 3
   Wir haben bei drei (n - 1) Geraden 4 Gebiete, fügen eine Gerade hinzu und erhalten 7 Gebiete (n = 3 Gebiete kamen hinzu)

Beweis:
Angenommen, es gibt n Geraden und die n - te Gerade fügte n Gebiete hinzu. Was passiert, wenn die (n + 1)- te Gerade hinzukommt?
Wegen allgemeiner Lage gilt, dass eine Gerade entweder ein Gebiet in zwei Teile schneidet oder das Gebiet nicht einmal berührt. Es muss also gezeigt werden, dass Gerade n + 1 genau n + 1 Gebiete schneidet.
Angenommen, Gerade n wäre nicht vorhanden. Dann würde die (n + 1) - te Gerade n neue Gebiete (Induktionsannahme) hinzufügen. Es muss also nur gezeigt werden, dass die Gegenwart von Gerade n verursacht, dass die (n + 1)- te Gerade ein zusätzliches Gebiet addiert.

Es existiert genau ein Gebiet, wo sich n-te  und (n + 1)-te Gerade schneiden (Schnittpunkt P). Gerade (n + 1) addiert ein neues Gebiet in G (schneidet es in zwei), wenn Gerade n nicht vorhanden, aber addiert zwei neue Gebiete (schneidet G in vier Teile), wenn Gerade n vorhanden ist.

G ist die einzige Region, die so beeinflusst wird. Also gilt: Die Gerade n + 1 addiert n Gebiete ohne Gerade n und n + 1 Gebiete mit der Geraden n.

Nun kann der Satz eigentliche Satz bewiesen werden:
Die Gesamtzahl der Gebiete für n Geraden in allgemeiner Lage ist
2 + 2 + 3 + 4 + 5 + ... + n.

1 + i = 1 + n·(n + 1) / 2

Für die Informatik wichtige Algorithmen
werden in diese Buch vorgestellt.

Die in diesem kurzen Abriss über die vollständige Induktion gewählten Bespiele stammen im wesentlichen aus diesem Buch.