Übungen zur Induktion
Übung 1
Beweisen Sie das Prinzip der vollständigen Induktion
(a) | mit Hilfe des Prinzips der starken Induktion, |
(b) | mit Hilfe des Prinzips vom kleinsten Element. |
Übung 2
Wir beweisen das Prinzip vom kleinsten Element mit Hilfe einfacher Induktion auf neue Art und Weise. Hierzu betrachten wir das folgende Prinzip:
(E) Jede endliche nichtleere Teilmenge von ℕ besitzt ein kleinstes Element.
Im Gegensatz zum Prinzip vom kleinsten Element werden hier also nur endliche Mengen betrachtet.
(1) | Zeigen Sie, dass aus (E) das Prinzip vom kleinsten Element folgt. |
(2) | Zeigen Sie (E) durch Induktion über die Anzahl n der Elemente einer nichtleeren endlichen Teilmenge von ℕ. |
Übung 3
Beweisen Sie das Prinzip monoton fallender Folgen mit Hilfe des Prinzips vom unendlichen Abstieg.
Übung 4
Zeigen Sie, dass jede nach unten beschränkte Teilmenge von ℤ ein kleinstes Element besitzt. (Dabei heißt ein A ⊆ ℤ nach unten beschränkt, wenn ein s ∈ ℤ existiert mit s ≤ a für alle a ∈ A.)
Übung 5
Sei ℰ(n) eine Eigenschaft natürlicher Zahlen. Es gelte:
(a) | ℰ(0), |
(b) | ∀n (ℰ(n) → ℰ(n + 2)), |
(c) | ∀nℰ(2n) → ℰ(1). |
Zeigen Sie, dass ℰ(n) für alle natürlichen Zahlen n gilt.
Übung 6
Sei ℰ(n, m) eine Eigenschaft natürlicher Zahlen. Es gelte:
(a) | ℰ(0, 0), |
(b) | ∀n, m ℰ(n, m) → ℰ(n + 1, m), |
(c) | ∀n, m ℰ(n, m) → ℰ(n, m + 1). |
Zeigen Sie, dass ℰ(n, m) für alle natürlichen Zahlen n, m gilt.
Übung 7
Sei ℰ(n) eine Eigenschaft natürlicher Zahlen. Es gelte:
(a) | ℰ(p) für jede Primzahl p, |
(b) | ∀n, m (ℰ(n) ∧ ℰ(m) → ℰ(nm)). |
Zeigen Sie, dass ℰ(n) für alle n gilt.
Übung 8
Sei ℰ(a) eine Eigenschaft ganzer Zahlen. Es gelte:
(a) | ∃a ∈ ℤ ℰ(a), |
(b) | ∀a ∈ ℤ (ℰ(a) → ℰ(a + 1) ∧ ℰ(a − 1)). |
Zeigen Sie, dass ℰ(a) für alle a ∈ ℤ gilt.
Übung 9
Wir betrachten eine rechteckige Tafel Schokolade der Länge n und Breite m (also mit nm Stückchen). Wie oft muss man die Schokolade brechen, um nm einzelne Stückchen zu erhalten? Auf welche Weise geschieht dies am Besten? Was hat diese Frage mit Induktion zu tun? Für das Brechen der Tafel oder eines Teils der Tafel ist dabei nur das übliche waagrechte oder senkrechte Abbrechen eines Teilstücks entlang der vorgegebenen Rillen erlaubt; es sind keine Tricks wie zum Beispiel das Übereinanderlegen von Stücken zulässig.
Übung 10
„Wer reich ist und einen Cent verliert ist immer noch reich.“ Beweisen Sie unter dieser Voraussetzung, dass man auch dann noch reich ist, wenn man gar kein Geld hat. (Der interessierte Leser möge sich zudem über das Sorites-Paradoxon der Philosophie informieren.)
Übung 11
In einigen Schulbüchern wird der Beweis durch vollständige Induktion als dreiteiliges Prinzip, bestehend aus Induktionsanfang, Induktionsvoraussetzung und Induktionsschritt eingeführt. Bewerten Sie dieses Vorgehen aus mathematischer Sicht.