Wie führe ich einen Induktionsbeweis?

Der Induktionsbeweis eignet sich häufig, wenn es um Aussagen über die Natürlichen Zahlen \(\mathbb{N}\) geht, allerdings kann er auch für die ganzen Zahlen \(\mathbb{Z}\) verwendet werden.

Prinzip

Der Gedanke hinter dem Induktionsbeweis ist, dass man sehr leicht für ein einzelnes Element zeigen kann, dass eine Aussage gilt. Diese Aussage ist die Behauptung. Dann zeigt man allgemein, wenn die Aussage für eine Zahl gilt muss sie auch für die nächste Zahl gelten.

Wenn man also für n = 1 zeigt dass die Aussage A(n) korrekt ist, dann gilt sie für alle positiven Zahlen.

Aufbau

  • Induktionsanfang (I.A.): Zeige, dass die Aussage für ein bestimmtes $n_0$ (also z.B. $n_0 = 0$) gilt. Dafür muss man einfach nur einsetzen.
  • Induktionsvorraussetzung (I.V.)): "Sei $n \in \mathbb{N}$ beliebig, aber fest und es gelte: "
  • Induktionsschluss (I.S.): Ausgehend von I.V. ist zu zeigen, dass die Aussage für $n_0 + 1$ gilt.

Beispiele

Identitäten

Es gibt viele Identitäten, die sich gut mit einem Induktionsbeweis zeigen lassen: Bei den folgenden Identitäten sei \(n \in \mathbb{N}\).

Gaußsche Summenformel

Behauptung: \(\sum_{k=1}^n k = \frac{1}{2} \cdot n \cdot (n+1)\)
Beweis: durch vollständige Induktion
I.A.: Sei n = 1. Dann: \(\sum_{k=1}^1 k = 1 = \frac{1}{2} \cdot 1 \cdot (1+1)\)
I.V.: Sei \(n \in \mathbb{N}\) beliebig, aber fest und es gelte: \(\sum_{k=1}^n k = \frac{1}{2} \cdot n \cdot (n+1)\)
I.S.: \(\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n+1) \stackrel{I.V.}{=} \frac{1}{2} \cdot n \cdot (n+1) + (n+1) = $ $= \frac{1}{2} \cdot (n^2 + n) + (n+1) = \frac{1}{2} \cdot (n^2 + 3n + 2) = \frac{1}{2} \cdot (n+1)(n+2) \blacksquare\)

Weitere

  1. $\sum_{k=1}^n k^3 = \frac{1}{4}n^2 (n+1)^2$
  2. Fibonacci: $f(m+n) = f(n+1) \cdot f(m) + f(n) \cdot f(m-1)$

Binomischer Satz

Das folgende habe ich als Mitschrift der Vorlesung "Analysis I" am KIT gemacht:

Seien $a, b \in \mathbb{R}.$ Dann gilt für alle $n \in \mathbb{N}$: $(a+b)^{n+1} = (a+b)(a+b)^n = (a+b) \underbrace{\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k}_\text{Binomischer Lehrsatz}$

I.A.: \(n=1: \sum_{k=0}^{1}\binom{1}{k} a^{1-k} b^k = (a+b)^n\)

I.V.: Sei \(n \in \mathbb{N}\) und es gelte \((a+b)^{n+1} = (a+b)(a+b)^n = (a+b) \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\)

I.S.:

\begin{align} (a+b)^{k+1} &= (a+b)(a+b)^n \\ &= (a+b) \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k + \sum_{k=0}^n \binom{n}{k} a^{n-k} b^{k+1} \\ &= \underbrace{\binom{n}{0}}_{\binom{n+1}{0}} a^{n+1} + \sum_{k=1}^n \binom{n}{k} a^{n+1-k} b^k + \underbrace{\sum_{k=0}^{n-1} \binom{n}{k} a^{n-k} b^{k+1}}_\text{Vorbemerkung} + \binom{n}{n} b^{n+1} \\ &= \binom{n+1}{0} a^{n+1} + \sum_{k=1}^{n} [\binom{n}{k} + \binom{n}{k-1}] a^{n+1} b^k + \binom{n+1}{n+1} b^{n+1} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^k \end{align}

Rekursive Folgen

