Banner der Website mathematik.de. Motiv: Überall ist Mathematik

Vollständige Induktion

Das Problem

In der Mathematik kommt es häufig vor, dass man Aussagen nicht nur für eine endliche Menge zeigen muss, sondern für die Gesamtheit der natürlichen Zahlen, welche wir mit \(\N\) bezeichnen. Hierbei kann man dann nicht wie gewöhnlich vorgehen und die Aussage A der Reihe nach für alle natürlichen Zahlen zeigen, da es sich ja um eine unendliche Menge handelt.

Die Lösung

Die vollständige Induktion liefert eine Methode, Aussagen für alle natürlichen Zahlen zu beweisen:

  1. Man weist nach, dass A(1) wahr ist (Induktionsanfang).
  2. Man nimmt an, dass A(n) für ein festes n in \(\N\) gilt (Induktionsvoraussetzung oder Induktionsannahme). Nun zeigt man, dass, wenn A(n) gilt, auch A(n+1) zutrifft; also, wenn die Aussage A für ein festes n in \(\N\) wahr ist, dass sie dann auch für den Nachfolger von n erfüllt ist (Induktionsschluss).

Somit weiß man, dass

  1. A(1) wahr ist und
  2. die Folgerung „Wenn A(n) gilt, so folgt, dass sie auch für A(n+1) zutrifft“ wahr ist.

Nun kann man aber auch schon sehen, dass die Aussage für alle natürlichen Zahlen gelten muss: Es gilt für die erste natürliche Zahl, die Eins. Somit wegen 2. auch für die Zwei und weiter wegen 2. für die Drei,....

Zu beachten:

  • Beim Induktionsschluss ist eine Implikation zu zeigen, das heißt, man muss überprüfen, ob eine Aussage für n+1 gilt unter der Annahme, dass sie für n gilt. Man muss nicht fragen, ob sie denn für n erfüllt ist.
  • Sowohl Induktionsanfang als auch Induktionsschluss müssen erfüllt sein. Ohne einen gültigen Induktionsanfang könnte man immer noch erhalten, dass der Schluss von n auf n+1 gelingt. Allerdings hat man es dann nicht für ein n in \(\N\) gezeigt und somit fehlt die Basis.
  • Der Induktionsanfang muss nicht immer bei n = 1 bzw. n = 0 gewählt werden. In manchen Fällen gilt die zu beweisende Aussage erst ab einer größeren Zahl. Dennoch ist es ratsam, den Induktionsanfang bei der kleinstmöglichen Zahl zu wählen.
  • Um die Beweisführung so übersichtlich wie möglich zu gestalten, hält man sich am Besten an das Schema:
    • Induktionsanfang (IA)
    • Induktionsvoraussetzung (IV)
    • Induktionsschluss (IS)
  • Manchmal muss man, um den Induktionsschluss führen zu können, bei der Induktionsannahme die Gültigkeit der Aussage gleich für ein paar natürliche Zahlen ≤ n annehmen. Das ist auch in Ordnung. Es darf nur nicht bei der Induktionsvoraussetzung die Gültigkeit der Aussage für eine natürliche Zahl > n angenommen werden bzw. beim Induktionsschluss verwendet werden.
  • Meistens läuft die Induktion über n ab. Jedoch ist n hier nur eine Variable und kann somit durch jeden anderen beliebigen Buchstaben ersetzt werden. In manchen Aussagen sind mehrere Variable enthalten, so dass man sich erst klar machen sollt,e über welche Variable die Induktion zu führen ist.

Beispiele:

  • Man beweise mit Hilfe vollständiger Induktion, dass die Formel 1+3+5+...+(2n-1) = n2 erfüllt ist.

    Induktionsanfang: n = 1:   1 = 12 = 1 ist erfüllt.
    Induktionsvoraussetzung: 1+3+5+...+(2n-1) = n2 gilt für ein n aus \(\N\).
    Induktionsschluss:

    1+3+5+...+(2(n+1)-1) = 1+3+5+...+(2n+1)
    = 1+3+5+...+(2n-1) + (2n+1)
    = n2 + (2n+1) (nach Induktionsvoraussetzung)
    = n2+2n+1
    = (n+1)2 (nach 1. binomischer Formel)

  • Beweise mit vollständiger Induktion: 1+5+9+...+(4n-3) = n(2n-1).

    Induktionsanfang: n = 1:   1 = 1(2-1) = 1 ist erfüllt.
    Induktionsvoraus.: 1+5+9+...+(4n-3) = n(2n-1) gilt für ein n in \(\N\).
    Induktionsschluss:

    1+5+9+...+(4n-3)+(4(n+1)-3) = n(2n-1)+(4(n+1)-3) (nach Induktionsvoraussetzung)
    = 2n2-n+4n+1
    = 2n2+3n+1
    = (n+1)(2n+1).

  • Mit Hilfe der vollständigen Induktion soll gezeigt werden, dass n5-n durch 5 teilbar ist für alle n in \(\N\).

    Induktionsanfang: n=1:   15-1=0 und somit durch 5 teilbar.
    Induktionsvoraus.: Gelte für ein n in \(\N\): n5-n ist durch 5 teilbar, d.h. es existiert ein m in \(\N\), so dass gilt: 5m = n5-n.
    Induktionsschluss:

    (n+1)5-(n+1) = (n+1)5-n-1
    = n5+5n4+10n3+10n2+5n+1-n-1
    = n5-n+5(n4+2n3+2n2+n)
    = 5m+5(n4+2n3+2n2+n) (nach Induktionsvoraussetzung)
    = (m+(n4+2n3+2n2+n))5
    Und somit folgt, dass (n+1)5-(n+1) durch 5 teilbar ist.

Links

Hier finden Sie Links zum Thema vollständige Induktion. Sie haben eine Seite zum Thema vollständige Induktion, die hier noch nicht auftaucht? Schreiben Sie uns! (mail[at]mathematik.de)