Vollständige Induktion PDF

Preview

Summary

Vollständige Induktion...

Description

Vorlesung 4

Vollst¨ andige Induktion In dieser Vorlesung lernen wir das Prinzip der vollst¨andigen Induktion kennen. Als Anwendung beweisen wir einige n¨utzliche Summenformeln, sowie den sehr wichtigen binomischen Lehrsatz.

4.1

Induktion

Wir werden mehrfach vor der Aufgabe stehen, eine Aussage zu beweisen, die von n ∈ N abh¨ angt. Beispiele solcher Aussagen sind: P n+1 1) Die geometrische Summe: F¨ur alle nat¨ urlichen Zahlen n ≥ 0 ist nk=0 q k = 1−q 1−q , wobei q 6= 1 ist. P n(n+1) 2) F¨ ur alle nat¨ urlichen Zahlen n ≥ 1 gilt nk=1 k = 2 3) F¨ ur alle nat¨ urlichen Zahlen n ≥ 1 gilt: n Elemente lassen sich auf n! verschiedene Arten anordnen. Oft lassen sich solche Aussagen mit vollst¨andiger Induktion beweisen. Eine Eigenschaft der nat¨urlichen Zahlen von fundamentaler Wichtigkeit ist die folgende, nicht besonders ¨uberraschende Feststellung: Wenn man bei 0 beginnend immer ” eins weiterz¨ahlt“, erreicht man jede nat¨urliche Zahl. Wenn man also eine Aussage A(n) hat, die f¨ur n = 0 wahr ist und beim Weiterz¨ahlen“ wahr bleibt, dann gilt sie f¨ur alle ” nat¨ urlichen Zahlen. Das ist das Prinzip der vollst¨andigen Induktion. Das gleiche Prinzip gilt nat¨urlich auch, wenn man mit einem Startwert“ n0 ∈ N ” beginnt und dann weiterz¨ahlt“. Die Aussage gilt dann f¨ur alle n ≥ n0 . ” Vollst¨ andige Induktion: Um eine Assage A(n) f¨ur alle n ∈ N mit n ≥ n0 (also ab einem Startwert n0 ) mit vollst¨andiger Induktion zu beweisen, gehen wir wie folgt vor: 1) Induktionsanfang: Wir zeigen, dass A(n0 ) gilt. 2) Induktionsschritt: Wir zeigen A(n) ⇒ A(n + 1)“, also dass wenn A(n) wahr ist, ” auch A(n + 1) wahr ist. Anschließend ist die Aussage f¨ur alle n ≥ n0 gezeigt. 33

Zum besseren Verst¨andnis teilt man den Induktionsschritt noch in zwei oder drei Teile, n¨ amlich 1) die Induktionsvoraussetzung: Wir nehmen an, dass A(n) f¨ur ein n ≥ n0 richtig ist, 2) die Induktionsbehauptung: Dann gilt auch A(n + 1)“, ” 3) den eigentlichen Induktionsschritt, bei dem die Induktionsbehauptung unter Benutzung der Induktionsvoraussetzung bewiesen wird. Die Induktionsbehauptung (IB) muss man nicht aufschreiben, aber es kann beim Beweisen helfen, wenn man sich noch einmal klar macht, wohin man eigentlich m¨ochte. F¨ur die Schritte bei der vollst¨andigen Induktion finden Sie manchmal auch andere Namen: Statt Induktionsanfang (IA) sagt man auch Induktionsverankerung, statt Induktionsvoraussetzung (IV) auch Induktionsannahme, und statt Induktionsschritt (IS) auch Induktionsschluss. Als erstes Beispiel beweisen wir noch einmal die Formel f¨ur die geometrische Summe (siehe Satz 2.14). Beispiel 4.1. Sei q 6= 1 eine reelle oder komplexe Zahl. Wir zeigen mit vollst¨andiger P n+1 Induktion, dass nk=0 q k = 1−q ur alle nat¨ urlichen Zahlen n gilt. f¨ 1−q P0 0+1 1−q k • Induktionsanfang: F¨ ur n = 0 ist k=0 q = q 0 = 1 = 1−q = 1−q 1−q . • Induktionsvoraussetzung: Die Behauptung sei f¨ur ein n ≥ 0 wahr, d.h. es gilt Pn 1−q n+1 k k=0 q = 1−q . • Induktionsschritt: Wir zeigen jetzt, dass die Behauptung auch f¨ur n + 1 wahr ist. Dazu rechnen wir: n+1 X k=0

qk =

n X

IV

q k + q n+1 =

k=0

