Analyse 1, 1. Kapitel: Vollständige Induktion

Einführung

• In der Mathematik benutzt man verschiedene Methoden, um Sätze oder Behauptungen zu beweisen.
• Eine dieser Methoden ist die vollständige Induktion, besonders geeignet für Aussagen, die von natürlichen Zahlen abhängen.
• Natürliche Zahlen: Menge der nicht-negativen ganzen Zahlen, angefangen bei 0.

Beweisprinzip der vollständigen Induktion

• Ziel: Beweisen, dass eine Klasse von Aussagen (a_n) für alle natürlichen Zahlen (n) gilt.
• Induktionsanfang: Es gibt eine natürliche Zahl (n_0), sodass (a_{n_0}) gilt.
• Induktionsschritt: Angenommen, (a_n) gilt für ein beliebiges (n\geq n_0), dann gilt auch (a_{n+1}).
• Folge: Wenn (a_1) gilt, dann gilt (a_2), (a_3) usw.

Beispiel 1: Summe der ersten n natürlichen Zahlen

• Behauptung: (1 + 2 + \ldots + n = \frac{n(n+1)}{2}).
• Induktionsanfang: Für (n = 1): (1 = \frac{1(1+1)}{2} = 1).
• Induktionsschritt:
  • Angenommen, (1 + 2 + \ldots + n = \frac{n(n+1)}{2}) gilt.
  • Beweise, dass (1 + 2 + \ldots + (n+1) = \frac{(n+1)(n+2)}{2}).
  • Berechnung: (1 + 2 + \ldots + n + (n+1) = \frac{n(n+1)}{2} + (n+1)).
  • Umformung zeigt: (\frac{(n+1)(n+2)}{2}), also gilt der Induktionsschritt.

Beispiel 2: Summe der ersten n ungeraden Zahlen

• Behauptung: (1 + 3 + \ldots + (2n-1) = n^2).
• Induktionsanfang: Für (n = 1): (1 = 1^2).
• Induktionsschritt:
  • Angenommen, (1 + 3 + \ldots + (2n-1) = n^2) gilt.
  • Beweise, dass (1 + 3 + \ldots + (2n-1) + (2n+1) = (n+1)^2).
  • Berechnung: (n^2 + (2n+1) = (n+1)^2).

Alternative Beweisführung

• Man kann auch ohne vollständige Induktion beweisen, z.B. durch Umformung und Nutzung bekannter Sätze.

Fakultät (Factorial)

• Definition: (n! = 1 \times 2 \times \ldots \times n).
• Für (n = 0) definiert man (0! = 1).

Kombinatorische Bedeutung der Fakultät

• Anzahl der Anordnungen einer Menge mit n Elementen.
• Beweis durch vollständige Induktion:
  • Induktionsanfang: Für (n = 1), nur eine Anordnung möglich.
  • Induktionsschritt: Anordnung von (n+1) Elementen über verschiedene Platzierungen des zusätzlichen Elements.
  • Anzahl der Anordnungen: ((n+1) \times n! = (n+1)!).

Diese Notizen bieten eine Übersicht über die Konzepte der vollständigen Induktion und deren Anwendung in verschiedenen mathematischen Beweisen.