-
E. Job-StiftungSchüler studieren Informatik am KIT

 


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

 



Vollständige Induktion
Direkter Beweis

Beweis durch Widerspruch

Vollständige Induktion

Im Schulunterricht begegnet man gewöhnlich diesen drei Beweistechniken: Direkter Beweis, Beweis durch Widerspruch und vollständige Induktion. Durch Umformungen und Ergänzungen beweist man z.B. - ausgehend vom Differentialquotienten – die Produktregel für die Ableitung: (fg)' = f'g + fg'. Der bekannte Beweis ist ein typischer Vertreter der direkten Beweise. Einem Beispiel für einen Beweis durch Widerspruch begegnen wir beim Nachweis, dass Wurzel aus 2 eine irrationale Zahl ist. Was man unter einer vollständigen Induktion versteht,  soll hier aufgezeigt und an einigen Beispielen gezeigt werden

 

Peanosche Axiome


Peano
(1858 - 1932)

Axiome sind Sätze, in denen sich Begriffe durch ihre Beziehung  untereinander erklären. So lassen sich die natürliche Zahlen axiomatisch durch 5 Sätze, den sog. Peanosche Axiome erklären.

  • 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.

 

Die Idee der vollständigen Induktion

Die Beweistechnik wird angewandt, wenn man zeigen will, dass eine Aussage A(n) für alle natürliche Zahlen n gilt.

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. 1

 

Dominosteine

Die Idee der vollständigen Induktion lässt sich mit einer langen Reihe  von Dominosteinen veranschaulichen (eigentlich müssten es so viele sein, wie es natürliche Zahlen gibt, also abzählbar unendlich viele, das lässt sich natürlich nicht in die Realität umsetzen, weshalb wir also eine 'lange' Reihe gewählt haben). Diese Dominosteine sind so in Reih' und Glied aufgestellt, dass man für jeden Stein folgendes garantieren kann:

  • 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.

 

Beispiel 1
Behauptung:

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

Beweis:

  1. Dass die Aussage für n=1,  (x1-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 „xn-1 ist durch
    x-1“ teilbar,  auch „xn+1 durch x-1 teilbar“ ist, also A(n+1) gilt:  Wir formen dazu xn+1 - 1 um und erhalten

     

    xn+1 - 1 = x (xn - 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)
Beispiel 2

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

Beweis:

  1. Wieder ist die Aussage für n = 1 trivial: 1+x1 ≥ 1+x
  2. (1+x)n+1 = (1+x)(1+x)n  ≥ (1+x)(1+nx) = 1+ (n+1)x+nx2
    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?  

Beispiel 3

Behauptung:

für alle n,x,y (x¹y) aus N ist xn+1 + xny - xyn - yn+1 durch x-y teilbar

Beweis:

  1. Die Aussage für n=1:

    x2 + xy - xy - y2 = x2 - y2 = (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.

    xn+2 + xn+1y - xyn+1 - yn+2 =
    x(xn+1 + xny - yn+1 - xyn) + x2yn - yn+2 =
    x(xn+1 + xny - yn+1 - xyn) + yn(x2 - y2)

    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

 

Fußnoten
1 Es werden also weder A(n) = wahr noch A(n+1) = wahr bewiesen. Es sei also vermerkt: Es gibt Fälle, in denen der Schluss von A(n) auf A(n+1) wohl gelingt, obwohl es kein n gibt, für das A(n) selbst wahr ist.

 

Weiterlesen

Introduction to Algorithms
Gebundene Ausgabe
- 300 Seiten - Addison Wesley
Erscheinungsdatum: 1. Januar 1989
ISBN: 0201120372

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.