Der Grenzwert rekursiv definierter Folgen lässt sich häufig sehr schön mit mehreren Induktionsbeweisen beweisen.

  1. Finde für dich heraus: Ist die Folge monoton steigend oder fallend? ist 0 oder 1 eine untere / obere Schranke? gibt es andere untere oder obere Schranken?
  2. Beweise, dass du eine obere / untere Schranke gefunden hast
  3. Beweise, dass die Folge monoton steigt / fällt
  4. Mache den Ansatz: Sei $a$ der Grenzwert der Folge $(a_n)_{n \in \mathbb{N}}$ mit $a_n = f(a_{n-1})$. Dann gilt: $a = f(a)$. Löse dann nach $a$ auf.

Eine Folge in der das wunderbar klappt ist folgende:

Sei \((a_n)_{n \in \mathbb{N}}\) eine Folge und definiert durch: \(a_0 = 2,~~~~~ a_n = \sqrt[3]{a_n^2+a_n-1}\).

Strukturelle Induktion

Bei der vollständigen Induktion iteriert man über eine natürliche Zahl und gelangt so, ab einer festen natürlichen Zahl \(n_0\) zu jeder beliebigen größeren natürlichen Zahl.

Die strukturelle Induktion nutzt allerdings nicht direkt Zahlen, sondern strukturen. Man hat eine sog. "Atomare Struktur" bzw. "Atomares Element", also in einem gewissen Sinn das oder die kleinsten Teilchen, gegeben. Diese Teilchen erfüllen die Aussage. Nun zeigt man, dass aus den Atomaren Elementen alle Strukturen gebildet werden können, über die in der Behauptung die Aussage getroffen wird und dass die Aussage bei jeder neuen Struktur richtig ist.

Insbesondere bietet sich die strukturelle Induktion bei komplexen Graphen, aussagelogischen Formeln und Wörtern an.

Beispiele

Voller, vollständiger Binärbaum

Sei G(V, E) ein Binärbaum.

G ist ein voller Binärbaum \(: \Leftrightarrow\) alle inneren Knoten von G haben den Verzweigungsgrad 2 G ist ein voller, vollständiger Binärbaum \(: \Leftrightarrow\) G ist ein voller Binärbaum und alle Blätter haben die gleiche Höhe

Behauptung \({\cal B} (n)\): Jeder volle, vollständige Binärbaum der Höhe \(n, n \in \mathbb{N}\) hat \(2^{n-1} - 1\) innere Knoten.
Beweis: durch strukturelle Induktion
I.A.: zeige \({\cal B} (1)\).
Ein voller, vollständiger Binärbaum der Höhe n = 1 besteht nur aus einem Knoten. Er hat also \(0 = 2^{n-1} - 1 = 2^{1-1} - 1 = 2^0 - 1 = 1 - 1 = 0\) innere Knoten. I.V.: Für beliebige, aber feste volle, vollständige Binärbäume G der Höhe n gilt: G hat \(2^{n-1} - 1\) innere Knoten.
I.S.: zeige \({\cal B} (n+1)\)
Für jeden vollen, vollständigen Binärbaum der Höhe \(n+1\) gibt es einen Teilgraphen T, der ein voller, vollständiger Binärbaum der Höhe n ist. \(\stackrel{I.V.}{\Rightarrow}\) T hat \(2^{n-1} - 1\) innere Knoten. Das sind auch innere Knoten von G. Da die Höhe von G um eins höher ist als die von T und sowohl G als auch T volle, vollstädige Binärbaume sind, kommen zu jedem der \(2^{n-1}\) Blätter aus T noch 2 Blätter. Dadurch hat G genau \(2^{n-1}\) innere Knoten mehr als T \(\Rightarrow\) G hat \(2^{n-1}-1+2^{n-1} = 2^n - 1\) innere Knoten \(\blacksquare\)

Aussagenlogische Ausdrücke

Die Idee habe ich aus dem Matheboard von "MoeMoeson". Bei diesem Beweis bin ich mir aber nicht sicher, ob es tatsächlich strukturelle Induktion ist :-/

Definition: Aussagenlogischer Ausdruck

  1. Jede Variable $p_i, i \in \mathbb{N}$ ist ein aussagenlogischer Ausdruck über V.
  2. Sind A und B aussagenlogische Ausdrücke über V, so sind auch $\neg A, A \land B, A \lor B, A \Rightarrow B, A \Leftrightarrow B, (A)$.
  3. Ein Wort über V ist nur dann ein aussagenlogischer Ausdruck über V, falls dies aufgrund endlich oftmaliger Anwendung von (i) und (ii) der Fall ist.

