Vollständige Induktion/Einführung/Textabschnitt

Die natürlichen Zahlen sind dadurch ausgezeichnet, dass man mit ihnen zählen kann, d.h. dass man in ihnen ausgehend von ${}0$ durch den Übergang von ${}n$ zum Nachfolger ${}n'=n+1$ jede natürliche Zahl erreicht. Dies begründet die folgende Eigenschaft: Wenn ${}T\subseteq \mathbb {N}$ eine Teilmenge ist, die einerseits die ${}0$ enthält und die andererseits mit jedem ${}n\in T$ auch den Nachfolger enthält (also ${}n+1\in T$), so ist bereits ${}T=\mathbb {N}$. Mit dem Startglied ${}0$ folgt ja dann zunächst ${}1\in T$, sodann ${}2\in T$, sodann ${}3\in T$ u.s.w, und da dieser Zählprozess jede natürliche Zahl erreicht, gehört jede natürliche Zahl zu ${}T$. Diese Beobachtung ist die Grundlage der vollständigen Induktion.

Mathematische Aussagen, die von natürlichen Zahlen abhängen, können mit dem Beweisprinzip der vollständigen Induktion bewiesen werden. Die folgende Aussage begründet dieses Prinzip.

Satz

Für jede natürliche Zahl ${}n$ sei eine Aussage ${}A(n)$ gegeben. Es gelte

1. ${}A(0)$ ist wahr.
2. Für alle ${}n$ gilt: wenn ${}A(n)$ gilt, so ist auch ${}A(n+1)$ wahr.

Dann gilt ${}A(n)$ für alle ${}n$.

Beweis

Es sei

${}M={\left\{n\in \mathbb {N} \mid A(n){\text{ ist wahr}}\right\}}\,.$

Wir wollen zeigen, dass ${}M=\mathbb {N}$ ist, denn genau dies bedeutet, dass die Aussage für alle ${}n$ gilt. Nach der ersten Bedingung ist

${}0\in M\,.$

Nach der zweiten Voraussetzung gilt für ${}M$, dass aus ${}n\in M$ stets ${}n+1\in M$ folgt. Damit erfüllt ${}M$ beide Voraussetzungen im Induktionsprinzip für Mengen, so dass ${}M=\mathbb {N}$ gilt.

$\Box$

Der Nachweis von (der Gültigkeit von) ${}A(0)$ heißt dabei der Induktionsanfang und der Schluss von ${}A(n)$ auf ${}A(n+1)$ heißt der Induktionsschluss. Innerhalb des Induktionsschlusses nennt man die Gültigkeit von ${}A(n)$ auch die Induktionsvoraussetzung. In manchen Situationen ist die Aussage ${}A(n)$ erst für ${}n\geq n_{0}$ für ein gewisses ${}n_{0}$ (definiert oder) wahr. Dann beweist man im Induktionsanfang die Aussage ${}A(n_{0})$ und den Induktionsschluss führt man für ${}n\geq n_{0}$ durch.

Das folgende Standardbeispiel für einen Induktionsbeweis verwendet das Summenzeichen. Für gegebene (natürliche, reelle, komplexe) Zahlen ${}a_{1},\ldots ,a_{n}$ bedeutet

${}\sum _{k=1}^{n}a_{k}:=a_{1}+a_{2}+\cdots +a_{n-1}+a_{n}\,.$

Dabei hängen im Allgemeinen die ${}a_{k}$ in einer formelhaften Weise von ${}k$ ab. Entsprechend ist das Produktzeichen definiert, nämlich durch

${}\prod _{k=1}^{n}a_{k}:=a_{1}\cdot a_{2}{\cdots }a_{n-1}\cdot a_{n}\,.$

Insbesondere sind für ${}n\in \mathbb {N}$ die Potenzen durch

${}a^{n}=\prod _{i=1}^{n}a=a^{n-1}\cdot a=\underbrace {a\cdot a{\cdots }a} _{n{\text{-mal}}}\,$

definiert. Dabei gelten die Konventionen ${}0a=0$ und ${}a^{0}=1$ (die erste lässt sich auch über die Multiplikation begründen, die zweite ist aber auch sinnvoll). Als Rechenregeln für das Potenzieren gelten

1. ${}(a\cdot b)^{n}=a^{n}\cdot b^{n}\,$

2. ${}a^{n+m}=a^{n}\cdot a^{m}\,$

3. ${}(a^{n})^{m}=a^{nm}\,.$

Aufgabe

Beweise durch Induktion die folgende Formel für ${}n\geq 1$.

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

Lösung

Beim Induktionsanfang ist ${}n=1$, daher besteht die Summe links nur aus einem Summanden, nämlich der ${}1$, und daher ist die Summe ${}1$. Die rechte Seite ist ${}{\frac {1\cdot 2}{2}}=1$, so dass die Formel für ${}n=1$ stimmt.

Für den Induktionsschritt setzen wir voraus, dass die Formel für ein ${}n\geq 1$ gilt, und müssen zeigen, dass sie auch für ${}n+1$ gilt. Dabei ist ${}n$ beliebig. Es ist

${}{\begin{aligned}\sum _{k=1}^{n+1}k&=\left(\sum _{k=1}^{n}k\right)+n+1\\&={\frac {n(n+1)}{2}}+n+1\\&={\frac {n(n+1)+2(n+1)}{2}}\\&={\frac {(n+2)(n+1)}{2}}.\end{aligned}}$

Dabei haben wir für die zweite Gleichheit die Induktionsvoraussetzung verwendet. Der zuletzt erhaltene Term ist die rechte Seite der Formel für ${}n+1$, also ist die Formel bewiesen.

Aufgabe

Zeige durch vollständige Induktion, dass für jedes ${}n\in \mathbb {N}$ die Zahl

$6^{n+2}+7^{2n+1}$

ein Vielfaches von ${}43$ ist.

Lösung

Induktionsanfang. Für ${}n=0$ ist

${}6^{2}+7=43\,$

ein Vielfaches von ${}43$. Induktionsschritt. Es sei nun die Aussage für ${}n$ bewiesen und betrachten wir den Ausdruck für ${}n+1$. Dieser ist

${}{\begin{aligned}6^{n+1+2}+7^{2(n+1)+1}&=6\cdot 6^{n+2}+7^{2}\cdot 7^{2n+1}\\&=6\cdot 6^{n+2}+(6+43)7^{2n+1}\\&=6{\left(6^{n+2}+7^{2n+1}\right)}+43\cdot 7^{2n+1}\\&=6\cdot 43\cdot s+43\cdot 7^{2n+1}\\&=43\cdot {\left(6\cdot s+7^{2n+1}\right)},\end{aligned}}$

wobei im vorletzten Schritt die Induktionsvoraussetzung verwendet wurde (nämlich die Eigenschaft, dass $6^{n+2}+7^{2n+1}$ ein Vielfaches von ${}43$ ist). Daher ist diese Zahl ein Vielfaches von ${}43$.