Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Induktion

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Induktionsbeweis - Kettenform

Sei für jede natürliche Zahl $ \mbox{$n$}$ eine Aussage $ \mbox{$A(n)$}$ gegeben, die zunächst einmal wahr oder falsch sein kann. Wir wollen ein Prinzip erläutern, mit welchem die Richtigkeit von $ \mbox{$A(n)$}$ für alle $ \mbox{$n\in\mathbb{N}$}$ gezeigt werden kann.

Induktionsanfang. Wir zeigen die Gültigkeit von $ \mbox{$A(0)$}$.

Induktionsschritt. Wir zeigen, daß aus der Gültigkeit von $ \mbox{$A(n)$}$ die Gültigkeit von $ \mbox{$A(n+1)$}$ folgt. Hierzu dürfen wir also die Induktionshypothese $ \mbox{$A(n)$}$ als wahr annehmen. Zu zeigen ist nur die Implikation $ \mbox{$A(n)$}$ $ \mbox{$\Longrightarrow $}$ $ \mbox{$A(n+1)$}$.

Sind Induktionsanfang und Induktionsschritt gezeigt, so gilt die Aussage $ \mbox{$A(n)$}$ wegen

$ \mbox{$\displaystyle A(0)\;\Longrightarrow \;A(1)\;\Longrightarrow \;A(2)\;\Longrightarrow \;A(3)\;\Longrightarrow \;A(4)\;\Longrightarrow \; \dots $}$
für alle $ \mbox{$n\in\mathbb{N}$}$. Formaler gesprochen folgt dies aus der Tatsache, daß jede nichtleere Teilmenge der natürlichen Zahlen ein Minimum besitzt. Denn wäre die Teilmenge der natürlichen Zahlen, für die $ \mbox{$A(n)$}$ nicht gilt, nicht leer, so hätte sie ein minimales Element $ \mbox{$n_0$}$. Dann ist $ \mbox{$n_0\geq 1$}$ wegen Induktionsanfang, aber $ \mbox{$A(n_0 - 1)$}$ wahr wegen Minimalität, und schließlich $ \mbox{$A(n_0)$}$ wahr wegen Induktionsschritt, Widerspruch.

Dasselbe Verfahren kann man für Aussagen $ \mbox{$B(n)$}$ verwenden, die für $ \mbox{$\{n\in\mathbb{Z}\; \vert\; n\geq m\}$}$ für ein $ \mbox{$m\in\mathbb{Z}$}$ zu zeigen sind, wobei dann $ \mbox{$B(m)$}$ als Induktionsanfang dient (verwende $ \mbox{$A(n) := B(n+m)$}$).

Induktionsbeweis - allgemeine Form

Sei wieder für jede natürliche Zahl $ \mbox{$n$}$ eine Aussage $ \mbox{$C(n)$}$ gegeben, die wahr oder falsch sein kann. Wir wollen ein weiteres Prinzip erläutern, mit welchem die Richtigkeit von $ \mbox{$C(n)$}$ für alle $ \mbox{$n\in\mathbb{N}$}$ gezeigt werden kann.

Induktionsanfang. Wir zeigen die Gültigkeit von $ \mbox{$C(0)$}$.

Induktionsschritt. Wir zeigen, daß aus der Gültigkeit aller Aussagen $ \mbox{$C(0)$}$, ..., $ \mbox{$C(n)$}$ die Gültigkeit von $ \mbox{$C(n+1)$}$ folgt.

Denn wäre die Teilmenge der natürlichen Zahlen, für die $ \mbox{$C(n)$}$ nicht gilt, nicht leer, so hätte sie ein minimales Element $ \mbox{$n_0$}$. Dann ist $ \mbox{$n_0\geq 1$}$ wegen Induktionsanfang, aber $ \mbox{$C(m)$}$ wahr für $ \mbox{$m < n_0$}$ wegen Minimalität, und schließlich $ \mbox{$C(n_0)$}$ wahr wegen Induktionsschritt, Widerspruch.

Rekursive Definition.

Sei $ \mbox{$X$}$ eine Menge. Wir wollen ein Prinzip erläutern, mit dem eine Funktion $ \mbox{$\mathbb{N}\unitlength.1mm\begin{picture}(80,50) \put( 0, 0){$\longrightarrow $} \put( 10, 27){\makebox[6mm]{$\scriptstyle f$}} \end{picture} X$}$ definiert werden kann. Sei hierzu $ \mbox{$r\geq 1$}$ gegeben, und eine Funktion $ \mbox{$F:\mathbb{N}\times X^r\longrightarrow X$}$, $ \mbox{$(n,x_1,\dots,x_r)\mapsto F(n,x_1,\dots,x_r)$}$. Wir sprechen dann auch von einer $ \mbox{$r$}$-gliedrigen Rekursion.

Rekursionsanfang. Sei $ \mbox{$f(0) := a_0,\; f(1):=a_1,\; \ldots ,\; f(r-1):=a_{r-1}$}$ mit gewissen, frei wählbaren Anfangswerten $ \mbox{$a_0,a_1,\ldots,a_{r-1}\in X$}$ definiert.

Rekursionsschritt. Für $ \mbox{$n\geq r$}$ sei

$ \mbox{$\displaystyle f(n) := F(n,f(n-r),\dots,f(n-1))\; . $}$

Mit Induktion folgt, daß $ \mbox{$f$}$ für alle $ \mbox{$n\in\mathbb{N}$}$ erklärt ist.

(Autoren: Künzer/Martin/Nebe)

Beispiele:

[Verweise]
  automatisch erstellt am 25.  1. 2006