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).[br]Die Übungsaufgaben wurden entweder dem Skript entnommen oder stammen aus den Hausaufgaben zur Vorlesung "Analysis I" von Herrn Prof. Walcher im WS 2015/16.

[color=#0000ff][size=200]Das Induktionsprinzip[/size][/color][br][br]Eine grundlegende Eigenschaft der Menge [math]\mathbb{N}[/math] der natürlichen Zahlen ist das Induktionsprinzip:[br][br]Es sei M eine Teilmenge von [math]\mathbb{N}[/math] mit folgenden Eigenschaften:[br](i) 1[math]\in[/math]M[br](ii) Für alle n[math]\in[/math]M gilt auch n+1[math]\in[/math]M.[br]Dann gilt M=[math]\mathbb{N}[/math].[br][br]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 [math]\mathbb{N}[/math].[br]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:[br]1. Der erste Stein muss umfallen.[br]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.

[size=100][size=200][color=#0000ff]Motivation[br][/color][/size][/size][size=85][size=100]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:[/size][/size][math]1+2+...+100=\sum_{k=1}^{100}k=\frac{100\left(100+1\right)}{2}=5050[/math][size=150] [br][size=100]Diese Formel lässt sich auch verallgemeinern für ein[/size] [math]n\in\mathbb{N}[/math]: [math]\sum_{k=1}^nk=\frac{n\left(n+1\right)}{2}[/math]. [br][size=100]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.[br][br][/size][color=#0000ff][size=200]Das Beweisverfahren der vollständigen Induktion[/size][/color][br][/size][br]Für jede natürliche Zahl [math]k[/math] sei eine Aussage [math]A_k[/math] gegeben und es gelte:[br](i) [math]A_1[/math] ist wahr.[br](ii) Für ein beliebiges aber festes [math]n\in\mathbb{N}[/math] ist [math]A_{n+1}[/math] wahr, wenn [math]A_n[/math] wahr ist. [br]Dann sind alle Aussagen [math]A_k[/math], [math]k\in\mathbb{N}[/math] wahr.[br][br][color=#0000ff][color=#000000]Üblicherweise[/color] [/color]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.[br][br][color=#0000ff][size=200]Beispiel 1: "Der kleine Gauss"[/size][/color][br][br][math]A_n[/math]: [math]\sum_{k=1}^nk=\frac{n\left(n+1\right)}{2}[/math] für alle [math]n\in\mathbb{N}[/math].[br][size=50]Entnommen aus dem Skript zur Vorlesung "Analysis I".[/size][br]Beweis per vollständiger Induktion über [math]n\in\mathbb{N}[/math]:[br](i) [math]A_{_1}[/math]: [math]\sum_{k=1}^1k=1=\frac{2}{2}=\frac{1\left(1+1\right)}{2}[/math] ist wahr.[br](ii) Angenommen, [math]A_n[/math] sei wahr für ein beliebiges aber festes [math]n\in\mathbb{N}[/math]. Dann ist[br][math]A_{n+1}[/math]: [math]\sum_{k=1}^{n+1}k=\left(n+1\right)+\sum_{k=1}^nk=\left(n+1\right)+\frac{n\left(n+1\right)}{2}[/math] [br]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:[br][br][math]\left(n+1\right)+\frac{n\left(n+1\right)}{2}=\frac{2\left(n+1\right)}{2}+\frac{n\left(n+1\right)}{2}=\frac{\left(2\left(n+1\right)+n\left(n+1\right)\right)}{2}=\frac{\left(n+2\right)\left(n+1\right)}{2}=\frac{\left(n+1\right)\left(\left(n+1\right)+1\right)}{2}[/math][br][br]Damit ist die Aussage nach dem Prinzip der vollständigen Induktion bewiesen.[br]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.[br][br][color=#0000ff][size=200]Beispiel 2:[/size] [/color][br][math]A_n[/math]: [math]\sum_{k=1}^n\frac{1}{k\left(k+1\right)}=1-\frac{1}{n+1}[/math] für alle [math]n\in\mathbb{N}[/math][br][size=50]Entnommen aus den Übungen zur Vorlesung "Analysis I".[/size][br]Beweis per vollständiger Induktion über [math]n\in\mathbb{N}[/math]:[br](i) [math]A_1[/math]: [math]\sum_{k=1}^1\frac{1}{k\left(k+1\right)}=\frac{1}{1\left(1+1\right)}=\frac{1}{2}=1-\frac{1}{2}=1-\frac{1}{1+1}[/math] ist wahr.[br](ii) Angenommen, [math]A_{_n}[/math] sei wahr für ein beliebiges aber festes [math]n\in\mathbb{N}[/math]. Dann ist[br][br][math]A_{n+1}[/math]: [math]\sum_{k=1}^{n+1}\frac{1}{k\left(k+1\right)}=\frac{1}{\left(n+1\right)\left(\left(n+1\right)+1\right)}+\sum_{k+1}^n\frac{1}{k\left(k+1\right)}=\frac{1}{\left(n+1\right)\left(n+2\right)}+1-\frac{1}{n+1}[/math][br][br]Im letzten Schritt wurde hier unsere Annahme verwendet. [size=100][color=#0000ff]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[/color][/size]. In diesem Beispiel könnte das so aussehen:[br][br][math]\frac{1}{\left(n+1\right)\left(\left(n+1\right)+1\right)}+\sum_{k+1}^n\frac{1}{k\left(k+1\right)}=^{\left(IV\right)}\frac{1}{\left(n+1\right)\left(n+2\right)}+1-\frac{1}{n+1}[/math][br][br]Nun können wir weiter umformen und versuchen, die beiden Brüche auf einen Nenner zu bringen:[br][br][math]=\frac{1}{\left(n+1\right)\left(n+2\right)}+1-\frac{\left(n+2\right)}{\left(n+1\right)\left(n+2\right)}=1-\frac{\left(n+1\right)}{\left(n+1\right)\left(n+2\right)}=1-\frac{1}{n+2}=1-\frac{1}{n+1+1}[/math][br][br]Damit ist die Aussage nach dem Prinzip der vollständigen Induktion bewiesen.[br][b]__________________________________________________________________________________________________________________[/b]

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.[br][br]Du solltest versuchen, in der vorgegebenen Zeit mindestens vier Aufgaben zu bearbeiten (am besten Übung 2, 3, 5 und 6).