Google Classroom
GeoGebraGeoGebra Classroom

Das Induktionsprinzip

Das folgende Arbeitsblatt basiert auf dem Impact Skript (Impact Schülerarbeitsheft, Grundlagenkurs - Folgen und Reihen - Komplexe Zahlen, Erhard Kramer, Johanna Heitzer, Sebastian Walcher, u.a., 2018, S. 121-128). Die Übungsaufgaben wurden entweder dem Skript entnommen oder stammen aus den Hausaufgaben zur Vorlesung "Analysis I" von Herrn Prof. Walcher im WS 2015/16.
Das Induktionsprinzip Eine grundlegende Eigenschaft der Menge der natürlichen Zahlen ist das Induktionsprinzip: Es sei M eine Teilmenge von mit folgenden Eigenschaften: (i) 1M (ii) Für alle nM gilt auch n+1M. Dann gilt M=. Das Induktionsprinzip beschreibt also zunächst die Eigenschaft, dass man mit der Eins anfangen kann und die ganzen natürlichen Zahlen erhält, indem man immer einen Schritt weiter geht.
Grundsätzlich ist das Induktionsprinzip also eine Aussage über Teilmengen von . Anhand von Dominosteinen können wir uns nun vorstellen, wie daraus ein Beweisprinzip wird. Diese Dominosteine sollen für die unendlich vielen natürlichen Zahlen stehen. Damit alle Steine umfallen, braucht man zwei Bedingungen: 1. Der erste Stein muss umfallen. 2. Betrachtet man irgendeinen beliebigen aber festen Stein und nimmt an, dass dieser umfällt, so muss man folgern können, dass sein Nachfolger ebenfalls umfällt.
Quelle: Impact Skript, S. 122.
Quelle: Impact Skript, S. 122.
Motivation Man erzählt sich, dass der berühmte Mathematiker Carl Friedrich Gauss (1777-1855) die folgende Aussage in seiner Schulzeit bewiesen haben soll, als sein Lehrer den Schülern die Aufgabe stelle, alle Zahlen von 1 bis 100 zu addieren. Er überlegte sich, dass es dazu bestimmt eine Formel gibt und stellte die folgende auf: Diese Formel lässt sich auch verallgemeinern für ein : . Nun musste er nur noch seinem Lehrer beweisen, dass diese Formel auch stimmt. Dafür nutzte er nach den Erzählungen die vollständige Induktion. Der Beweis folgt nach einer kurzen allgemeinen Definition. Das Beweisverfahren der vollständigen Induktion Für jede natürliche Zahl sei eine Aussage gegeben und es gelte: (i) ist wahr. (ii) Für ein beliebiges aber festes ist wahr, wenn wahr ist. Dann sind alle Aussagen , wahr. Üblicherweise spricht man von (i) als dem Induktionsanfang und von (ii) als dem Induktionsschritt. Im Induktionsanfang wird die Behauptung zunächst für den ersten Wert gezeigt, für den sie gelten soll. Danach folgt die Induktionsannahme oder Induktionsvermutung, in der angenommen wird, dass die Aussage für eine beliebige natürliche Zahl gelten soll. Zuletzt folgt der Induktionsschritt, in dem die Annahme auch für die folgende Zahl gezeigt wird. Beispiel 1: "Der kleine Gauss" : für alle . Entnommen aus dem Skript zur Vorlesung "Analysis I". Beweis per vollständiger Induktion über : (i) : ist wahr. (ii) Angenommen, sei wahr für ein beliebiges aber festes . Dann ist : Hier wurde im ersten Schritt der letzte Term aus der Summe herausgezogen und danach unsere Induktionsannahme verwendet, die besagt, dass die Aussage für ein festes n gelten soll. Nun können wir weiter umformen: Damit ist die Aussage nach dem Prinzip der vollständigen Induktion bewiesen. Nun folgt noch ein weiteres, komplizierteres Beispiel, um dich auf die folgenden Übungsaufgaben vorzubereiten und dir schon ein paar Tipps an die Hand zu geben. Beispiel 2: : für alle Entnommen aus den Übungen zur Vorlesung "Analysis I". Beweis per vollständiger Induktion über : (i) : ist wahr. (ii) Angenommen, sei wahr für ein beliebiges aber festes . Dann ist : Im letzten Schritt wurde hier unsere Annahme verwendet. Es ist sehr wichtig, dass du in deinen Beweisen immer kennzeichnest, an welcher Stelle du die Induktionsannahme verwendest. Schreibe am besten einfach über das Gleichzeichen von dem Schritt, in dem du sie verwendest, ein kleines IA oder IV für Induktionsannahme oder Induktionsvoraussetzung. In diesem Beispiel könnte das so aussehen: Nun können wir weiter umformen und versuchen, die beiden Brüche auf einen Nenner zu bringen: Damit ist die Aussage nach dem Prinzip der vollständigen Induktion bewiesen. __________________________________________________________________________________________________________________

