6. Vollständige Induktion

Übung 1

Wir definieren für jede natürliche Zahl n ≥ 1 die endliche Summe

s_n = 3 ∑_{1 ≤ k ≤ n} k (k − 1) = 3 ( 1 · 0 + 2 · 1 + 3 · 2 + … + n · (n − 1))

(a)	Berechnen Sie s₁, s₂, s₃ und s₄.

(b)	Zeigen Sie durch vollständige Induktion: s_n = (n − 1) n (n + 1) für alle n ≥ 1

Übung 2

Für alle n  ∈  ℕ und k = 0, …, n ist der Binomialkoeffizient „k aus n“ (gleichwertige Sprechweise: „n über k“) definiert durch

bin(n, k) = $( \binom{n}{k} )$ = ^n!_{k! (n − k)!}

(a)	Seien n ≥ 1 und k  ∈  { 1, …, n }. Zeigen Sie: $( \binom{n}{k - 1} )$ + $( \binom{n}{k} )$ = $( \binom{n + 1}{k} )$

(b)	Zeigen Sie durch vollständige Induktion mit Hilfe von (a), dass für alle n ≥ 0 gilt: (+)_nFür alle k = 0, …, n gilt: bin(n, k) ist die Anzahl der k-elementigen Teilmengen von { 1, …, n }

Bemerkungen

(1)	Die Aussage in (b) können wir auch so notieren: ∀n ∀k ≤ n bin(n, k) = \|{ X ⊆ { 1, …, n } \| \|X\| = k }\| Dabei ist \|M\| die Anzahl der Elemente einer endlichen Menge M.

(2)	Elementare Eigenschaften über endliche Mengen dürfen in den Beweisen frei verwendet werden.

Übung 3

Eine natürliche Zahl d heißt Teiler einer natürlichen Zahl n, in Zeichen d|n, falls es eine natürliche Zahl k gibt mit d · k = n. Ist d zudem eine Primzahl, so heißt d ein Primteiler von n. Wir betrachten die Aussage:

(+) Jede natürliche Zahl n ≥ 2 besitzt einen kleinsten Primteiler.

(a)	Beweisen Sie (+) mit Hilfe starker Induktion.

(b)	Beweisen Sie (+) mit Hilfe des Prinzips vom kleinsten Element.

Übung 4

Wir definieren für jede natürliche Zahl n ≥ 1 die endliche Summe

s_n = ∑_{1 ≤ k ≤ n} ¹_{k (k + 2)} = ¹_{1 · 3} + ¹_{2 · 4} + … + ¹_{n · (n + 2)}

(a)	Berechnen Sie s₁, s₂ und s₃.

(b)	Zeigen Sie durch vollständige Induktion nach n ≥ 1: ∑_{1 ≤ k ≤ n} ¹_{k (k + 2)} = ^{n (3n + 5)}_{4 (n + 1)(n + 2)} für alle n ≥ 1

Lösungshinweis

zu (b): Ein Induktionsschritt von n − 1 nach n führt zu einfacheren Termen.