1 − q n+2 1 − q n+1 q n+1 − q n+2 1 − q n+1 + q n+1 = = + . 1−q 1−q 1−q 1−q

Beispiel 4.2. Wir zeigen mit vollst¨andiger Induktion, dass n X

k = 1 +2 +... +n =

k=1

n(n + 1) 2

f¨ ur alle n ∈ N, n ≥ 1, P1gilt. 1(1+1) IA: F¨ur n = 1 ist k=1 k = 1 = 2 . Pn IV: F¨ur ein n ∈ N, n ≥ 1, gelte k=1 k = 1 + 2 + . . . + n = IS: Wir zeigen, dass die Behauptung auch f¨ur n + 1 gilt: n+1 X

k=

k=1

n X k=1

=

IV

k + (n + 1) =

n(n+1) . 2

n(n + 1) 2(n + 1) n(n + 1) + (n + 1) = + 2 2 2

(n + 1)(n + 2) n(n + 1) + 2(n + 1) . = 2 2

Nach dem Prinzip der vollst¨andigen Induktion gilt die Formel dann f¨ur alle n ≥ 1. Die Formel gilt sogar f¨ ur alle n ∈ N, denn f¨ur n = 0 ist die leere Summe = 0 und damit P0 0(0+1) . k = 0 = k=1 2 34

Beispiel 4.3. Wir zeigen mit vollst¨andiger Induktion: F¨ur alle n ∈ N, n ≥ 1, gilt  n  Y k+1 k (n + 1)n = . k n! k=1 IA: F¨ur n = 1 gilt    1  Y k+1 k 21 1+1 1 =2= . = k 1! 1 k=1 k (n+1)n  Q = n! . IV: F¨ur ein n ∈ N, n ≥ 1, gelte nk=1 k+1 k IS: Wir zeigen, dass die Aussage dann auch f¨ur n + 1 gilt. Es ist   n+1   n+1 n  n Y  k + 1 k Y n + 2 n+1 k+1 k n+1+1 IV (n + 1) = = · n! n+1 n+1 k k k=1

k=1

(n + 2)n+1 (n + 2)n+1 = . n!(n + 1) (n + 1)! k Q0  =1= Die Formel gilt auch f¨ur n = 0, da (leeres Produkt) k=1 k+1 k =

(0+1)0 0!

.

Beispiel 4.4 (Bernoulli-Ungleichung). Sei x eine reelle Zahl mit x ≥ −1. Dann gilt f¨ur alle n ∈ N die Ungleichung (1 + x)n ≥ 1 + nx. Das weisen wir mit vollst¨andiger Induktion nach. IA: F¨ur n = 0 ist (1 + x)0 = 1 ≥ 1 = 1 + 0 · x. IV: F¨ur ein n ∈ N sei (1 + x)n ≥ 1 + nx wahr. IS: Wir zeigen die Behauptung f¨ur n + 1. Es gilt 1 + x ≥ 0, und nach Induktionsvoraussetzung gilt (1 + x)n ≥ 1 + nx. Daher erhalten wir (1 + x)n+1 = (1 + x)n (1 + x) ≥ (1 + nx)(1 + x) = 1 + x + nx + nx2 = 1 + (n + 1)x + nx2 ≥ 1 + (n + 1)x. Bei der letzten Absch¨atzung haben wir verwendet, dass nx2 ≥ 0 ist.

Beispiel 4.5. Wir beweisen mit vollst¨andiger Induktion, dass f¨ur jedes n ∈ N, n ≥ 1, die Anzahl der m¨oglichen Reihenfolgen (= Anordnungen = Permutationen) von n Elementen gleich n! ist. Wir schreiben zur Abk¨urzung die Aussage A(n): n Elemente lassen sich ” auf genau n! verschiedene Weisen (linear) anordnen.“ IA: Ein einziges Element l¨asst sich auf eine Weise anordnen, also ist A(1) wahr. IV: A(n) ist f¨ur ein n ∈ N, n ≥ 1, wahr. IS: Wir zeigen, dass dann auch A(n + 1) wahr ist. Dazu lassen wir von den n + 1 Elementen eines weg. Die verbleibenden n Elemente k¨onnen wir nach der Induktionsannahme auf n! verschiedene Weisen anordnen. In jede dieser Anordnungen kann das weggelassene Element an n + 1 Stellen eingef¨ugt werden (nach einem der n Elemente oder vor dem ersten). Also ist die gesuchte Anzahl m¨oglicher Anordnungen (n + 1) · n! = (n + 1)!. 35

4.2

Binomischer Lehrsatz

