Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge

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 $ A(n)$ eine von $ n\in\mathbb{N}$ abhängige Aussage, so sind dazu die folgenden beiden Beweisschritte durchzuführen.

Dann ist gewährleistet, daß $ A(n)$ 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 $ n_0 = 1$, sondern für ein $ n_0>1$ 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 ($ A(1)$):

$\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