________________________________________________________________________________
Inhalt....: Das Prinzip der vollständigen Induktion
Kategorie.: Unterrichtsmaterial
Mathematik: Analysis
MuPAD.....: 3.0.0
Datum.....: 2003-03-04
Autoren...: Kai Gehrs <acrowley@mupad.de>
Funktionen: subs, expand
________________________________________________________________________________
Das Prinzip der vollständigen Induktion
Dieses Notebook bietet eine kurze, kompakte Einführung in das Beweisprinzip der voll-
ständigen Induktion. Am Beispiel des Domino-Day wird das Konzept von Induktionsanfang
(der erste Stein, der umkippt), Induktionsvoraussetzung (der n-te Stein kippt um) und dem
Induktionsschluß (wenn der n-te Stein umkippt, so zeige, dass auch der (n+1)-te Stein um-
kippen wird) erklärt. Anschließend werden zwei formale Induktionsbeweise mit MuPAD
diskutiert. Dabei sind - neben den Funktionen subs und expand und einigen elementaren
Kenntnissen zur Bedienung von MuPAD - keinerlei weitere Voraussetzungen nötig.
Motivation und Konzept des Arbeitsblatts
Bei der Einführung der Integralrechnung über Rechtecksummen tauchen in der Regel
unweigerlich spezielle Summenformeln wie z.B.
auf: Oft wird etwa die Normalparabel f (x) = x² zur Einführung der Riemann-Integration
im Unterricht benutzt. Man wählt sich z.B. das Intervall von 0 bis 1 und beginnt es suk-
zessive in mehr gleich lange Teilintervalle zu unterteilen. Beim Übergang zu einem
allgemeinen Summationsindex steht man im Fall der Normalparabel vor dem Pro-
blem, die Summe der Quadratzahlen von 1 bis n berechnen zu müssen und an-
schließend den Grenzübergang für n gegen Unendlich vollziehen zu können. In der
Regel bleibt im Unterricht nicht die Zeit, diese Formeln herzuleiten, geschweige
denn sie mittels vollständiger Induktion zu beweisen.
Dieses Arbeitsblatt soll Abhilfe schaffen. Die Schüler/innen können sich selbst-
ständig mit den unten aufgeführten Inhalten beschäftigen. Das Prinzip der voll-
ständigen Induktion kann auf diese Weise im Rahmen einer Stunde bzw. einer
Doppelstunde (je nach Belieben) im Unterricht trotz Zeitmangels vorgestellt wer-
den.
Unterrichtliche Voraussetzungen für diese Einheit:
- die Schüler/innen haben den elementaren Umgang mit MuPAD
bereits erlernt
- die Berechnung von Summen bis zu einem allgemeinen Index
wurde zuvor im Unterricht (z.B. im Kontext der Integration) motiviert
- je nach Geschmack kann zuvor eine kurze Erläuterung des gedank-
lichen Prinzips der vollständigen Induktion erfolgt sein
Letzteres sollte nicht zwingend nötig sein: Das Prinzip der vollständigen Induktion
wird im folgenden anschaulich am Beispiel des "Domino-Days" verdeutlicht.
Motivation: Das gedankliche Prinzip der vollständigen Induktion
am Beispiel des "Domino-Day"
Wir alle kennen den "Domino-Day" aus dem Fernsehen, wo ein Team von
begeisterten Domino-Fans ganze Kunstwerke aus Domino-Steinen errichtet.
Die Steine werden dabei so geschickt angeordnet, dass an einer ausge-
zeichneten Stelle zu Beginn nur ein einzelner Stein umgekippt werden muss.
Dieser löst dann eine Kettenreaktion aus: Der erste Stein kippt gegen seinen
Nachbarn, der Nachbar kippt wiederum gegen seinen Nachbarn, der wiederum
gegen den nächsten Nachbarn usw. Auf diese Weise fallen alle Steine nach-
einander um.
Stellen wir uns vor, wir sollten im Voraus begründen, warum tatsächlich alle
Domino-Steine nacheinander umfallen. Wie würden wir dieses Problem am
geschicktesten lösen?
Nun: Eine Möglichkeit sicherlich darin, das gesamte Feld von Domino-Steinen
genaustens in Augenmerk zu nehmen und zu kontrollieren, ob alle Steine in der
Tat so angeordnet sind, dass der Vorgänger immer von seinen Nachfolger um-
stoßen wird.
Wer allerdings schon einmal den "Domino-Day" im Fernsehen gesehen hat,
der weiß, dass man wahrscheinlich Tage brauchen würde, bis man davon
überzeugt sein kann, dass in der Tat alle Steine umfallen werden.
Geschickter ist die folgende simple Argumentation: Wir wissen, dass der
erste Stein per Hand umgestoßen wird. Stellen wir uns die Domino-Steine
einmal mit den Zahlen 1, 2, 3, . . . , n, n + 1, . . . usw. durchnummeriert vor.
Jetzt nehmen wir einfach an, der Stein mit der Nummer n würde in der Tat
umfallen. Dann kontrollieren wir, ob der Stein n nah genug an seinem Nach-
folger, d.h. dem Stein mit der Nummer n + 1, steht. Ist dies der Fall, so wird
der Stein mit der Nummer n + 1 umfallen.
Sind wir also in der Lage, die obige Argumentation für einen beliebigen
Stein n und seinen Nachfolger mit der Nummer n + 1 durchzuführen, so
können wir also unser Gegenüber sicherlich davon überzeugen, dass alle
Steine umfallen.
Und was hat das alles mit Mathematik zu tun?
Eine ganze Menge!
Formalisierung des Prinzips der vollständigen Induktion am
Beispiel der Summe der ersten n Quadratzahlen
Was wir soeben informell erarbeitet haben, nennt sich das Prinzip der
vollständigen Induktion. Dieses Prinzip ist eines der wichtigsten in der
Mathematik und der Informatik. Wir werden jetzt sehen, wie man es
nutzen kann, um "Aussagen über den natürlichen Zahlen" zu beweisen.
Aufgabe: Beweise, dass die Summe der Quadratzahlen von 1 bis zu einer
beliebigen Zahl n gegeben ist durch:
Dabei bedeutet das Zeichen auf der linken Seite der Gleichung
nichts anderes als: Bilde die Summe der ersten n Quadratzahlen.
Wir können natürlich nicht für jede natürliche Zahl n ausprobieren, ob die obige
Formel korrekt ist. Stattdessen gehen wir einfach so vor, wie wir es oben bei
dem Beispiel des "Domino-Days" getan haben.
Induktionsanfang:
Wir müssen sicherstellen, dass der erste Domino-Stein umgekippt wird. Andern-
falls haben alle anderen keine Chance auch umzufallen. In unserer Situation ent-
spricht das "Umkippen des ersten Stein" der Probe, ob die obige Formel für den
"trivialen Fall" n = 1 erfüllt ist. Die Summe der ersten n Quadratzahlen schrumpft für
den Fall n = 1 auf 12 = 1 zusammen. Wir müssen also nur noch überprüfen, ob
auch die rechte Seite der Formel
für n = 1 den Wert 1 ergibt. Dies nennt man den Induktionsanfang.
Dazu definieren wir die rechte Seite zuerst für allgemeines
Quadrate_bis_n:= 1/6 * n * (n + 1) * (2*n + 1)
und setzen dann für n den Wert 1 ein:
subs(Quadrate_bis_n, n = 1)
Das ist genau der Wert, den wir haben wollten. Wir haben also gezeigt, dass
die obigen Formel im Fall n = 1 richtig ist oder mit anderen Worten: Der erste
Domino-Stein ist umgefallen.
Induktionsvoraussetzung und Induktionsschluss:
Jetzt gehen wir davon aus, dass der Stein mit der Nummer n umgefallen ist.
Diese Annahme nennt man die Induktionsvoraussetzung.
Unter dieser Voraussetzung müssen wir zeigen, dass auch der Stein mit der
Nummer n + 1 umfallen wird, d.h. wir führen den sogenannten Induktions-
schluss durch.
In unserer Situation bedeutet das: Wir nehmen an, die Summe der ersten
n Quadratzahlen ist in der Tat durch
gegeben. Zu zeigen ist, dass die Summe ersten n + 1 Quadratzahlen gegeben
ist durch
d.h. wir setzen einfach in die ursprünglich Formel statt n den Wert n + 1 ein.
Der Beweis ist nun gar nicht: Wir dürfen annehmen, dass die Summe der
Quadratzahlen von 1 bis n gegeben durch
Quadrate_bis_n
Um die Summe der Quadratzahlen von 1 bis n + 1 zu berechnen, müssen wir
also zu der Formel Quadrate_bis_n nur noch das Quadrat von n + 1 hinzu-
addieren:
Summe:= Quadrate_bis_n + (n + 1)^2
Nun prüfen wir einfach, ob die Ausdrücke
und
gleich sind: Am einfachsten gelingt dies, wenn wir beide Ausdrücke vollständig
ausmultiplizieren lassen.
expand(Summe)
expand(1/6 * (n + 1) * (n + 1 + 1) * (2 * (n + 1) + 1))
Die beiden Ausdrücke sind gleich! Damit ist die Behauptung bewiesen.
Nun zu einem weiteren Beispiel: Wir wollen beweisen, dass die Formel
korrekt ist, d.h. dass die Summe der Zahlen von 1 bis n gerade durch
die rechte Seite der obigen Gleichung gegeben ist.
Wir kürzen die Vorgehensweise jetzt stärker ab und gestalten den Beweis
formaler:
Induktionsanfang (zeige die Behauptung für n = 1): Die Summe der Zahlen
von 1 bis 1 ist sicherlich 1. Wir setzen den Wert n = 1 in die rechte Seite der
obigen Gleichung ein und erhalten:
Summe_1_bis_n:= 1/2 * n * (n + 1)
subs(Summe_1_bis_n, n = 1)
Damit ist der Induktionsanfang erledigt.
Induktionsvoraussetzung: Die Summe der Zahlen von 1 bis n ist
Induktionsschluss: Setzen wir in die Formel für n den Wert n + 1 ein, so
erhalten wir:
::::::::::::::::::( * )
Unter Verwendung der Induktionsvoraussetzung ergibt sich die Summe der
Zahlen von 1 bis n + 1 zu:
Summe:= Summe_1_bis_n + (n + 1)
Wir müssen zeigen, dass dieser Ausdruck und ( * ) übereinstimmen:
expand(Summe)
expand(1/2 * (n + 1) * (n + 1 + 1))
was offensichtlich der Fall ist. Damit ist die Behauptung bewiesen.
Aufgabe: Beweise analog zu der obigen Vorgehensweise die Formel
________________________________________________________________________________
Anmerkungen:
1. Weitere Anregungen finden Sie in der Buchreihe Mathematik 1 x anders. In dieser Reihe
wird eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD gelöst. Die
Bücher können unter www.schule.mupad.de/literatur kostenfrei kopiert werden.
2. Viele weitere praxisorientierte Aufgaben finden sich unter der Web-Adresse
http://www.learn-line.nrw.de
________________________________________________________________________________