Ing Mathematik: Vollständige Induktion

Zurück zu Komplexe Zahlen | Hoch zu Gesamtinhaltsverzeichnis |

Bei der vollständigen Induktion handelt es sich um eine recht häufig genutzte Beweismethode der Mathematik. Im Kapitel Zahlenbereiche haben wir die Peano'schen Axiome kennengelernt. Das fünfte ist das sog. „Induktionsaxiom“. Auf diesem basiert der Induktionsbeweis.

Grundidee

Am besten veranschaulicht man sich die Idee durch ein Dominospiel: Man nimmt sich eine beliebige natürliche Zahl $n$ - oder einen beliebigen Dominostein - und beweist die Aussage für diesen. Schmeißt man diesen Stein um, bzw. beweist die Aussage dann auch für $n+1$, so folgt sofort die Gültigkeit der Aussage für alle anderen natürlichen Zahlen (Steine), die folgen. Man nehme sich nun zum Beispiel die Zahl 5 und beweise eine Formel, indem man die 5 einsetzt. Beweist man nun die Formel auch für $n+1$, so hat man gezeigt, dass sie auch für 6 gilt. Da jedoch $n+1$ nicht an ein konkretes $n$ gebunden ist, folgt die Gültigkeit auch für $n=6$ (da gerade bewiesen) und $n+1=7$, etc... I. d. R. macht es Sinn, mit dem ersten Stein, bzw. der „ersten“ natürlichen Zahl anzufangen (je nach Definiton i.A. 0 oder 1).

Beweismethode

Der Beweis wird in drei Schritte unterteilt: Dem Induktionsanfang, der Formulierung der Induktionsvoraussetzung und dem Induktionsschritt. Es soll nun Aussage A bewiesen werden.

1. IA: Sei $n=0$. Dann ist ... und A gilt für $n=0$.
2. IV: A gelte nun für ein beliebiges, aber festes $n\in \mathbb {N}$.
3. IS: $n$ → $n+1$. Nun wird gezeigt, dass A unter Induktionsvoraussetzung auch für $n+1$ gilt.

Die Aussage ist somit bewiesen. Man beachte, dass beim IA nicht zwingend mit der 0 begonnen werden muss.

Diese abstrakte Vorgehensweise wird nun durch ein Beispiel verdeutlicht.

Beispiel 1: Endliche geometrische Reihe

Wir wollen nun zeigen, dass für alle natürlichen Zahlen und alle $q\in \mathbb {R}$ gilt:

$\sum _{k=0}^{n}q^{k}={\frac {1-q^{n+1}}{1-q}}$

IA

Sei $n=0$. Dann gilt:

$\sum _{k=0}^{0}q^{k}=q^{0}=1={\frac {1-q}{1-q}}={\frac {1-q^{0+1}}{1-q}}$

Die Aussage giltsomit für $n=0$.

IV

Die Aussage gelte nun für ein beliebiges, aber festes $n\in \mathbb {N}$.

IS

$n$ → $n+1$: Wir beweisen nun die Aussage für $n+1$.

${\begin{aligned}\sum _{k=0}^{n+1}q^{k}=\sum _{k=0}^{n}q^{k}+q^{n+1}=^{*}{\frac {1-q^{n+1}}{1-q}}+q^{n+1}={\frac {1-q^{n+1}}{1-q}}+{\frac {(1-q)q^{n+1}}{1-q}}\\={\frac {1-q^{n+1}+(1-q)q^{n+1}}{1-q}}={\frac {1-q^{n+1}+q^{n+1}-q^{n+2}}{1-q}}={\frac {1-q^{(n+1)+1}}{1-q}}\end{aligned}}$

Die Aussage ist somit für alle natürlichen Zahlen bewiesen.

An der Stelle * ist die (im IA) bewiesene IV eingeflossen. Hier wird deutlich, wieso es „für ein beliebiges, aber festes $n$“ und nicht „für alle $n$“ heißen muss; wir haben schließlich die Aussage noch nicht für alle natürlichen Zahlen, sondern für eine feste, die 0, bewiesen.

In der Regel sieht der IS dann so aus, dass man auf „einer Seite“ (hier links) anfängt und so lange umformt, bis man zur anderen gekommen ist.

Zurück zu Komplexe Zahlen | Hoch zu Gesamtinhaltsverzeichnis |