Mathematik-Online-Kurs: Vorkurs Mathematik-Grundlagen-Aussagenlogik-Vollständige Induktion

	[Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
	Mathematik-Online-Kurs: Vorkurs Mathematik - Grundlagen - Aussagenlogik
	Vollständige Induktion

[vorangehende Seite] [nachfolgende Seite]

[Gesamtverzeichnis][Seitenübersicht]

Aussageformen mit natürlichen Zahlen als Parametern kann man mit vollständiger Induktion beweisen. Ist eine von $n\in\mathbb{N}$ abhängige Aussage, so sind dazu die folgenden beiden Beweisschritte durchzuführen.

Induktionsanfang: Man zeigt, dass richtig ist.
Induktionsschluss: Man zeigt, dass aus der Annahme, dass richtig ist (Induktionshypothese), folgt, dass auch richtig ist, d.h.

$\displaystyle A(n) \implies A(n+1) \,.$

Dann ist gewährleistet, daß

für alle $n\in\mathbb{N}$ gilt.

Bei einem Induktionsbeweis wird sukzessive das Nächste aus dem Vorherigen gefolgert. Wird der Induktionsanfang nicht für , sondern für ein durchgeführt, so gilt die Aussage nur für alle $n \geq n_0$ .

Die Formel für die Summe der Quadratzahlen,

$\displaystyle A(n):\ \sum_{i=1}^{n} i^2 = 1^2+2^2+\dots+n^2=\frac{1}{6}n(n+1)(2n+1) \,,$

kann mit vollständiger Induktion bewiesen werden.

Induktionsanfang ():

$\displaystyle \sum_{i=1}^{1} i^2 = 1^2 = \frac{1\cdot2\cdot3}{6} \,.$

Induktionsschluß ( $A(n)\implies A(n+1))$ :

$\displaystyle \sum_{i=1}^{n+1} i^2$	$\displaystyle =$	$\displaystyle \sum_{i=1}^{n} i^2 + (n+1)^2 = \underbrace{\displaystyle\frac{n(n+1)(2n+1)}{6}}_{ A(n)} + (n+1)^2$
	$\displaystyle =$	$\displaystyle \displaystyle\frac{(n+1)\big[n(2n+1)+6(n+1)\big]}{6} = \displaystyle\frac{(n+1)(n+2)(2n+3)}{6}\,.$

Die Induktionshypothese wurde, wie angedeutet, bei der dritten Gleichheit benutzt.

[vorangehende Seite] [nachfolgende Seite]

[Gesamtverzeichnis][Seitenübersicht]

automatisch erstellt am 23.10.2009