03 Vollständige Induktion

3. Beweise mit vollständiger Induktion

Voraussetzung: 02 Folgen - Grundlagen (rekursive Folgen, Fibonacci)

3.1 Grundlage: Abspaltregel der Aussagenlogik

Abspaltregel (Modus Ponens)

Sind Aussagen $A$ und $A⟹B$ (“aus A folgt B”) wahr, dann ist auch $B$ wahr. $(A\wedge (A⟹B))\to B$ ist eine Tautologie (immer wahr).

Merksatz

Aus zwei wahren Aussagen $A$ und $A⟹B$ folgt zwingend, dass auch $B$ wahr ist. Dies ist das logische Fundament der gesamten Induktionstechnik.

3.2 Aussageform / Prädikat

Eine Induktionsbehauptung ist zunächst nur eine Aussageform, abhängig vom Parameter $n$ — keine Aussage, bis man $n$ konkret einsetzt.

Beispiel: $A(n):{\sum }_{k=1}^{n}k=1+2+3+\cdots +n=\frac{n\cdot (n+1)}{2}$

• $A(1):{\sum }_{k=1}^{1}k=1=\frac{1\cdot (1+1)}{2}$ — wahre Aussage
• $A(2):{\sum }_{k=1}^{2}k=1+2=3=\frac{2\cdot (2+1)}{2}$ — wahre Aussage
• $\forall n\in \mathbb{N}:A(n)$ — “für alle $n$ gilt $A(n)$”

Merksatz

Eine Aussageform wird erst durch Einsetzen eines konkreten $n$ zu einer echten, wahren oder falschen Aussage. Das ist dieselbe Unterscheidung wie im Fach Grundlagen und diskrete Strukturen zwischen Aussageform und Aussage.

Direkter Beweis derselben Formel (zur Einordnung)

Zur Einordnung: $A(n)$ lässt sich hier auch direkt (ohne Induktion) beweisen, mit dem klassischen Gauß-Trick:

$\begin{array}{c}S=1+2+\cdots +n\\ S=n+(n-1)+\cdots +1\end{array}\}\Rightarrow 2S=\underset{n\text{ mal}}{\underbrace{(n+1)+(n+1)+\cdots +(n+1)}}=n\cdot (n+1)$

$⟹{\sum }_{k=1}^{n}k=\frac{n\cdot (n+1)}{2}$

Warum steht da $2S$?

$S$ wird zweimal hingeschrieben: einmal vorwärts ($1+2+\cdots +n$), einmal rückwärts ($n+(n-1)+\cdots +1$). Beide Zeilen stellen denselben Wert $S$ dar, also ist ihre Summe $S+S=2S$ — unabhängig davon, wie man die Zeilen dann spaltenweise addiert.

Nicht jede Formel lässt sich so elegant direkt beweisen — vollständige Induktion ist die allgemeine Technik für Aussagen über alle natürlichen Zahlen.

---

3.3 Vollständige Induktion — Tiefe 1

Prinzip

$\underset{\text{Induktionsanfang + Induktionsschritt}}{\underbrace{A(1)\wedge \forall n\in \mathbb{N}:(A(n)⟹A(n+1))}}⟹\forall n\in \mathbb{N}:A(n)$

Dies folgt direkt aus der Abspaltregel: $A(1)$ ist wahr, und mit $A(1)⟹A(2)$ folgt $A(2)$, mit $A(2)⟹A(3)$ folgt $A(3)$, und so weiter — eine “Kettenreaktion”.

Eine Induktion besteht also immer aus zwei Teilen:

• Induktionsanfang: $A(1)$ gilt (Startfall)
• Induktionsschritt: $\forall n:A(n)⟹A(n+1)$ (von einem beliebigen $n$ auf den Nachfolger $n+1$ schließen)

Beispiel: Gaußsche Summenformel per Induktion

$\forall n\in \mathbb{N}:\underset{A(n)}{\underbrace{\sum _{k=1}^{n}k=\frac{n(n+1)}{2}}}$