Wir beweisen nun den binomischen Lehrsatz, also die Verallgemeinerung der Binomischen Formel (a + b)2 = a2 + 2ab + b2 auf (a + b)n mit beliebigem n ∈ N. Dazu brauchen wir einige Vorbereitungen. Definition 4.6. F¨ ur n, k ∈ N und 0 ≤ k ≤ n definieren wir den Binomialkoeffizienten   n! n := . k k !(n − k )! F¨ur k 6= 0 ergibt das   n(n − 1) · . . . · (n − k + 1) n , = k 1 · 2 · ... · k wobei Z¨ ahler und Nenner ein Produkt aus k Faktoren sind. Im Spezialfall k = 0 ist n  n! n! = 1. Auch f¨ = ur k = n ist nn = 1. 0 0!(n−0)! = n! F¨ur die Binomialkoeffizienten gilt     n! n n = = . k k!(n − k)! n−k Wir rechnen weiter nach (auf Hauptnenner bringen und vereinfachen), dass     n n! n n! + + = (k − 1)!(n − k + 1)! k !(n − k )! k−1 k n!k n!(n − k + 1) = (4.1) + k!(n − k + 1)! k!(n − k + 1)!   n!(n + 1) (n + 1)! n+1 = = = . k!(n − k + 1)! k k!(n − k + 1)!   beDie Formel (4.1) ist eine Rekursionsformel“: Wenn man alle nk f¨ur ein n schon n+1  ” . Eine rechnet hat, bekommt man daraus ganz einfach die Binomialkoeffizienten k Illustration dieser Formel gibt das Pascalschen Dreieck : 0  1 0 1 1  1 1 1 0 2 2 2  1 2 1 2 1 0      3 3 3 3 1 3 3 1 3 0 1 2 4  4 4 4  4  1 4 6 4 1 4 3 2 1 0

Interpretiert man k als Spalten- und n als Zeilenindex in diesem Dreieck, so ist jeder Eintrag dieSumme  beiden dar¨uber liegenden Eintr¨age (abgesehen von den ”Rand der eintr¨agen“ 0n und nn ). 36

Satz 4.7 (Binomischer Lehrsatz). F¨ ur alle n ∈ N und reelle oder komplexe a, b gilt: n   X n n−k k (a + b)n = a b . k k=0

ur n = 2 ist das die bekannte binomische Formel (a + b)2 = a2 + 2ab + b2 , f¨ur n = 3 F¨ gilt (a + b)3 = a3 + 3a2 b + 3ab2 + b3 . F¨ ur n = 5 haben wir die Binomialkoeffizienten (n¨achste Zeile des Pascalschen Dreiecks):             5 5 5 5 5 5 = 5, = 10, = 1, = 1, = 10, = 5, 4 3 5 0 2 1 daher ist

(a + b)5 = 1a5 + 5a4 b + 10a3 b2 + 10a2 b3 + 5ab4 + 1b5 .

Beweis. Wir beweisen den binomischen Lehrsatz mit vollst¨ a ndiger Induktion. IA: F¨ ur n = 0 ist ! ! 0 X 0 0−k k 0 0 a b = a0 b0 = 1 = (a + b) . k 0 k=0 Pn   IV: F¨ ur ein n ∈ N gelte (a + b)n = k=0 kn an−k bk . IS: Wir zeigen mit der Induktionsvoraussetzung, dass die Behauptung auch f¨ ur n + 1 gilt, also dass ! n+1 X n + 1 n+1−k k n+1 a b . ( a + b) = k k=0 Dazu rechnen wir:

n+1

(a + b)

! n X n = (a + b)(a + b) = (a + b) an−k bk k k=0 ! ! n n X n n+1−k k X n n−k k+1 = a b + a b . k k n IV

k=0

k=0

In der zweiten Summe machen wir eine Indexverschiebung und fassen zusammen: ! ! n+1 n X n n n+1−k k X n+1 an+1−k bk a b + ( a + b) = k − 1 k k=1 k=0 ! ! n n X X n n n+1 n+1−k k an+1−k bk + bn+1 a b + =a + k−1 k k=1 k=1 ! !! n X n n n+1 + an+1−k bk + bn+1 . =a + k k−1 k=1   n+1  Mit (4.1) und n+1 = 1 = erhalten wir schließlich n+1 0 ! ! ! n n + 1 n+1 n + 1 n+1 X n + 1 n+1−k k n+1 a b + a + b (a + b) = k 0 n+1 k=1 ! n+1 X n + 1 n+1−k k = a b . k k=0 Damit ist der binomische Lehrsatz bewiesen.

37...