Das Induktionsprinzip

Author:herzwol, Lena Hans

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

M (ii) Für alle n

M gilt auch n+1

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

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
für alle
B
für alle
C
für alle
D
für alle

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.

Check my answer

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

Check my answer

Lösung zu Übungsaufgabe 2

Check my answer

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

Check my answer

Ü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".

Check my answer

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

Check my answer

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

Check my answer

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!

Check my answer

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

Check my answer

Lösung zu Übungsaufgabe 7

Check my answer

Ü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".

Check my answer

Das Induktionsprinzip

Lösung zu Übungsaufgabe 2

Lösung zu Übungsaufgabe 7

New Resources

Discover Resources

Discover Topics