Induktionsanfang ($n=1$):

Behauptung: ${\sum }_{k=1}^{1}k=\frac{1(1+1)}{2}$

Beweis: ${\sum }_{k=1}^{1}k=1=\frac{1(1+1)}{2}$ ✓ richtig

Induktionsschritt ($\forall n:A(n)⟹A(n+1)$):

Voraussetzung: ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$ (dies ist $A(n)$)

Behauptung: ${\sum }_{k=1}^{n+1}k=\frac{(n+1)(n+1+1)}{2}=\frac{(n+1)(n+2)}{2}$ (dies ist $A(n+1)$)

Beweis: ${\sum }_{k=1}^{n+1}k=1+2+\cdots +n+(n+1)={\sum }_{k=1}^{n}k+(n+1)$ $\underset{\text{Vor.}}{\underbrace{=}}\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}✓$

Merksatz

Induktionsanfang (ein Startfall) plus Induktionsschritt ($A(n)⟹A(n+1)$) beweisen die Aussage für alle $n$. Der entscheidende Trick im Beweis des Induktionsschritts: Man darf die Voraussetzung $A(n)$ als bereits bewiesen verwenden (hier beim Einsetzen von ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$) — das ist der ganze Witz der Induktion.

---

3.4 Vollständige Induktion — Tiefe 2

Manche Aussagen (insbesondere über rekursive Folgen mit zwei Vorgängern wie Fibonacci) brauchen eine stärkere Variante:

Prinzip (Tiefe 2)

$\underbrace{A(1)\wedge A(2)\wedge \forall n:(A(n)\wedge A(n+1)⟹A(n+2))}⟹\forall n\in \mathbb{N}:A(n)$

Hier braucht man zwei Startfälle ($A(1)$ und $A(2)$) und im Induktionsschritt zwei Voraussetzungen ($A(n)$ und $A(n+1)$), um auf $A(n+2)$ zu schließen.

Beispiel: Untere Abschätzung der Fibonacci-Folge

Sei $(a_n)$ die Fibonacci-Folge: $a_1=1,a_2=1,a_{n+2}=a_{n+1}+a_n$ für $n\ge 1$.

Behauptung: $\forall n\in \mathbb{N}:a_n\ge {\sqrt{2}}^{n-2}$

Induktionsanfang (beide Fälle $n=1$ und $n=2$):

Behauptung: $a_1\ge {\sqrt{2}}^{1-2}$ und $a_2\ge {\sqrt{2}}^{2-2}$

Beweis: $a_1=1\ge \frac{1}{\sqrt{2}}={\sqrt{2}}^{-1}={\sqrt{2}}^{1-2}✓$ $a_2=1\ge 1={\sqrt{2}}^0={\sqrt{2}}^{2-2}✓$

Induktionsschritt ($A(n)\wedge A(n+1)⟹A(n+2)$):

Voraussetzung: $a_n\ge {\sqrt{2}}^{n-2}$ und $a_{n+1}\ge {\sqrt{2}}^{n+1-2}={\sqrt{2}}^{n-1}$

Behauptung: $a_{n+2}\ge {\sqrt{2}}^{n+2-2}={\sqrt{2}}^n$

Beweis:

a_{n+2} &= a_{n+1}+a_n && \text{(Rekursionsformel)} \\ &\geq \sqrt{2}^{\,n-1} + \sqrt{2}^{\,n-2} = \sqrt{2}\cdot\sqrt{2}^{\,n-2} + \sqrt{2}^{\,n-2} \\ &= \sqrt{2}^{\,n-2}\cdot(\sqrt{2}+1) \\ &> \sqrt{2}^{\,n-2}\cdot 2 = \sqrt{2}^{\,n-2}\cdot\sqrt{2}^2 \\ &= \sqrt{2}^{\,n} \end{aligned}$$ Insgesamt: $a_{n+2} > \sqrt{2}^{\,n}$ ✓

Merksatz

