Themenbereiche mit Youtubelinks PDF

Preview

Summary

Hier finden sich zu den einzelnen Lernthemen Youtubelinks...

Description

Vollständige Induktion

n

Vollständige Induktion von Summen: Man hat am Anfang eine Annahme, die es zu beweisen gilt:

k ³= ∑ k=1

n ²(n+1) ² ∀n ϵ N 4

heißt: Jede Zahl hoch 3

von 1 bis n ist dasselbe, wie n² mal (n+1) ² durch n. Dies gilt für alle (Ɐ) n die Elemente der natürlichen Zahlen sind. Zuerst kommt der Induktionsanfang: Man setzt hier die kleinste natürliche Zahl ein (meistens 1 oder 0) für die die Induktion erfüllt sein soll. Bei diesem Beispiel:

1

1² (1+1) ² 4 entspricht 1= also 1. k ³= ∑ 4 4 k=1

Damit wäre der Induktionsanfang bewiesen. Nun kommt die Induktionsvoraussetzung: Da wir im

Induktionsanfang gesehen haben, dass die 1 funktioniert können wir hier einfach die Formel hinschreiben für: „Es gibt (ⱻ) eine natürliche Zahl, für die die Induktion erfüllt ist:

n

∃ n ϵ N : ∑ k ³= k=1

n ²(n+1) ² 4

. Der dritte Schritt ist die Induktionsbehauptung: Für diese gilt, dass nicht nur für n=1 die Induktion gilt, sondern auch für

n+1 seinen Nachfolger, also n+1. Wir schreiben also einfach die Behauptung hin, die wir beweisen wollen:

∑ k ³= (n +1)²4(n +2)²

. Der vierte Schritt wird

k=1

Induktionsschritt genannt. Dieser beginnt immer mit dem ersten Teil der Induktionsbehauptung = dem ersten Teil der Induktionsvoraussetzung + dem Summanden der

n+1

n

k=1

k=1

∑ k ³=∑ k ³+(n+1)³

Induktionsbehauptung eingesetzt in die Variable. In diesem Fall:

, da n+1 immer die letzte Zahl der Suche ist (die Summe geht von

k=1 bis k=n+1). In diesem Fall ist es die letzte Zahl von k, also k³. Nun werden die beiden Summenregeln ausgetauscht, d.h. es werden die beiden Teile hinter dem Gleichheitszeichen gleichgesetzt. Wir nehmen also den zweiten Teil der Induktionsbehauptung, sowie den zweiten Teil der Induktionsvoraussetzung uns ganz wichtig von der

(n+1)² (n+2)² n ²(n+ 1)² +(n+ 1)³ = 4 4

Behauptung den letzten Term hinzufügen, also die letzte Zahl:

. Nun kann mittels Äquivalenzumformung die

Formel gekürzt werden. Dies geschieht in diesem Fall mittels Wegkürzen von (n+1) ² und Multiplikation von vier. Das Ergebnis: (n+2) ² = n² + 4(n+1) => n² + 4n + 4 = n² + 4n + 4. Damit ist Aufgabe erfüllt, da durch die Äquivalenzformung der Wahrheitsgehalt des Induktionsschrittes bewiesen ist, d.h. es ist bewiesen, dass jede n+1 der natürlichen Zahlen erfüllt ist. Wenn wir jetzt noch einen Schritt zurückgehen zum Induktionsanfang und sehen, dass n=1 erfüllt wurde, dann ist auch n=2 bewiesen, da wir dies gerade geschafft haben, mit dem Beweis das jedes n+1 wahr ist. Vollständige Induktion von Ungleichungen: Diese funktioniert gleich wie die vollständige Induktion von Summen, bis auf einen kleinen Unterschied im vierten Schritt, dem Induktionsschritt. Als Beispiel nehmen wir die Bernoulli Ungleichung:

n A ( n) :(1+ x ) ≥ 1+ nx x >−1, n ≥ 0