Kurze Verständnisaufgabe (Aufgabe 1) Welche der folgenden Aussagen können per Induktion gezeigt werden?

Select all that apply
  • A
  • B
  • C
  • D
Check my answer (3)

Wenn du bei dieser Aufgabe Probleme hast, schau dir nochmal die Definitionen zu Beginn der Lernumgebung an. Wenn dir das auch nicht weiter hilft, schau hier in die Lösung für einen kleinen Tipp.

Für die folgenden Übungsaufgaben nimmst du dir am besten ein Blatt und einen Stift und rechnest die Aufgaben per Hand. Danach kannst du deine Lösung mit der Musterlösung vergleichen. Du solltest versuchen, in der vorgegebenen Zeit mindestens vier Aufgaben zu bearbeiten (am besten Übung 2, 3, 5 und 6).

Übungsaufgabe 2 Beweise mithilfe der vollständigen Induktion die folgende Aussage: Für alle und gilt : . Wenn du einen Tipp brauchst, kannst du hier an dieser Stelle die Lösung anklicken. Entnommen aus den Übungen zur Vorlesung "Analysis I".

Lösung zu Übungsaufgabe 2

Übungsaufgabe 3 Jetzt, wo du schon ein bisschen Übung hast, erkennst du den Fehler im folgenden Beweis? Die Aussage : ist offensichtlich für jedes falsch. Trotzdem funktioniert folgender "Beweis": Nimmt man an, dass wahr ist, so gilt also . Addiert man nun auf beiden Seiten der Ungleichung eine 1, so erhält man: , also ist wahr. Stimmt also doch etwas nicht mit dem Induktionsprinzip? Oder liegt irgendwo ein Fehler begraben? Entnomen aus dem Impact-Skript, S. 125.

Übungsaufgabe 4 Dies ist eine schwere Aufgabe, wenn dir die vorherigen Aufgaben leicht gefallen sind, versuche sie zu lösen. Wenn du noch mehr Übung brauchst, überspringe diese Aufgabe. Mithilfe des Induktionsprinzips können aber nicht nur Gleichheiten, sondern auch Ungleichheiten bewiesen werden: Zeige mithilfe der vollständigen Induktion die folgende Aussage für und : : Entnommen aus den Übungen zur Vorlesung "Analysis I".

Übungsaufgabe 5 Mithilfe der vollständigen Induktion können auch Eigenschaften von Funktionen bewiesen werden. Zeige mithilfe der vollständigen Induktion die folgende Aussage. Für alle gilt : ist die k-te Ableitung von . Entnommen aus dem Impact-Skript, S. 124.

Übungsaufgabe 6 Beweise mithilfe der vollständigen Induktion folgende Aussage: Für alle ist die Ableitung von gegeben durch . Entnommen aus dem Impact-Skript, S. 125.

Beispiel 3 Wenn du denkst, dass du für die folgenen Aufgaben Hilfe brauchst, schaue dir zunächst das Beispiel an, bevor du weiter rechnest. Versuche aber die Aufgaben zuerst ohne Hilfe zu lösen und schau dir das Beispiel nur an, wenn du es brauchst!

Übungsaufgabe 7 (Zusatzaufgabe) Beweise mithilfe der vollständigen Induktion folgende Aussage: Für alle gilt : (" teilt ()"). Wenn du einen Tipp brauchst, kannst du an dieser Stelle die Lösung anklicken. Entnommen aus dem Impact-Skript, S. 123.

Lösung zu Übungsaufgabe 7

Übungsaufgabe 8 (Zusatzaufgabe, schwer) Beweise mithilfe der vollständigen Induktion die folgende Aussage: Für alle gilt : . Tipp: Aufgepasst! Eventuell kannst du bei den Umformungen im Induktionsschritt die Aussage nicht für alle zeigen! Entnommen aus den Übungen zur Vorlesung "Analysis I".