Loes7 - Hausaufgaben und Lösungen PDF

Preview

Summary

Hausaufgaben und Lösungen...

Description

Mathematik f¨ ur die Informatik A, Wintersemester 2020/2021 L¨ osungen zu Serie 7

(25) Finden Sie das kleinstm¨ogliche n0 ∈ N mit n3 < 2n fu¨r alle n ∈ N mit n ≥ n0 . Dabei ist sowohl zu beweisen, dass das von Ihnen angegebene n0 die gew¨unschte Eigenschaft als auch, dass es tats¨achlich minimal mit dieser Eigenschaft ist. Behauptung: F¨ ur jedes n ∈ N mit n ≥ 10 ist n3 < 2n wa¨hrend 93 > 29 gilt. achst ist 93 = 729 > 512 = 29 . Nun zeigen wir durch vollsta¨ndige Induktion Beweis: Zun¨ mit dem Startwert n0 = 10, dass f¨ ur jedes n ∈ N mit n ≥ 10 stets n3 < 2n gilt. Im 3 Induktionsanfang haben wir 10 = 1000 < 1024 = 210, die Behauptung gilt also fu ¨r 3 n n = 10. Im Induktionsschritt sei n ∈ N mit n ≥ 10 und n < 2 . Dann haben wir n3 > 7n3 = 3n2 + 3n2 + n2 > 3n2 + 3n + 1 und somit gilt nach einem Beispiel zur binomischen Formel und der Induktionsannahme auch (n + 1)3 = n3 + 3n2 + 3n + 1 < 2n3 < 2 · 2n = 2n+1. andiger Induktion gilt damit n3 < 2n fu¨r alle n ∈ N mit n ≥ 10. Per vollst¨

(26) Zeigen Sie, dass f¨ur alle n ∈ N die Gleichung n X k=0

  n = 2n−1 · n k· k

gilt. Beweis: Wir beweisen dies durch vollst¨andige Induktion. Im Induktionsanfang n = 0 gilt     n X n 0 k· = 0 = 2n−1 · n. = 0· 0 k k=0 Im Induktionsschritt sei n ∈ N mit n X k=0

  n k· = 2n−1 · n. k

1

Zun¨ achst erhalten wir mit der Formel des Pascalschen Dreiecks   n n+1 X n + 1  X n+1 = +n+1 k· k· k k k=0 k=1     n X n n = + +n+1 k· k−1 k k=1  X    n n X n n = +n+1 + k· k· k k−1 k=1 k=1   n X n = + 2n−1 n + n + 1 k· k − 1 k=1   = 1, §4.Satz 7.(b,d) und die Induktionsannahme verwendet haben. F¨ ur wobei wir n+1 n+1 den ersten Summanden ergibt sich mit §4.Satz 7.(c,d) n X k=1

 n−1   X   X n−1 n−1   X n n n n = . = + k· (k + 1) · k· k−1 k k k 

k=0

k=0

k=0

n

Mit n = 1, der Induktionsannahme und einem unserer Beispiele zur binomischen Formel folgt weiter    X  n   n n X X n n n = 2n−1 n + 2n . + +n+1= k· k· k k k − 1 k=0 k=0 k=1 Insgesamt ist damit n+1

  n+1 = 2 · 2n−1 n + 2n = 2n (n + 1) k· k k=0 X

und wir haben den Induktionsschritt durchgef¨ uhrt. Die Behauptung folgt somit durch vollst¨ andige Induktion.

(27) Zeigen Sie, dass es genau eine Folge (Ln )n∈N mit L0 = 1, L1 = 3 und Ln+2 = Ln + Ln+1 f¨ur alle n ∈ N gibt. Zeigen Sie weiter, dass dann f¨ur jedes n ∈ N auch n X

L2k = Ln · Ln+1 − 2

k=0

gilt. 2

ur jedes n ∈ N mit n ≥ 2 sei Fn : Nn → Beweis: Sei F1 : N → N; n 7→ 3 und f¨ N; (x1 , . . . , xn ) 7→ xn−1 + xn . Nach dem Rekursionssatz §4.Satz 6 existiert genau eine Folge (Ln )n∈N mit L0 = 1 und Ln = Fn (L0 , . . . , Ln−1 ) f¨ ur alle n ∈ N\{0}, also mit L0 = 1, L1 = F1 (L0 ) = 3 und Ln = Fn (L0 , . . . , Ln−1 ) = Ln−2 + Ln−1 f¨ ur alle n ∈ N mit n ≥ 2. Dies beweist die erste Aussage. Die zweite Aussage zeigen wir durch vollst¨andige Induktion. Im Induktionsanfang n = 0 haben wir n X L2k = L20 = 1 = 3 − 2 = Ln · Ln+1 − 2. k=0

Im Induktionsschritt sei nun n ∈ N mit n X

Lk2 = Ln · Ln+1 − 2.

k=0

Mit der Induktionsannahme folgt dann auch n+1

X k=0

Lk2 =

n X

2 = Ln Ln+1 + L2n+1 − 2 = Ln+1(Ln + Ln+1 ) − 2 = Ln+1Ln+2 − 2 L2k + Ln+1

k=0