. Im Induktionsanfang wird auch hier die kleinste natürliche Zahl eingesetzt, um zu schauen, ob die Induktion

erfüllt ist (man setzt hier z.B. die 0 ein und erhält 1 ≥ 1, was der Wahrheit entspricht. Man schreibt dann die Induktionsvoraussetzung:

∃ n ϵ N , n ≥ 0:(1+ x)n ≥1+ nx . Nun kommt wieder die Induktionsbehauptung, in der wir schauen, ob die Induktion auch für den Nachfolger von n wahr ist: (1+x)n +1 ≥ 1+(n+1) x . Nun kommt auch hier der Induktionsschritt: Wir nehmen den ersten Term der Induktionsbehauptung: (1+ x)n +1 und versuchen ihn nach dem ersten Term der Induktionsvoraussetzung aufzusplitten: (in diesem Fall nach (1+x)n ). Dies ist möglich, denn (1+x)n∗(1+ x )1 n +1 ist dasselbe wie . Da laut Induktionsvoraussetzung (1+ x) (1+ x)n ≥1+ nx , ist auch (1+x)n∗ ( 1+ x )1 ≥1+nx∗(1+ x )1 . Nun umzuformen. Die gelingt fast, müssen wir noch versuchen den Teil hinter dem ≥ in demselben Teil hinter dem ≥ aus der Induktionsbehauptung, also 1+( n+1 ) x 1 wenn man 1+nx∗( 1+ x ) ausmultipliziert in 1 + (n+1) x + nx². Es ist nur mehr das nx² „Zuviel“. Das dieser Term aber auf jeden Fall größer ist, sieht man aus den Angaben, da x>−1und n ≥0 ist. Somit ist nx² immer eine positive Zahl und 1 + (n+1) x + nx² ist immer größer als 1 + (n+1) x. Damit ist die Annahme erfüllt und nicht nur n, sondern auch sein Nachfolger n+1 haben beide die Annahmen erfüllt und die Induktion ist wahr. Vollständige Induktion von Produkten: Auch hier

∏ ( 1− k1 )= n1 n ϵ N , n ≥2 n

müssen wir die folgenden 4 Schritte bei einem Beispiel machen:

. Setzen wir nun Induktionsanfang die kleinste Zahl 2 ein,

k=2 so ist das Ergebnis

1 1 = 2 2

n

. Damit ist das geklärt. Nun wird die Induktionsvoraussetzung hingeschrieben:

( )

∃ n ϵ N , n ≥2 : ∏ 1− 1 = 1 k n k=2

. Der

n+1

dritte Schritt ist wieder die Induktionsbehauptung, dass der Nachfolger von n, auch wahr ist:

1 1 1− )= ∏ ( k n+1 k=2

. Nun kommt wieder der

Induktionsschritt: Wir nehmen vor dem Gleichheitszeichen den ersten Term der Induktionsbehauptung und hinter dem Gleichheitszeichen den ersten Term der

∏( n+1

Induktionsvoraussetzung, also:

k=2

) ( ) ∏ ( 1− k1 )=∏ (1− 1k )∗(1− 1n ) n

1−

1 1 =∏ 1− k k =2 k

. Um dies nun zu beweisen, spalten wir wieder den ersten Term auf. Um von n auf n+1 zu kommen

n+1

k=2

1 n+1

∏ ( 1− k1 )∗(1− 1n ) n

und

k=2

mit

1 1 ∗(1− ) n n+1

∏ ( 1− k1 ) n+1

n

wird an den zweiten Term noch das fehlende Teil angehängt:

. Nachdem wir ja

k =2

abkürzen können, bleibt nur mehr der Term mit

mit

k=2

1 1 1 = ∗(1− ) n+1 n n+1

Ausgerechnet, bzw. ausgekürzt ergibt dies: n=n. Somit ist auch diese Behauptung richtig. Und wieder ist bewiesen, dass die Induktion für und für n+1 richtig ist.

....