Wenn die Rekursion zwei Vorgänger braucht (wie bei Fibonacci), braucht der Beweis auch zwei Startfälle und zwei Voraussetzungen im Induktionsschritt. Die “Tiefe” der Induktion richtet sich also danach, wie viele vorherige Glieder die Rekursion verwendet.

---

3.5 Allgemeine vollständige Induktion

Die allgemeinste Form erlaubt, sich im Induktionsschritt auf alle vorherigen Fälle zu stützen (nicht nur auf die letzten ein oder zwei):

Prinzip (allgemein)

$\forall n:A(n)\equiv A(1)\wedge \forall n\in \mathbb{N}:(A(1)\wedge A(2)\wedge \cdots \wedge A(n))⟹A(n+1)$

Achtung

Man muss genau aufpassen, ab welchem $n$ der Induktionsschritt tatsächlich funktioniert — manche Argumente brauchen z.B. $n\ge 2$ als Mindestvoraussetzung, obwohl der Induktionsanfang bei $n=1$ beginnt.

Typische Anwendung 1: Verallgemeinerte Summenformel

${\sum }_{k=1}^n{k}^2=1^2+2^2+3^2+\cdots +n^2=\frac{n\cdot (n+1)(2n+1)}{6}$

(Beweis analog zu 3.3, hier nicht ausgeführt — Übungsaufgabe.)

Typische Anwendung 2: n-te Ableitung einer Funktion

$f(x)=e^{2x}$

Man berechnet die ersten Ableitungen, um ein Muster zu erkennen: $f^{\prime }(x)=2\cdot e^{2x}$ $f^{\prime \prime }(x)=2\cdot 2\cdot e^{2x}=4\cdot e^{2x}$ $f^{\prime \prime \prime }(x)=4\cdot 2\cdot e^{2x}=8\cdot e^{2x}$

Vermutung: $f^{(n)}(x)=2^n\cdot e^{2x}$ für alle $n$.

Induktionsanfang ($n=0$):

Behauptung: $f^{(0)}(x)=e^{2x}\cdot 2^0$

Beweis: $f^{(0)}(x)=e^{2x}=2^0\cdot e^{2x}$ ✓ (die “0-te Ableitung” ist die Funktion selbst)

Induktionsschritt:

Voraussetzung: $f^{(n)}(x)=2^n\cdot e^{2x}$

Behauptung: $f^{(n+1)}(x)=2^{n+1}\cdot e^{2x}$

Beweis: $f^{(n+1)}(x)=(f^{(n)}(x){)}^{\prime }$ $(2^n\cdot e^{2x}{)}^{\prime }=2^n\cdot (e^{2x}{)}^{\prime }=2^n\cdot 2\cdot e^{2x}=2^{n+1}\cdot e^{2x}✓$

Merksatz

Im Induktionsschritt darf man sich auf alle vorherigen Fälle $A(1),\dots ,A(n)$ stützen, nicht nur auf den unmittelbaren Vorgänger — in der Praxis braucht man aber meistens (wie in diesem Beispiel) tatsächlich nur $A(n)$, um $A(n+1)$ zu zeigen. Die “allgemeine” Form ist eher eine theoretische Absicherung dafür, dass man bei Bedarf auch weiter zurückgreifen darf.

---

3.6 Zusammenfassung: Welche Induktionstiefe brauche ich?

Rekursion braucht…	Induktionsanfang	Induktionsschritt
1 Vorgänger (z.B. arithmetische/geometrische Folge)	$A(1)$	$A(n)⟹A(n+1)$
2 Vorgänger (z.B. Fibonacci)	$A(1)$ und $A(2)$	$A(n)\wedge A(n+1)⟹A(n+2)$
beliebig viele Vorgänger	$A(1)$	$A(1)\wedge \cdots \wedge A(n)⟹A(n+1)$

Die Faustregel: Die Anzahl der nötigen Startfälle und Voraussetzungen im Induktionsschritt richtet sich immer danach, wie viele vorherige Glieder die zu beweisende Aussage bzw. die zugrundeliegende Rekursion tatsächlich braucht.