Transcript
Fachbereich Mathematik der Universit¨at Hamburg Dr. Hanna Peywand Kiani
WiSe 2015/2016
H¨ orsaalu ¨bung zu Blatt 2 Analysis I fu ¨r Studierende der Ingenieurwissenschaften Vollst¨ andige Induktion, Zahlen, Beweistechniken 26/27.10.2015 Das ins Netz gestellte Material zur H¨ orsaalu ¨bung soll nur die Mitarbeit w¨ahrend der Veranstaltung erleichtern. Ohne die in der Veranstaltung gegebenen zus¨atzlichen Erl¨auterungen sind diese Unterlagen unvollst¨andig (z. Bsp. fehlen oft wesentliche Voraussetzungen). Tipp– oder Schreibfehler, die rechtzeitig auffallen, werden nur mu ¨ndlich w¨ahrend der Veranstaltung angesagt. Eine Vero¨ffentlichung dieser Unterlagen an anderer Stelle ist untersagt!
Ablauf, Organisation, Material • Vorlesung: Prof. Dr. M. Hinze Di 13:15-14:45, Audimax I (BU, BVT, LUM, MB, SB, VT), Start 20.10 Do 11:30-13:00, Audimax II (AI, ET, EUT, IN, MTB), Start 22.10 ¨ • Ubungen : 36 Gruppen, ca. 20 Tutoren, Anmeldung erforderlich!, siehe Kursbelegung im Intranet der TUHH oder http://www.math.uni-hamburg.de/teaching/export/tuhh/cm/a1/1516/gruppen.html ¨ 14-t¨aglich im Wechsel mit den Ubungen zur Linearen Algebra ¨ • Ubungsaufgaben: http://www.math.uni-hamburg.de/teaching/export/tuhh/cm/a1/1516/lm.html ¨ Abgabe der Ubungsaufgaben jeweils in Gruppen von 2-4 Personen 2
¨ • Anleitungen/H¨ orsaalu ¨bung: Bru ¨cke zwischen Vorlesung und Ubung/Klausur Dr. Hanna Peywand Kiani 14-t¨aglich im Wechsel mit den H¨orsaalu ¨bungen zur Linearen Algebra Dr. Jes-Peter Zemke Mo 14:45-16:15 Uhr , Audimax I, VT, BV, EU, LUM, BU, AI, Start 19.10 Di 09:45-11:15 Uhr, Audimax I, ET, IN/IIW, MB, MTB/MEC, SB, Start: 20.10 • Alle Infos, Alles an Material zu Analysis (alte Klausuren, Sprechstunden etc.) unter http://www.math.uni-hamburg.de/teaching/export/tuhh/index.html Kiani: Tel. 42838-4940 e-mail: kiani at math.uni-hamburg.de Sprechstunden: Raum 3078, SBS95 (Lindwurm)
3
Vollst¨ andige Induktion Situation: Eine Aussage A(n) die von n ∈ N abh¨angt soll fu ¨r alle n ≥ n0 bewiesen werden. Im Fall n0 = 1 soll die Aussage also fu ¨r alle n ∈ N bewiesen werden. Beispiele a) Es gibt n! verschiedene M¨oglichkeiten n verschiedene Objekte zu sortieren. b) Fu ¨r die Summe der ersten N natu ¨rlichen Zahlen gilt: n X
k=1
k = 1 + 2 + 3 + 4 + · · · + (n − 1) + n =
n(n + 1) . 2
4
Vorgehen :
Induktionsanfang: Die Aussage wird fu ¨r n = n0 bewiesen.
Induktionsvorraussetzung: Man setzt voraus, dass die Aussage fu ¨r irgendeine Zahl N ≥ n0 aus N gilt. Man sagt hier oft N sei beliebig aber fest.
Induktionsschritt: Man beweist, dass die Aussage dann auch fu ¨r N + 1 gilt.
Nach diesen drei Schritten folgt (anschaulich nach dem Dominoprinzip, mathematisch nach PEANO), dass die Aussage fu ¨r alle natu ¨rlichen Zahlen gilt.
5
Beispiel 1: Behauptung: Fu ¨r alle n ∈ N gilt: 2n > n. Beweis: a) Anfang/Verankerung: b) Voraussetzung/Annahme: c) Schritt: Zu zeigen ist Beweisstrategie : 1) Zerlege den neuen Ausdruck (hier 2N +1 oder N + 1) in einen aus der Annahme bekannten und einen neuen Teil: 2N +1 = 2) Setzte die Information aus der Annahme ein 2N +1 = 6
3) Versuche nun durch Umformungen die Behauptung fu ¨r n = N + 1 zu beweisen. Wir haben: 2N +1 > N · 2 Ziel: 2N +1 > N + 1 Hier soll also aus dem 2 · N ein N + 1 werden: 2N +1 > N · 2
··· ≥
N +1
Zum Beispiel so: 2N +1 > 2 · N
7
Beispiel 2: (Induktionsanfang muss nicht bei 1 sein) 2n > 3n + 2,
∀ n ∈ N , n ≥ 4.
Beweis: Induktionsanfang: Fu ¨r n = n0 =
Induktionsvoraussetzung: Fu ¨r ein beliebiges festes N ∈ N mit N ≥ n0 =
gelte:
Induktionsschritt: zu zeigen ist, dass fu ¨r n = N + 1:
8
Beweis: 1) Zerlege den neuen Ausdruck hier wieder 2N +1 in einen aus der Annahme bekannten und einen neuen Teil: 2N +1 = 2N · 2 2) Setzte die Information aus der Annahme ein 2N +1 = 2N · 2 > 3) Versuche nun durch Umformungen die Behauptung fu ¨r n = N + 1 zu beweisen. Wir haben: 2N +1 > (3N + 2) · 2
Ziel: 2N +1 > 3(N + 1) + 2
9
Beispiel 3: (ein wenig komplizierter) Behauptung: Fu ¨r alle n ∈ N gilt n X
k=1
n(n + 1)(2n + 1) k = 6 2
∀n ∈ N,
Beweis: Induktionsanfang: Fu ¨r n = 1 ist die Behauptung wahr, denn es gilt 1 X k2 = k=1
Induktionsvoraussetzung:Fu ¨r ein beliebiges festes N ∈ N mit N ≥ 1 gelte
N X
k=1
N (N + 1)(2N + 1) k = . 6 2
10
Induktionsschritt: zu zeigen
N +1 X k=1
k2 =
(N + 1)((N + 1) + 1)(2(N + 1) + 1) . 6
Beweis: N +1 X k=1
k2
= 12 + 22 + · · · + N 2 + (N + 1)2 =
Zerlegung in alten und neuen Term Einsetzen der Induktionsvoraussetzung Umformen in Richtung der Behauptung
(N + 1) ((N + 1) + 1) (2(N + 1) + 1) = .✷ 6 11
Beispiel 4: (Aufgabe 1a, Vordiplomsklausur WiSe 02/03, leicht ge¨andert) n−1 X k=2
2 1 1 = − k 3 − k 2 n(n − 1)
n ≥ 3,
Induktionsanfang: n = 3. Es gilt 2 X
k=2
2 = k3 − k
und
1 1 − = 2 3(2 − 1)
Induktionsvoraussetzung: Wir nehmen mit einem festen aber beliebigem N ∈ N, N ≥ 2 an, dass die Behauptung fu ¨r N gilt. Also: N −1 X k=2
2 1 1 = − · 3 k − k 2 N (N − 1)
Induktionsschritt: N −→ N + 1) 12
Zu zeigen ist
N X
k=2 N X
k=2
2 1 1 = − k 3 − k 2 (N + 1)N
2 = k3 − k =
=
N −1 X k=2
2 k3 − k
!
1 1 − 2 N (N + 1)
2 + 3 N −N
(Zerlegen) (Induktionsvoraussetzung)
Ziel!
13
Tipps zur Aufgabe 3: Sei n ∈ N und Mn eine Menge mit n Elementen. Zeigen Sie, dass es n! Permutationen der Elemente von Mn gibt. Ohne Einschr¨ankung der Allgemeinheit (o.E.d.A.) Mn = {1, 2, 3, . . . , n}. Permutation = Umordnung Beispiel: M3 = {1, 2, 3}. Permutationen der Elemente von M :
Fakult¨at: Definiere fu ¨r n ∈ N : n! = (n + 1)! = 14
Oben gezeigt: Es gibt 3! Permutationen der Elemente von M3: 123
132
213
231
312
321
Jetzt M4 = {1, 2, 3, 4} 123
132
213
231
312
321
15
Zur Aufgabe 4: Hauptsatz der Zahlentheorie: Jede natu ¨rliche Zahl n ≥ 2 besitzt eine eindeutige Primfaktorzerlegung Primzahlen: 2, 3, 5, 7, 11, 13, 17, · · · Beispiel: 3150 = 10 · 315 = = = Allgemein fu n = pr11 · · · prmm , ¨r n ≥ 2 gilt: mit Primzahlen p1, · · · , pm und Potenzen
r1 , · · · , rm ∈ N
¨ Beweis: Ubung. 16
BEWEISSKIZZE: Vollst¨andige Induktion. Anfang mit n = 2. Induktionsvoraussetzung: Setze voraus das fu ¨rlichen ¨r ein festes beliebiges N ∈ N, N ≥ 2 alle natu Zahlen n ≤ N eine eindeutige Primfaktorzerlegung haben. Schritt: Zeige, dass dann auch N + 1 eine eindeutige Primfaktorzerlegung hat.
17
Allgemeine Beweistechniken: Zu Beweisen sei A =⇒ B – direkter Beweis A ⇐⇒ · · · =⇒ · · · B, – indirekter/Widerspruchsbeweis: fu ¨hre Annahme A ∧ ¬B zum Widerspruch. – Gegenbeispiel
Beispiel 1: direkter Beweis Fu ¨r alle reellen Zahlen x, y gilt die Dreiecksungleichung: |x| + |y| ≥ |x + y|. Seien nun a, b beliebige Zahlen aus R. Beweisen oder widerlegen Sie: |a| − |b| ≤ |a − b| ·
18
L¨ osung: Die Aussage ist wahr. Setze c = a − b. Dann gilt nach der Dreiecksungleichung: |c| + |b| ≥ |c + b| und damit
Beispiel 2: indirekter Beweis a) Beweis:
| 2ab | ≤ a2 + b2
∀ a, b ∈ R .
Annahme : Es gibt reelle Zahlen a, b mit | 2ab | > a2 + b2 . Es gilt
| 2ab | = −2ab
oder
| 2ab | = 2ab
. 19
Im ersten Fall erh¨alt man mit der Annahme: −2ab > a2 + b2 ⇐⇒ 0 > a2 + b2 + 2ab Der zweite | 2ab | = 2ab fu ¨hrt analog zu einem Widerspruch! b)
√
2 ist irrational.
Beweis:
20
Beispiel 3: Gegenbeispiele a) Behauptung: Fu ¨r alle a, b, c, d ∈ R: a > b, c > d
⇐⇒
ac > bd,
Die Aussage ist im allg. falsch. Gegenbeispiel: a = −1, b = −2, c = −3, d = −4,
21
b) Behauptung: Fu ¨r alle n ∈ N gilt n=1:
5 · 12 − 7 · 1 + 4 2 = . k = 1 =1 = 2 2
2 X
2 5 · 2 10 −7·2+4 2 2 2 = . k = 1 +2 =5 = 2 2
k=1
n=3:
k=1
5n2 − 7n + 4 k = . 2 2
1 X
k=1
n=2:
n X
3 X
2
2
k2 =
k=1
n=4:
4 X
k2
k=1
Merke: Die Negation von
∀ x ∈ M : A(x) ist
∃ x ∈ M : ¬A(x).
22
