Title: ADM26 / Beweise und Methoden

Q: Wie lautet das Induktionsschema zum Beweis von Summenformeln?
A: Typ: Aussage über explizite Summen (z. B. \( \sum_{k=1}^{n} f(k) \))
Schema:
1. Behauptung: Für alle \( n \geq n_0 \) gilt: \[ \sum_{k=a}^{n} f(k) = F(n) \]
2. Induktionsanfang: Zeige Gültigkeit für \( n = n_0 \): \[ \sum_{k=a}^{n_0} f(k) = F(n_0) \]
3. Induktionsvoraussetzung (IV): Für beliebiges aber fixes \( n \geq n_0 \) gelte: \[ \sum_{k=a}^{n} f(k) = F(n) \]
4. Induktionsschritt: Zeige: \[ \sum_{k=a}^{n+1} f(k) = \sum_{k=a}^{n} f(k) + f(n+1) = F(n) + f(n+1) \stackrel{!}{=} F(n+1) \]
Typisch: Arithmetische/geometrische Reihen, klassische Formeln.

Q: Wie lautet das Induktionsschema zum Beweis von Ungleichungen?
A: Typ: Aussagen der Form \( A(n) \leq B(n) \), \( A(n) \geq B(n) \) oder ähnlich
Schema:
1. Behauptung: Für alle \( n \geq n_0 \) gilt: \[ A(n) \leq B(n) \]
2. Induktionsanfang: Prüfe die Ungleichung für \( n = n_0 \)
3. Induktionsvoraussetzung (IV): Für ein fixes \( n \geq n_0 \) gelte: \[ A(n) \leq B(n) \]
4. Induktionsschritt: Zeige: \[ A(n+1) \leq B(n+1) \] unter Verwendung der IV. Oft durch Abschätzung: \[ A(n+1) = f(A(n), n) \leq f(B(n), n) \leq B(n+1) \]
Beispiel: Zeige \( 2^n > n^2 \) für \( n \geq 5 \)

Q: Wie lautet das Induktionsschema für rekursiv definierte Folgen?
A: Typ: Folge \( (a_n) \) ist rekursiv definiert, und eine explizite Eigenschaft von \( a_n \) soll gezeigt werden
Schema (abhängig von der Rekursionstiefe):
1. Behauptung: Für alle \( n \geq n_0 \) gilt eine Aussage über \( a_n \), z. B.: \[ a_n \leq F(n) \quad \text{oder} \quad a_n = F(n) \]
2. Induktionsanfang: Zeige Aussage für alle benötigten Anfangswerte (z. B. \( n_0, n_0+1, \ldots \))
3. Induktionsvoraussetzung (IV): Für alle \( k \in \{n_0, \ldots, n\} \) gelte die Aussage über \( a_k \)
4. Induktionsschritt: Zeige Aussage für \( a_{n+1} \), z. B. durch Einsetzen in die Rekursion: \[ a_{n+1} = f(a_n, a_{n-1}, \ldots) \leq \ldots \leq F(n+1) \]
Typisch: Fibonacci, T(n) aus Algorithmen, rekursive Algorithmenabschätzungen

Q: Induktion mit Abschätzung – allgemeines Prüfungsschema:
A: Gegeben:
Zu zeigen ist für alle \( n \ge n_0 \):
\[P(n):\quad L(n) \;\square\; R(n)\] wobei \( \square \in \{<,\le\} \).
1) Induktionsanfang (IA):
Ziel: \( P(n_0) \) ist wahr.
Vorgehen:
- \( L(n_0) \) exakt ausrechnen
- \( R(n_0) \) exakt ausrechnen
- Numerisch vergleichen
Merksatz:
Keine Abschätzung im IA – nur rechnen.
2) Induktionsvoraussetzung (IV):
Annahme für ein festes, aber beliebiges \( n \ge n_0 \):
\[L(n) \;\square\; R(n)\]
Wichtig: Die IV ist die einzige erlaubte Annahme im Induktionsschritt.
3) Induktionsschritt (IS):
Ziel:
\[L(n+1) \;\square\; R(n+1)\]
3a) Zerlegung von \( L(n+1) \):
Man schreibt \( L(n+1) \) so, dass die IV sichtbar wird:
Typische Formen:
Summen: \[\sum_{k=1}^{n+1} a_k = \underbrace{\sum_{k=1}^{n} a_k}_{\text{IV-Term}} + \underbrace{a_{n+1}}_{\text{Zusatzterm}}\] Produkte: \[(n+1)! = (n+1)\cdot \underbrace{n!}_{\text{IV-Term}}\] Rekursionen: \[a_{n+1} = f(a_n, n)\]
3b) Einsetzen der IV:
Der IV-Term wird durch \( R(n) \) ersetzt:
\[L(n+1) \;\square\; R(n) + T(n+1)\] wobei \( T(n+1) \) der Zusatzterm ist.
3c) Abschätzung (kritischer Schritt):
Man zeigt: \[R(n) + T(n+1) \;\square\; R(n+1)\] Prinzip:
Der Zusatzterm wird so abgeschätzt, dass genau \( R(n+1) \) entsteht.
Erlaubt:
- gröbere Abschätzungen
- Monotonieargumente
- Umformen auf gleiche Struktur wie \( R(n+1) \)
4) Schluss:
Da IA und IS gelten, folgt die Aussage für alle \( n \ge n_0 \).

Q: Induktion mit Abschätzung – Prüfungs-Merkschema:
A: Die vier festen Rollen:
- IV-Term: Teil von \( L(n+1) \), der durch die IV kontrolliert ist
- Zusatzterm: Neuer Term bei \( n+1 \)
- Abschätzung: Kontrolle des Zusatzterms
- Zielschranke: \( R(n+1) \)
Goldene Regel:
\[\text{Induktion} \neq \text{Rechnen}\] \[\text{Induktion} = \text{Struktur erkennen + Abschätzen}\]
Warnsignal:
Wenn du im IS anfängst „exakt auszurechnen“, bist du fast immer auf dem falschen Weg.
Richtiger Weg:
Terme gröber machen, aber stabil in Richtung \( R(n+1) \).