und per vollst¨ andiger Induktion ist alles bewiesen. Bemerkung: Man nennt (Ln )n∈N die Folge der Lukaszahlen, die ersten dieser Zahlen sind L0 = 1, L1 = 3, L2 = 4, L3 = 7, L4 = 11, L5 = 18, L6 = 29. Die Anwendung des Rekursionssatzes wird in der Regel nicht explizit festgehalten, man sagt, dass die Folge (Ln )n∈N durch L0 = 1, L1 = 3 und Ln = Ln−2 + Ln−1 f¨ ur n ≥ 2 induktiv definiert wird. (28) F¨ ur n ∈ N schreiben wir [n] := {k ∈ N|1 ≤ k ≤ n}, also insbesondere [0] = ∅. Seien nun n, m ∈ N und f : [n] → [m] eine injektive Funktion. Zeigen Sie, dass dann n ≤ m gilt wobei genau dann Gleichheit besteht wenn f bijektiv ist. Beweis: Auch dies beweisen wir durch vollst¨andige Induktion nach n, als Aussageform ur n ∈ N verwenden wir dabei f¨  Fur ¨ jedes m ∈ N und jede injektive Abbildung f : [n] → [m] A(n) ≡ gilt n ≤ m und genau dann ist n = m wenn f bijektiv ist. Im Induktionsanfang n = 0 sei f : [n] → [m] eine injektive Abbildung. Dann ist n = 0 ≤ m (etwa nach §3.Satz 22.(a)). Ist auch m = 0 so ist f = ∅ bijektiv und ist m > 0 so haben wir 1 ∈ [m] aber 1 ∈ / Bild(f ) = ∅, d.h. f ist nicht bijektiv. Damit ist f genau dann bijektiv wenn m = 0 = n ist. Somit gilt A(0). Jetzt sei n ∈ N und nehme A(n) an. Wir m¨ ussen A(n + 1) zeigen, seien also m ∈ N und f : [n + 1] → [m] eine injektive Abbildung. Wegen n + 1 ∈ [n + 1] ist f (n + 1) ∈ [m] 3

also [m] 6= ∅ und somit gilt m ≥ 1. Damit m ∈ [m]. Wir behaupten nun, dass es eine bijektive Abbildung τ : [m] → [m] mit τ (f (n + 1)) = m gibt. Hierzu unterscheiden wir zwei F¨ alle. Fall 1. Ist f (n + 1) = m so hat τ := id[m] die gew¨ unschte Eigenschaft. Fall 2. Nun sei f (n + 1) 6= m. Dann definieren wir die Abbildung   k = f (n + 1),  m, τ : [m] → [m]; k 7→ f (n + 1), k = m,   k, k∈ / {f (n + 1), m}

mit τ (f (n + 1)) = m. Wir zeigen nun, dass τ bijektiv ist. Sei k ∈ [m]. F¨ ur k = f (n + 1) ist dann τ (τ (k)) = τ (τ (f (n + 1))) = τ (m) = f (n + 1) = k und ur f¨ k = m haben wir τ (τ (k)) = τ (τ (m)) = τ (f (n + 1)) = m = k. Ist dagegen k ∈ / {f (n + 1), m} so ist ebenfalls τ (τ (k)) = τ (k) = k. Dies zeigt τ ◦ τ = id[m] und nach §3.Satz 10.(d) ist τ bijektiv. Dies zeigt diese Zwischenbehauptung. Nun erhalten wir die Abbildung g := τ ◦ f : [n + 1] → [m] mit g (n + 1) = τ (f (n + 1)) = m. Nach §3.Satz 9.(a) ist auch g injektiv. F¨ ur jedes k ∈ [n] ⊆ [n + 1] ist dann auch k 6= n + 1 und somit g(k) 6= g (n + 1) = m also g(k) ∈ [m]\{m} = [m − 1], wobei letzeres §3.Satz 22.(c) verwendet und nach Aufgabe (21) ist auch m − 1 ∈ N. Damit erhalten wir die injektive Abbildung g ′ := g |[n] : [n] → [m − 1] und nach unserer Induktionsannahme A(n) gilt n ≤ m − 1. Damit ist auch n + 1 ≤ m. Es bleibt nur noch zu zeigen, dass genau dann n + 1 = m ist wenn f bijektiv ist. ”=⇒” Nehme also n + 1 = m an. Dann ist auch n = m − 1 und die Induktionsannahme A(n) ergibt, dass g ′ bijektiv ist. Hieraus folgt, dass auch g surjektiv ist, denn ist k ∈ [m] so ist im Fall k = m sofort m = g(n + 1) ∈ Bild(g) und im Fall k 6= m ist ebenfalls k ∈ [m − 1] = Bild(g ′ ) ⊆ Bild(g ). Damit ist g bijektiv und nach §3.Satz 9.(e) ist auch f = τ −1 ◦ g bijektiv. ”⇐=” Nun nehme an, dass f bijektiv ist. Nach §3.Satz 9.(e) ist dann auch g = τ ◦ f bijektiv. Ist also k ∈ [m − 1] ⊆ [m] so existiert ein l ∈ [n + 1] mit g(l) = k. Wegen g (l) = k 6= m = g(n + 1) ist dann auch l 6= n + 1 also gilt l ∈ [n] und g ′ (l) = k. Damit ist g ′ surjektiv und somit insgesamt bijektiv. Die Induktionsannahme A(n) liefert jetzt n = m − 1 und damit auch n + 1 = m. Damit haben wir A(n + 1) nachgewiesen und mit vollst¨ andiger Induktion folgt die Behauptung der Aufgabe.

4...