Lösungen zu den Übungen

Übung 1

Zeigen Sie mit Hilfe vollständiger Induktion:

Für alle n ≥ 1 gilt  ∑1 ≤ k ≤ n (2k − 1)  =  n2.

Lösung zur Übung 1

Wir beweisen die Aussage durch vollständige Induktion nach n ≥ 1.

Induktionsanfang n = 1: 

Die linke Seite berechnet sich für n = 1 zu

∑1 ≤ k ≤ 1 (2k − 1)  =  2 · 1 − 1  =  2 − 1  =  1.

Die rechte Seite berechnet sich für n = 1 zu

n2  =  12  =  1.

Beide Seiten stimmen überein.

Kürzer können wir auch so argumentieren: Für n = 1 gilt

∑1 ≤ k ≤ n (2k − 1)  =  ∑1 ≤ k ≤ 1 (2k − 1)  =  2 · 1 − 1  =  2 − 1  =  1  =  12  =  n2.

Induktionsschritt von n nach n + 1: 

Es gelte:

∑1 ≤ k ≤ n (2k − 1)  =  n2  (Induktionsvoraussetzung I.V.)

Wir zeigen:

(+)  ∑1 ≤ k ≤ n + 1 (2k − 1)  =  (n + 1)2

Zum Beweis formen wir die linke Seite von (+) mit Hilfe der Induktionsvoraussetzung in die rechte Seite um. Es gilt:

∑1 ≤ k ≤ n + 1 (2k − 1) =  ∑1 ≤ k ≤ n (2k − 1)  +  (2(n + 1) − 1)
=I. V.  n2  +  (2(n + 1) − 1)
=  n2 + 2n + 2 − 1
=  n2 + 2n + 1
=  (n + 1)2
Übung 2

Illustrieren Sie die für alle n ≥ 1 gültige Summenformel

∑1 ≤ k ≤ n (2k − 1)  =  n2

aus Übung 1 durch ein Diagramm, sodass ein visueller Beweis der Formel entsteht.

Lösung zur Übung 2

Die Formel besagt, dass wir die Quadratzahlen durchlaufen, wenn wir die ungeraden Zahlen

1,  3,  5,  7,  … 

aufsummieren. Wir stellen Quadratzahlen geometrisch mit Hilfe von Zählsteinen dar, um dies zu visualisieren:

hm1-AbbIDodd_sum_1

Wir fügen schrittweise 1, 3, 5, …, 2n − 1, … Zählsteine hinzu, die wir winkelförmig anordnen. Dabei entstehen Quadrate mit 1, 4, 9, …, n2, … Zählsteinen.

Übung 3

(a)

Geben Sie alle zweielementigen Teilmengen von { 1, …, n } für n = 2, 3, 4 in Form einer Tabelle an.

(b)

Zeigen Sie mit Hilfe vollständiger Induktion, dass für alle n ≥ 2 gilt:

Es gibt genau n(n − 1)/2 zweielementige Teilmengen von { 1, …, n }.

(c)

Begründen Sie die Anzahlformel in (b) durch eine kombinatorische Argumentation, d.h. geben Sie eine begründete Antwort auf die Frage:

„Wieviele Möglichkeiten gibt es, zwei Elemente aus { 1, …, n } auszuwählen?“

Lösung zur Übung 3

zu (a): 

n = 2: { 1, 2 }
n = 3: { 1, 2 },  { 1, 3 },  { 2, 3 }
n = 4: { 1, 2 },  { 1, 3 },  { 1, 4 },  { 2, 3 },  { 2, 4 },  { 3, 4 }

zu (b): 

Induktionsanfang n = 2:  Für n = 2 gibt es genau eine zweielementige Teilmenge von { 1, 2 } (nämlich die Menge selbst). Für n = 2 gilt n(n − 1)/2 = 1, sodass die Anzahlformel für n = 2 richtig ist.

Induktionsschritt von n nach n + 1:  Es gebe genau n(n − 1)/2 zweielementige Teilmengen von { 1, …, n } (Induktionsvoraussetzung I.V.). Wir zeigen, dass es genau (n + 1)n/2 zweielementige Teilmengen von { 1, …, n + 1 } gibt. Hierzu beobachten wir:

(i)

Jede zweielementige Teilmenge von { 1, …, n } ist eine solche von { 1, …, n + 1 }.

(ii)

Die anderen zweielementigen Teilmengen von { 1, …, n + 1 } sind von der Form { k, n + 1 } für k = 1, …, n.

Nach Induktionsvoraussetzung gibt es genau n(n − 1)/2 Teilmengen wie in (i). Weiter gibt es genau n Teilmengen wie in (ii). Damit berechnet sich die Zahl dieser Teilmengen zu

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

zu (c): 

Sei n ≥ 2. Dann gibt es genau n(n − 1) geordnete Paare (a, b) mit a ≠ b und a, b  ∈  { 1, …, n }. Denn für die erste Position haben wir n und für die zweite Position n − 1 Möglichkeiten. Weiter gibt es n(n − 1)/2 derartige (a, b) mit a < b (da mit (a, b) immer auch (b, a) ein Paar ist). Die Anzahl der geordneten Paare (a, b) mit a < b entspricht genau den ungeordneten Paarmengen { a, b } mit a ≠ b.

Übung 4

Zeigen Sie mit Hilfe vollständiger Induktion:

Für alle natürlichen Zahlen n ≥ 0 gilt  ∑k ≤ n k2  =  n (n + 1) (2n + 1)6.

Lösung zur Übung 4

Um die Notation zu vereinfachen (Vermeidung von Brüchen), zeigen wir die äquivalente Aussage:

(#)  Für alle natürlichen Zahlen n ≥ 0 gilt  6 ∑k ≤ n k2  =  n (n + 1) (2n + 1).

Wir beweisen (#) durch vollständige Induktion nach n ≥ 0.

Induktionsanfang n = 0: 

Für n = 0 gilt

6 ∑k ≤ n k2  =  6 ∑k ≤ 0 k2  =  6 · 02  =  0  =  0 · 1 · 1  =  n (n + 1) (2n + 1).

Induktionsschritt von n nach n + 1: 

Es gelte

6 ∑k ≤ n k2  =  n (n + 1) (2n + 1)  (Induktionsvoraussetzung).

Wir zeigen, dass

6 ∑k ≤ n + 1 k2  =  (n + 1) (n + 2) (2n + 3)  (mit 2(n + 1) + 1 = 2n + 3)).

Es gilt:

6 ∑k ≤ n + 1 k2 =  6 ∑k ≤ n k2  +  6 (n + 1)2
=I. V.  n (n + 1) (2n + 1)  +  6 (n + 1)2
=  (n + 1) (n (2n + 1)  +  6 (n + 1))
=  (n + 1) (2n2 + n + 6n + 6)
=  (n + 1) (2n2 + 7n + 6)
=  (n + 1) (n + 2) (2n + 3)