Behauptung Jeder aussagenlogischer Ausdruck endet entweder auf eine Variable oder auf eine schließende Klammer.
Beweis: durch strukturelle Induktion
I.A.: Jeder aussagenlogischer Ausdruck aus (i) endet auf eine Variable.
I.V.: Für beliebige, aber feste aussagenlogische Ausdrücke A gilt: A endet auf eine Variable oder eine schließende Klammer.
I.S.: Ein aussagenlogischer Ausdruck kann nur durch endlich häufige Anwendung von (i) und (ii) erzeugt werden (vgl. (iii)). (i) erfüllt die Bedingung laut I.V., (ii) auch. \(\blacksquare\)

Behauptung Für jeden aussagenlogischen Ausdruck A gibt es einen äquivalenten aussagenlogischen Ausdruck B, der nur \(\neg\) und \(\land\) als Operatoren verwendet.
Beweis: durch strukturelle Induktion
I.A.: Seien \(p_1, p_2\) aussagenlogische Variablen. Dann gilt: \(p_1 \lor p_2 = \neg (\neg p_1 \land \neg p_2)\) \(p_1 \Leftrightarrow p_2 = \neg (p_1 \land \neg p_2) \land \neg (\neg p_1 \land p_2)\) \(p_1 \Rightarrow p_2 = p_1 \land \neg p_2\) Für alle weiteren Ausdrücke aus (i) und (ii) gilt die Behauptung offensichtlich.

I.V.: Für beliebige, aber feste aussagenlogische Ausdrücke A gilt: Es gibt einen äquivalenten aussagenlogischen Ausdruck B, der nur \(\neg\) und \(\land\) als Operatoren verwendet.
I.S.: Ein aussagenlogischer Ausdruck kann nur durch endlich häufige Anwendung von (i) und (ii) erzeugt werden (vgl. (iii)). (i) und (ii) erfüllen die Bedingung laut I.V.. \(\blacksquare\)

Unendlich - Wann Induktion nicht funktioniert

Mit Induktion kann man Aussagen für beliebig große/kleine ganze Zahlen treffen. Allerdings eben nur für ganze Zahlen. Unendlich ist keine ganze Zahl. Also kann man auch keine Aussagen für "unendliche Aussagen" treffen.

Hier ein Beispiel:

Sei A eine Menge. A heißt offen \(:\Leftrightarrow \forall_{x \in A} : \exists_{\delta = \delta(x) > 0} : U_\delta(x) \subseteq A\) Es gilt: U und V sind offene Mengen \(\Rightarrow U \cap V\) ist offen.*

Nun könnte man den Trugschluss machen, dass der Schnitt unendlich vieler offener Mengen auch offen ist. Der falsche Induktionsbeweis würde in etwa so aussehen:

Voraussetungen: Seien \(M_i, i \in \mathbb{N}_0\) offene Mengen. Sei M eine Menge und definiert durch \(M := \displaystyle \bigcap_{i=0}^\infty M_i\).
Behauptung: M ist offen.
Beweis: durch vollständige Induktion
I.A.: Sei n = 1. Dann: \(\cap_{i=0}^1 M_i = M_0 \cap M_1\) ist laut * offen.
I.V.: Sei \(n \in \mathbb{N}\) beliebig, aber fest und es gelte: \(\displaystyle \bigcap_{i=0}^n M_i\) ist offen.
I.S.: \(\displaystyle \bigcap_{i=0}^{n+1} M_i = \bigcap_{i=0}^{n} M_i \cap M_{n+1}\). Nun gilt: \(\displaystyle \bigcap_{i=0}^{n} M_i\) ist per I.V. offen. \(M_{n+1}\) ist per Vorraussetzung offen. Der Schnitt von beiden ist wegen * offen. Da n beliebig groß werden kann, ist auch M offen \(\blacksquare\)

Allerdings gilt: \(\displaystyle \bigcap_{n=1}^\infty \left (1 - \frac{1}{n}, 2+\frac{1}{n} \right) = [1, 2]\), also ein Gegenbeispiel.

Der "Beweis" ist also offensichtlich falsch. Wo ist aber der Fehler? Man hat gezeigt, dass beliebig viele Schnitte von offenen Mengen wieder offen sind. Die Behauptung sagt aber, dass unendlich viele Schnitte offener Mengen wieder offen sind. Es gibt also einen unterschied zwischen "beliebig viel" und "unendlich".

Weitere Übungen

Quellen

Published


by

Category

German posts

Tags

Contact