Lernmodul: Beweisprinzipien

Functions

PreviousDominoeffekt beim Beweis mit vollständiger Indukti… 
  Beispiel mit einer Summe Next

Beweis mit vollständiger Induktion

Schauen wir uns den Beweis mit vollständiger Induktion nun genauer an.
Der Induktionsanfang ist einfach zu zeigen. Wir setzen den Startwert \(n_0\) in die Aussage ein und zeigen, dass die Aussage gilt.
Beim Induktionsschritt müssen wir Folgendes tun:
\(\tiny\blacksquare\enspace\)
Induktionsvoraussetzung:
Wir gehen davon aus, dass die Aussage \(A(n)\) wahr ist für ein beliebiges \(n\in\mathbb{N}\) mit \(n\ge n_0\).
\(\tiny\blacksquare\enspace\)
Induktionsbehauptung:
Wir behaupten, dass die Aussage für \(A(n+1)\) wahr ist.
\(\tiny\blacksquare\enspace\)
Induktionsbeweis:
Wir beweisen, dass unter der Annahme der Induktionsvoraussetzung die Induktionsbehauptung wahr ist.
Wir fassen das Prinzip der vollständigen Induktion wie folgt zusammen:
Prinzip der vollständigen Induktion:
Falls gilt
1.\(\enspace\)
Induktionsanfang:
\(\enspace\)
\(A(n_0)\) ist wahr
2.\(\enspace\)
Induktionsschritt:
\(A(n)\implies A(n+1)\) ist wahr für alle \(n\ge n_0\)
so ist \(A(n)\) wahr für alle \(n\ge n_0\).
Beispiel:
Wir zeigen mit vollständiger Induktion die folgende Aussage für \(n\ge 1\):
\(\qquad\)
\(\large\sum\limits_{i=1}^{n} \normalsize i=\dfrac{n(n+1)}{2}\)
Zum besseren Verständnis der Aussage schauen wir uns die Entwicklung der Summe genauer an und stellen Summe und Formel gegenüber.
\(\large\sum\limits_{i=1}^{n} \normalsize i=1+2+3+\ldots +n\)
\(\enspace n\enspace\)
\(\large\sum\limits_{i=1}^{n} \normalsize i\)
\(\dfrac{n(n+1)}{2}\)
\(1\)
\(1\)
\(\dfrac{1\cdot 2}{2}=1\)
\(2\)
\(1+2=3\)
\(\dfrac{2\cdot 3}{2}=3\)
\(3\)
\(1+2+3=6\)
\(\dfrac{3\cdot 4}{2}=6\)
\(4\)
\(1+2+3+4=10\)
\(\dfrac{4\cdot 5}{2}=10\)
Beweis mit vollständiger Induktion:
Induktionsanfang:
Wir setzen den Startwert \(n_0=1\) in die Aussage ein und zeigen, dass die Summe auf der linken Seite der Gleichung dem Quotienten auf der rechten Seite der Gleichung entspricht.
Linke Seite:
\(\qquad\)
\(\large\sum\limits_{i=1}^{1}\normalsize i=1\)
Rechte Seite:
\(\qquad\)
\(\dfrac{1\cdot (1+1)}{2}=\dfrac{2}{2}=1\)
Also sind linke und rechte Seite gleich und der Induktionsanfang ist somit wahr.
Induktionsschritt:
Induktionsvoraussetzung:
\(\qquad\)
Wir nehmen an, dass für ein festes, aber beliebiges \(n\) gilt:
\(\qquad\)
\(\sum\limits_{i=1}^{n} i=\dfrac{n(n+1)}{2}\qquad (*)\)
Induktionsbehauptung:
\(\qquad\)
Wir behaupten, dass dann auch gilt:
\(\qquad\)
\(\large\sum\limits_{i=1}^{n+1} \normalsize i=\dfrac{(n+1)((n+1)+1)}{2}=\dfrac{(n+1)(n+2)}{2}\)
Induktionsbeweis:
\(\qquad\)
Wir beginnen mit der linken Seite der Behauptung und spalten die Summe in die Summe über die ersten \(n\) Glieder und in das letzte Glied auf. Sollten Sie unsicher im Rechnen mit Summen sein, dann schauen Sie im Kurs "Mathematische Grundlagen" nach. Dort wird das Rechnen mit Summen geübt.
\(\qquad\)
\(\large\sum\limits_{i=1}^{n+1} \normalsize i=\left(\large \sum\limits_{i=1}^{n} \normalsize i\right)+\left(\large\sum\limits_{i=n+1}^{n+1} \normalsize i\right)\) \(=\Bigg(\underbrace{\large\sum\limits_{i=1}^{n} \normalsize i}_{(*)}\Bigg)+n+1 \)
\(\qquad\)
Wir setzen für die Summe \(\large\sum\limits_{i=1}^{n} \normalsize i\) den Ausdruck \(\dfrac{n(n+1)}{2}\) ein, wie in der Induktionsvoraussetzung \((*)\) angegeben:
\(\qquad\)
\(\large\sum\limits_{i=1}^{n+1} \normalsize i=\dfrac{n(n+1)}{2}+n+1 \)
\(\qquad\)
Nun schreiben wir \((n+1)\) als Bruch mit dem Nenner \(2\):
\(\qquad\)
\(\large\sum\limits_{i=1}^{n+1} \normalsize i=\dfrac{n(n+1)}{2}+\dfrac{2(n+1)}{2} \)
\(\qquad\)
Wir klammern den Term \(\dfrac{n+1}{2}\) aus:
\(\qquad\)
\(\large\sum\limits_{i=1}^{n+1} \normalsize i=\dfrac{n+1}{2}\cdot (n+2) \)
\(\qquad\)
Dies ist genau die Induktionsbehauptung.
Durch den Induktionsbeweis haben wir gezeigt, dass der Induktionsschritt richtig ist und die Aussage nun wegen der vollständigen Induktion für alle \(n\in\mathbb{N}\) mit \(n\ge 1\) wahr ist.
\(\blacksquare\)
\(\enspace\)
 Quellen 
 Glossar 
PreviousDominoeffekt beim Beweis mit vollständiger Indukti… 
  Beispiel mit einer Summe Next