Florian André Dalwigk
Vollständige Induktion – Beispiele und Aufgaben bis zum Umfallen
Springer Spektrum 2019, XI+ 341, 27,99 €
ISBN: 978-3-662-58632-7
ISBN: 978-3-662-58633-4 (eBook)
Die Vollständige Induktion ist ein Beweisprinzip, das man problemlos im Gymnasium erklären kann: Wenn ich eine durchnummerierbare Liste von Aussagen habe, von denen die erste richtig ist, und für jede natürliche Zahl n die Richtigkeit der n-ten Aussagen die Richtigkeit der n + 1-ten Aussage nach sich zieht, dann sind alle Aussagen richtig. Zur Illustration des Prinzips beweist man gerne Gleichheiten von algebraischen Ausdrücken, die von einer natürlichen Zahl abhängen, zum Beispiel \(1+\cdots + n=\frac{1}{2}n(n+1)\). Wenn dies die Aussage \(A(n)\) ist, dann besteht der zugehörige Induktionsbeweis aus zwei Teilen. Dem Induktionsanfang, das heißt dem Nachweis, dass \(A(1)\) richtig ist (im Beispiel \(1=\frac{1}{2}\cdot 1\cdot 2\)), und dem Induktionsschritt, das heißt dem Nachweis, dass für jedes \(n\in{\mathbb N}\) aus der Aussage \(A(n)\) die Aussage \(A(n+1)\) folgt (im Beispiel
\(1+\cdots + n + (n+1){{=}\atop{A(n)}}\frac{1}{2}n(n+1)+(n+1)=\frac{1}{2}(n+1)(n+2)\)).
Man braucht also drei Informationen, um einen Induktionsbeweis durchführen zu können: Die exakte Formulierung der zu beweisenden nummerierten Liste \(A(n)_{n\in{\mathbb N}}\) von Aussagen, eine Methode die Richtigkeit von \(A(1)\) zu etablieren und eine Methode die Implikation \(A(n)\Rightarrow A(n+1)\) zu zeigen. Wenn man eine Summe der Form \(\sum_{k=1}^n a_k\) auswerten will (im Beispiel oben war \(a_k=k\)), dann scheitert das in aller Regel schon daran, dass man keinen Kandidaten für die rechte Seite von \(A(n)\) findet. Hat man eine nummerierte Liste von Aussagen vorgegeben, kann schon der Induktionsanfang problematisch sein. Nehmen wir zum Beispiel als \(A(n)\) die Aussage „Es gibt keine natürlichen Zahlen \(x,y,z\) mit \(x^{n+2}+y^{n+2}=z^{n+2}\)“. Dann ist der Induktionsanfang ein Spezialfall des Großen Fermatschen Satzes, von dem man annimmt, dass Pierre de Fermat (1607–1665) ihn tatsächlich beweisen konnte (der erste veröffentlichte Beweis stammt von Euler aus dem Jahr 1770). Aber selbst wenn man damit den Induktionsanfang geschafft hat, ist völlig unklar, wie der Induktionsschritt getan werden könnte. Der Beweis, den Andrew Wiles 1994 für die allgemeine Aussage \(A(n)\) gab, beruhte auf ganz anderen Methoden. Für Induktionsbeweise lässt sich also kein allgemeines Kochrezept angeben. Vielmehr stellt es sich heraus, dass es eine Kunst ist, die richtigen Aussagen zu wählen. Manchmal wird ein Beweis dadurch ermöglicht, dass man die Aussagen in der richtigen Art und Weise verschärft. Ein simples Beispiel hierfür ist die Aussagenliste \(\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{(n+1)^2}<1\). Wenn man sie zu \(\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{(n+1)^2}=1-\frac{1}{n+1}\) verschärft, ist der Induktionsbeweis ganz einfach.
Klausuraufgaben zur Induktion geben normalerweise die Aussagenliste vor. Wenn nicht, werden Beispiele gewählt, für die man die Aussage durch Berechnung der ersten paar Aussagen raten kann, wie zum Beispiel \({n\choose 0}+{n\choose 1}+\cdots+{n\choose n}=?\) (es kommt immer \(2^n\) heraus, wie man auch am Binomischen Lehrsatz sieht). Niemand erwartet, dass Oberstufenschüler oder studentische Anfänger sich in der Klausursituation subtile Tricks ausdenken (etwas anders sieht es bei Klausuren zu Mathematik-Olympiaden aus). Daher ist in solchen Aufgaben typischerweise der Induktionsanfang eine einfache Verifikation und der Induktionsschritt mithilfe von wenigen algebraischen Umformungen oder als bekannt vorausgesetzten Identitäten zu bewältigen. Man will ja nur testen, ob die Prüflinge das Prinzip verstanden haben.
In der mathematischen Praxis dagegen kommt die nummerierende Zahl in der Aussagenliste ganz oft als Dimension, Nilpotenzgrad oder Erzeugeranzahl daher. Wie immer, wenn es darum geht etwas anzuwenden, macht die anzuwendende Technik (hier die vollständige Induktion) nur einen kleinen Prozentsatz der intellektuellen Anstrengung aus. Der Löwenanteil geht in die Durchdringung des Kontexts.
Beide hier zu besprechenden Bücher, Andreescu-Crisan ([AC]) und Dalwigk ([D]), sind im Wesentlichen Aufgabensammlungen mit kurzen Theorieteilen und detailliert vorgeführten Beispielen sowie ausgearbeiteten Lösungen. [AC] enthält auf 430 Seiten 216 Aufgaben, [D] auf 341 Seiten 104 Aufgaben. Dennoch sind Anspruch und Zielsetzung der beiden Bücher grundverschieden.
Dalwigk versteht seinen Text als Hilfestellung für Erstsemester bei der Bewältigung von Klausuraufgaben zum Thema vollständige Induktion. Bemerkenswert forsch formuliert er seine Kritik an der Lehrpraxis an deutschen Hochschulen und nimmt für sich in Anspruch den richtigen Weg zur Vermittlung des Stoffes gefunden zu haben. Er setzt auf folgendes Induktionsrezept (Abschnitt 1.3): „[...]Was brauchst du alles dafür?
1. Einen Induktionsanfang, den du für einen Startwert n0 zeigst,
2. eine Induktionsvoraussetzung,
3. eine Induktionsbehauptung und
4. einen Induktionsschritt.“
In meiner obigen Beschreibung entspricht dem:
1. \(A(1)\),
2. \(A(n)\)1,
3. \(A(n+1)\),
4. \(A(n)\Rightarrow A(n+1)\).
Wenn die Aussagenliste erst mit \(A(n_0)\) beginnt, kann man sie durch die Liste \(A'(n)=A(n+n_0-1)\) ersetzen. Dalwigk folgt diesem Schema bei allen seinen Lösungen. Angesichts der Tatsache, dass in praktisch allen seiner Aufgaben die Aussagenliste explizit ausformuliert ist, ist es etwas ermüdend jeweils \(A(n)\) und \(A(n+1)\) nochmals aufgelistet zu bekommen. Irritierend finde ich auch, dass Dalwigk sein Rezept (erweitert um den Punkt „5. Schließe den Beweis mit der Beweisbox \(\Box\) .“) in Satz 1.1 den Induktionsalgorithmus nennt. Denn selbstverständlich kann er keine allgemeine Methode angeben, wie die Implikation \(A(n)\Rightarrow A(n+1)\) zu beweisen ist. Forsch ist auch seine Einleitung zu Kapitel 4 (Die Problemklassen). Sie kulminiert in dem Satz „Sieh dieses Kapitel als das an, was es ist: eine Sammlung (fast) aller möglichen Induktionsbeweisklassen und als Planungsinstrument für eine erfolgreiche Klausurvorbereitung!“ Die angesprochenen Problemklassen sind: Summenformeln, Produktformeln, Teilbarkeitszusammenhänge, Ungleichungen, Allgemeine Ableitungsformeln, Rekursionsformeln und Matrizen. Im Lichte dieses Anspruchs ist die inhaltliche Breite der aufgelisteten Induktionsaufgaben doch etwas dünn. So sind zum Beispiel die 23 Aufgaben zum Thema Summenformeln allesamt entweder Varianten von \(\sum_{k=1}^n k\), des Binomischen Lehrsatzes oder der geometrischen Reihe. Die Aufgaben zur Teilbarkeit erschöpfen sich darin die Teilbarkeit von diversen algebraischen Ausdrücken durch vorgegebene Zahlen zu verifizieren.
Dalwigk bedient mit seinem Aufbau, seiner Aufgabenauswahl und der Wahl seiner Lösungsmethoden das Bedürfnis vieler Studierender nach vorgeschriebenen, abarbeitbaren Prozeduren, über die man sich keine weiteren Gedanken machen muss. Außerdem suggeriert er, seine Darstellung erlaube anstrengungsfreie Aneignung des Stoffes: „Anders als in der Vorlesung [...]. Stattdessen kannst du dich entspannt zurücklehnen und die Argumentation bei einer Tasse Tee auf dich wirken lassen.“ Er teilt seine Aufgaben nach Schwierigkeitsgrad ein: für Einsteiger, Fortgeschrittene und Profis. Zu den Aufgaben für Profis schreibt er „Bei den Aufgaben für Profis geht es um teilweise sehr abstrakte Fragestellungen, bei denen ,thinking out of the box‘ nicht einfach nur ein hübscher Profilspruch für Facebook, Xing oder LinkedIn ist, sondern wirklich gelebt wird“. Hier zwei Beispiele für Profi-Aufgaben, bei denen thinking out of the box statt eines Schema-F-Induktionsbeweises gut getan hätte: Aufgabe 5.52 „Beweise, dass das um 1 verringerte Quadrat einer ungeraden Zahl immer eine gerade Zahl ist“ (Lösung: ungerade mal ungerade ist ungerade, minus 1 ergibt gerade). Aufgabe 5.68 „\(\forall n\in{\mathbb N_{\geq 2}}:\sum_{k=1}^n k>\sqrt{n}\)“ (Lösung: für \(n\geq 2\) gilt schon \(n>\sqrt{n}\)).
Noch einen Satz zu Kapitel 2 (Die Theorie hinter der vollständigen Induktion). Die Kapitelüberschrift ist wiederum etwas zu großspurig geraten. Zwar findet man dort eine Version der Peano-Axiome für die natürlichen Zahlen, aber das Prinzip der vollständigen Induktion wird daraus nicht abgeleitet. Dafür enthält das Kapitel einen längeren Exkurs zu Hilberts Hotel, dessen Bezug zum eigentlichen Thema des Buches mir nicht klar ist.
Mein Fazit zu Dalwigks Buch ist: Man kann die präsentierten Aufgaben im Übungsbetrieb des ersten Studiensemesters einsetzen, einen Mehrwert gegenüber älteren Zusammenstellungen von Übungsaufgaben mit Lösungen2 sehe ich nicht. Wirklich problematisch finde ich die Einordnung der vollständigen Induktion durch den Autor, der das ganze Prinzip in irreführender Weise als Algorithmus darstellt.
Das Buch von Andreescu und Crisan richtet sich an Oberstufenschüler (sprich Highschool) mit mathematischen Ambitionen. Es kann als Trainingsbuch zum Thema vollständige Induktion für mathematische Wettbewerbe angesehen werden. Bei vielen der besprochenen Aufgaben geben die Autoren auch an, in welchem Kontext sie gestellt wurden. Dabei sind nicht alle Aufgaben gleich anspruchsvoll. Es gibt auch Überschneidung mit der Sammlung von Dalwigk. Im Gegensatz zu Dalwigk problematisieren Andreescu und Crisan in Abschnitt 1.1.3 (Paradox of Induction) die Formulierung der zu beweisenden Aussagen ganz explizit. Auch in diesem Buch gibt es eine Kapitel-Aufteilung nach Problemklassen
2. Sums, Products, and Identities,
3. Functions and Functional Equations,
4. Inequalities,
5. Sequences and Recurrences,
6. Number Theory,
7. Combinatorics,
8. Games,
und dann noch ein Kapitel Miscellaneous Topics, aber es wird nirgendwo behauptet, dies wäre eine (fast) erschöpfende Liste. Sie ist trotzdem sehr viel breiter gestreut als die Liste von Dalwigk und auch innerhalb der einelnen Themenbereiche gibt es sehr viel mehr Variation.
Die Kapitel 2–8 beginnen jeweils mit einem Abschnitt Theory and Examples, in dem die verwendeten Begriffe eingeführt und diverse Beispiele diskutiert werden. Es folgt jeweils ein Abschnitt Proposed Problems. Im Kapitel über die Miscellaneous Topics werden Kenntnisse über die drei behandelten Themen Geometrie, Infinitesimalrechnung und Algebra vorausgesetzt.
Die in Kapitel 10 vorgeschlagenen Lösungen sind sehr viel knapper und bei weitem nicht so strukturiert wie die in [D]. Für den aufmerksamen Leser, der sich mit der jeweiligen Aufgabe beschäftigt hat, sind sie aber allemal ausreichend.
Auch das Buch von Andreescu-Crisan geht nicht auf die Rolle der vollständigen Induktion in der modernen Mathematik ein, sondern beschränkt sich auf elementare (nicht zu verwechseln mit triviale!) Beispiele. Es vermittelt aber viel stärker ein Gefühl dafür, welches Maß an Kreativität Induktionsbeweise oft erfordern.
Dieses Buch im Übungsbetrieb zu einer Erstsemestervorlesung einzusetzen erfordert sicher mehr Umsicht als der Einsatz von [D], aber wer einen bestimmten Aspekt des Induktionsprinzips illustrieren möchte, hat beste Chancen hier ein passendes Beispiel zu finden3. Für mathematisch ambitionierte Erstsemester ist der Text sicher ebenso zugänglich wie für die ursprüngliche Zielgruppe. Studierende würden es wohl eher nicht systematisch durcharbeiten, sondern nur darin schmökern. Ich kann das Buch Lehrenden und Studierenden gleichermaßen empfehlen.
1 Wieso Dalwigk wiederholt an dieser Stelle \(\exists n\in{\mathbb N}:A(n)\) schreibt, erschließt sich mir nicht, denn die
Existenz ist ja schon mit dem Induktionsanfang abgehandelt.
2 Siehe z.B. die Sammlung von Rainer Müller (©2007) auf http://www.eMath.de, auf die im deutschen
Wikipedia-Artikel zur vollständigen Induktion verwiesen wird.
3 Das Beispiel \(\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{(n+1)^2}<1\) habe ich aus Problem 1.2.
Funding Open Access funding provided by Projekt DEAL.
Open Access Dieser Artikel wird unter der Creative Commons Namensnennung 4.0 International Lizenz veröffentlicht, welche die Nutzung, Vervielfältigung, Bearbeitung, Verbreitung und Wiedergabe in jeglichem Medium und Format erlaubt, sofern Sie den/die ursprünglichen Autor(en) und die Quelle ordnungsgemäß nennen, einen Link zur Creative Commons Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Die in diesem Artikel enthaltenen Bilder und sonstiges Drittmaterial unterliegen ebenfalls der genannten Creative Commons Lizenz, sofern sich aus der Abbildungslegende nichts anderes ergibt. Sofern das betreffende Material nicht unter der genannten Creative Commons Lizenz steht und die betreffende Handlung nicht nach gesetzlichen Vorschriften erlaubt ist, ist für die oben aufgeführten Weiterverwendungen des Materials die Einwilligung des jeweiligen Rechteinhabers einzuholen. Weitere Details zur Lizenz entnehmen Sie bitte der Lizenzinformation auf http://creativecommons.org/ licenses/by/4.0/deed.de.
Quelle: Springer Verlag, Mathematische Semesterberichte, 2020, Band 67, Seiten 301-305.
Mit freundlicher Genehmigung des Verlags.
Rezension: Joachim Hilgert (Paderborn)