Vollständige Induktion: Beispiele – Serlo „Mathe für Nicht-Freaks“

Schema zum Beweis mit vollständiger Induktion

Beispiel einer Aufgabe mit Hilfe der vollständigen Induktion

Die folgende Übersicht hilft dir, einen Beweis mit Hilfe vollständiger Induktion zu führen, wie sie im Abschnitt „Prinzip der vollständigen Induktion“ definiert wurde. Zwar kannst du viele Induktionsbeweise nach diesem Schema lösen, aber es gibt auch Ausnahmen!

Lösungsweg: Beweis auf Schmierblatt finden

Kein Beweis fällt vom Himmel – so auch kein Induktionsbeweis. Bevor du den gesuchten Beweis aufschreiben kannst, musst du ihn erst einmal finden (klingt logisch, oder?  ). Das folgende Schema soll dir dabei helfen. Die einzelnen Fragen beziehungsweise Schritte kannst du auf Schmierpapier oder im Kopf durchführen. In den nächsten Abschnitten wird dieses Schema an typischen Induktionsaufgaben erklärt und exemplarisch angewandt.

Vorüberlegungen

Fragen/Schritt	Anmerkungen
Über welche Variable wird die Induktion geführt?	Oftmals ist diese Variable $n$ (hat sich so etabliert). Dies muss aber nicht sein und ist aufgabenabhängig.
Wie lautet die Aussageform, deren Allgemeingültigkeit zu beweisen ist?	Mach dir klar, wie die Aussageform aussieht, deren Allgemeingültigkeit du beweisen möchtest/musst.

Induktionsanfang

Fragen/Schritt	Anmerkungen
Welchen Wert hast du für die Induktionsvariable im Induktionsanfang? Welches ist die kleinste natürliche Zahl für den Induktionsanfang?	Meistens geht aus der Aufgabenstellung hervor, wie der Induktionsanfang lautet. Manchmal ist dies aber nicht der Fall und du musst den Induktionsanfang selbst herausfinden, etwa durch Probieren.
Wie lautet die zu beweisende Aussage für den Induktionsanfang	Setze in die Aussageform die oben gefundene Zahl für den Induktionsanfang ein.
Finde einen Beweis für den Induktionsanfang	Hier musst du den Beweis für die oben gefundene Aussage finden. Bei Gleichungen bzw. Ungleichungen gelingt dir dies zum Beispiel dadurch, dass du beide Seiten dieser Gleichung oder Ungleichung ausrechnest und die dadurch entstanden Werte vergleichst.

Induktionsschluss

Fragen/Schritt	Anmerkungen
Wie lautet die Induktionsvoraussetzung?	—
Wie lautet die Induktionsbehauptung?	Achte darauf, dass du die Induktionsbehauptung richtig formulierst, dass du also Klammern um $k+1$ setzt. Wenn du zum Beispiel die zu bearbeitende Aussageform $A(n)$ lautet „$2n+1$ ist ungerade“ lautet die Induktionsbehauptung $A(n=k+1)$ nicht „$2k+2$ ist ungerade“, sondern „$2(k+1)+1=2k+3$ ist ungerade“.
Finde den Beweis für den Induktionsschritt	Finde den Beweis dafür, dass unter Annahme der Induktionsvoraussetzung die Induktionsbehauptung gilt. Hier ist Kreativität gefragt, denn es gibt kein Beweisschema F. Aber meistens kannst du Aufgaben des gleichen oder ähnlichen Typs auf ähnliche Weise lösen (natürlich nicht immer). Das heißt, wenn du schon einige Induktionsbeweise gesehen oder durchgeführt hast, wird es dir leichter fallen, ähnliche Aufgaben zur vollständigen Induktion zu lösen. Es heißt mal wieder: Übung macht den Meister!

Beweis aufschreiben

Nachdem du dir den Beweis im Kopf oder auf Schmierpapier überlegt hast, geht es nun darum, einen sauberen und formal richtigen Beweis aufzuschreiben. Das folgende Schema gibt dir eine mögliche Struktur vor, wie du dies machen kannst:

Aussageform, deren Allgemeingültigkeit für $n\in \mathbb {N}$ bewiesen werden soll:

<Aussageform aufschreiben, welche bewiesen werden soll>

1. Induktionsanfang:

<gefundenen Beweis für den Induktionsanfang aufschreiben>

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

<Induktionsvoraussetzung formulieren>

2b. Induktionsbehauptung:

<Induktionsbehauptung formulieren>

2c. Beweis des Induktionsschritts:

<gefundenen Beweis für den Induktionsschritt aufschreiben>

Bedenke, dass das obige Beweisschema nur eine Möglichkeit ist, einen Beweis für vollständige Induktion aufzuschreiben, an dem du dich aber gut orientieren kannst. Sollten dir mal in einer Klausur, Test oder ähnlichem ein paar Punkte der vollständigen Induktion fehlen, schreibe die restlichen trotzdem auf. Oft werden sie auch schon bewertet.

Beweis einer Summenformel

Als erste Beispielaufgabe wähle ich den Beweis einer Summenformel, da dies ein typisches Anwendungsgebiet der vollständigen Induktion ist. Aber auch Produktgleichungen kannst du auf eine ähnliche Art lösen. Unsere Beispielaufgabe lautet:

„Beweise durch vollständige Induktion, dass $\sum _{k=1}^{n}(2k-1)^{2}={\frac {n\cdot (2n-1)\cdot (2n+1)}{3}}$ für alle natürlichen Zahlen $n$ ist.“

Beweisfindung auf dem Schmierblatt

Notwendige Vorüberlegungen

Frage: Über welche Variable wird die Induktion geführt?

$n$

Frage: Wie lautet die zu beweisende Aussageform?

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

Der Doppelpunkt steht dabei für „ist definiert durch“.

Induktionsanfang

Frage: Was ist die kleinste sinnvoll einsetzbare natürliche Zahl für $n$?

Nach der Aufgabenstellung ist $n\in \mathbb {N}$, also $n\in \{1,2,3,\ldots \}$. Die kleinste, sinnvoll einsetzbare natürliche Zahl ist damit die $1$ , womit die Induktion startet.

Frage: Wie lautet die zu beweisende Aussage für den Induktionsanfang?

Nach dem Einsetzen der $1$ für $n$ in der Aussageform erhalten wir die Aussage:

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

Aufgabe: Finde einen Beweis für den Induktionsanfang.

Bei Summenformeln musst du die im Induktionsanfang entstandene Gleichung verifizieren. Dies erreichst du durch Nachrechnen der beiden Seiten der Gleichung, welche identisch sein müssen. Bei unserer Aufgabe erhalten wir für den linken Term der Gleichung:

$\sum _{k=1}^{1}(2k-1)^{2}=(2\cdot 1-1)^{2}=1^{2}=1$

Für den rechten Term der Gleichung erhalten wir:

${\frac {1\cdot (2\cdot 1-1)\cdot (2\cdot 1+1)}{3}}={\frac {1\cdot 1\cdot 3}{3}}={\frac {3}{3}}=1$

Damit stimmen beide Seiten der obigen Gleichung überein, so dass $A(1)$ wahr ist.

Induktionsschritt

Frage: Wie lautet die Induktionsvoraussetzung?

Die Induktionsvoraussetzung $A(n=l)$ lautet $\sum _{k=1}^{l}(2k-1)^{2}={\frac {l\cdot (2l-1)\cdot (2l+1)}{3}}$. Wir benutzen hier den Variablennamen $l$, weil der Name $k$ bereits als Laufindex in der Summe vorkommt.

Frage: Wie lautet die Induktionsbehauptung?

Die Induktionsbehauptung $A(n=l+1)$ lautet $\sum _{k=1}^{l+1}(2k-1)^{2}={\frac {(l+1)\cdot (2\cdot (l+1)-1)\cdot (2\cdot (l+1)+1)}{3}}$.

Aufgabe: Finde den Beweis für den Induktionsschritt.

Wir müssen nun beweisen, dass unter Annahme der Induktionsvoraussetzung die Induktionsbehauptung gilt. Bei Summenformeln können meistens folgende Schritte identifiziert werden:

1. Zerlege die Summe der Induktionsbehauptung so, dass du die Induktionsvoraussetzung anwenden kannst.

Dazu musst du von der Summe so viele Summanden extra schreiben (oder in einer eigenen Summe zusammenfassen), dass die restliche Summe der Summe in der Induktionsvoraussetzung entspricht:

$\underbrace {\sum _{k=1}^{l+1}(2k-1)^{2}} _{\text{linke Seite der Induktionsbehauptung}}=\underbrace {\sum _{k=1}^{l}(2k-1)^{2}} _{\begin{matrix}{\text{hier lässt sich die}}\\{\text{Induktionsvoraussetzung einsetzen}}\end{matrix}}+\quad \underbrace {(2\cdot (l+1)-1)^{2}} _{\text{restlicher Summand}}$

2. Induktionsvoraussetzung anwenden.

Nun kann die Induktionsvoraussetzung verwendet werden:

${\begin{aligned}\sum _{k=1}^{l+1}(2k-1)^{2}=\ &{\color {OliveGreen}\sum _{k=1}^{l}(2k-1)^{2}}+(2\cdot (l+1)-1)^{2}\\&\quad {\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung verwenden}}\right.}\\=\ &{\color {OliveGreen}{{l\cdot (2l-1)\cdot (2l+1)} \over 3}}+(2\cdot (l+1)-1)^{2}\\\end{aligned}}$

Somit müssen wir jetzt folgende Gleichheit beweisen:

${\frac {l\cdot (2l-1)\cdot (2l+1)}{3}}+(2\cdot (l+1)-1)^{2}={\frac {(l+1)\cdot (2\cdot (l+1)-1)\cdot (2\cdot (l+1)+1)}{3}}$

3. Termumformungen finden, um eine Seite der Gleichung in die andere zu überführen.

Wie du auf die notwendigen Termumformungen kommst wird im Abschnitt „Terme – Notwendige Termumformungen finden“ beschrieben. Du kannst die obige Gleichung durch Termumformumgen zum Beispiel so beweisen:

${\begin{alignedat}{2}{\frac {l\cdot (2l-1)\cdot (2l+1)}{3}}+(2\cdot (l+1)-1)^{2}&\qquad &&{\frac {(l+1)\cdot (2\cdot (l+1)-1)\cdot (2\cdot (l+1)+1)}{3}}\\{\frac {l\cdot (2l-1)\cdot (2l+1)+3\cdot (2l+1)^{2}}{3}}&&&{\frac {(l+1)\cdot (2l+1)\cdot (2l+3)}{3}}\\{\frac {(2l+1)\cdot (l\cdot (2l-1)+3\cdot (2l+1))}{3}}&&&{\frac {(l+1)\cdot (2l+1)\cdot (2l+3)}{3}}\\{\frac {(2l+1)\cdot \left(2l^{2}-l+6l+3\right)}{3}}&&&{\frac {(2l+1)\cdot \left(2l^{2}+3l+2l+3\right)}{3}}\\{\frac {(2l+1)\cdot \left(2l^{2}+5l+3\right)}{3}}&\ =&&{\frac {(2l+1)\cdot \left(2l^{2}+5l+3\right)}{3}}\\\end{alignedat}}$

Beweis aufschreiben

Nun kann der Beweis nach dem obigen Schema aufgeschrieben werden.

Aussageform, deren Allgemeingültigkeit für $n\in \mathbb {N}$ bewiesen werden soll:

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

1. Induktionsanfang:

Für $n=1$ gilt:

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

Damit ist $A(1)$ wahr.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

$\sum _{k=1}^{l}(2k-1)^{2}={\frac {l\cdot (2l-1)\cdot (2l+1)}{3}}$

2b. Induktionsbehauptung:

$\sum _{k=1}^{l+1}(2k-1)^{2}={\frac {(l+1)\cdot (2\cdot (l+1)-1)\cdot (2\cdot (l+1)+1)}{3}}$

2c. Beweis des Induktionsschritts:

Es gilt:

${\begin{aligned}\sum _{k=1}^{l+1}(2k-1)^{2}&=\left(\sum _{k=1}^{l}(2k-1)^{2}\right)+(2\cdot (l+1)-1)^{2}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung verwenden}}\right.}\\[0.3em]&={\frac {l\cdot (2l-1)\cdot (2l+1)}{3}}+(2\cdot (l+1)-1)^{2}\\&={\frac {l\cdot (2l-1)\cdot (2l+1)+3\cdot (2l+1)^{2}}{3}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ (2l+1){\text{ ausklammern}}\right.}\\[0.3em]&={\frac {(2l+1)\cdot {\Big (}l\cdot (2l-1)+3\cdot (2l+1){\Big )}}{3}}\\&={\frac {(2l+1)\cdot (2l^{2}-l+6l+3)}{3}}\\&={\frac {(2l+1)\cdot (2l^{2}+2l+3l+3)}{3}}\\&={\frac {(2l+1)\cdot (2l\cdot (l+1)+3\cdot (l+1))}{3}}\\&={\frac {(l+1)\cdot (2l+1)\cdot (2l+3)}{3}}\\\end{aligned}}$

Damit ist die Induktionsbehauptung bewiesen.

Beweise von Ungleichungen

Ungleichung mit Summenformel

Aufgabe

Beweise, dass für alle $n\in \mathbb {N}$ die Ungleichung $\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}\geq {\frac {n}{2}}$ gilt.

Lösungsweg

Ungleichungen zu beweisen, ist ein weiteres Problem, bei der die vollständige Induktion oftmals eingesetzt wird. Hier sind die notwendigen Termumformungen meist raffinierter als beim Beweis von Summenformeln und man muss geschickte Abschätzungen für Terme finden.

Diese Beispielaufgabe beschreibt eine wichtige Abschätzung der harmonischen Reihe, die noch später im Buch relevant wird (die Folge $1,\,{\tfrac {1}{2}},\,{\tfrac {1}{3}},\ldots$ nennt man harmonische Folge, die Summe über diese Folge wird dementsprechend harmonische Reihe genannt). Die Aussageform, deren Allgemeingültigkeit zu beweisen ist, lautet:

$A(n):\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}\geq {\frac {n}{2}}$

Frage: Wie lautet der Induktionsanfang?

Fangen wir wie immer mit dem Induktionsanfang an. Wie oben ist die kleinste sinnvoll einsetzbare Zahl für $n$ die $1$. Die Aussage für $A(1)$, die wir beweisen müssen, lautet:

$A(1):\sum _{k=1}^{2^{1}-1}{\frac {1}{k}}\geq {\frac {1}{2}}$

Nun Rechnen wir die linke Seite der Ungleichung aus und erhalten:

$\sum _{k=1}^{2^{1}-1}{\frac {1}{k}}=\sum _{k=1}^{1}{\frac {1}{k}}={\frac {1}{1}}=1$

Da $1>{\tfrac {1}{2}}$ ist, ist damit die Ungleichung für $n=1$ und somit der Induktionsanfang bewiesen.

Nun geht es mit dem Induktionsschritt weiter. Nach Induktionsvoraussetzung nehmen wir an, dass $\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}\geq {\frac {n}{2}}$ für ein bestimmtes $n$ gültig ist. Unsere Aufgabe ist es, zu beweisen, dass unter dieser Annahme $\sum _{k=1}^{2^{n+1}-1}{\frac {1}{k}}\geq {\frac {n+1}{2}}$ auch gültig sein muss (beachte, dass wir für die Induktionsbehauptung überall $n$ durch $n+1$ ersetzt haben). Da wir in der vollständigen Induktion irgendwie die Induktionsvoraussetzung verwenden müssen, sollten wir die Summe so zerlegen, dass die Summe der Induktionsvoraussetzung auftritt (mal schauen, ob uns das gelingt und weiterhilft). Es ist $\sum _{k=1}^{2^{n+1}-1}{\frac {1}{k}}=\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}+\sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{k}}$.

Die rechte Seite der Ungleichung lässt sich auch als Summe schreiben (dadurch können wir beide Seiten besser miteinander vergleichen). Es ist ${\frac {n+1}{2}}={\frac {n}{2}}+{\frac {1}{2}}$ und somit lautet unsere zu beweisende Ungleichung:

$\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}+\sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{k}}\geq {\frac {n}{2}}+{\frac {1}{2}}$

Wir wissen nach der Induktionsvoraussetzung bereits, dass $\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}\geq {\frac {n}{2}}$ ist. Wenn wir nun beweisen könnten, dass $\sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{k}}\geq {\frac {1}{2}}$ wäre, wäre unsere Induktionsbehauptung bewiesen. Hier brauchen wir eine geschickte Abschätzung der Summe. Wir wissen, dass die Summanden ${\frac {1}{k}}$ mit wachsendem $k$ immer kleiner werden. Da wir die Summe nach unten abschätzen müssen, könnten wir alle Summanden mit dem kleinsten in der Summe vorkommenden Summanden abschätzen. Dies gibt uns die Möglichkeit, die Summe zu vereinfachen und daraus vielleicht eine Abschätzung zu bekommen. Der kleinste Summand wäre ${\frac {1}{2^{n+1}-1}}$. Da sich mit ${\frac {1}{2^{n+1}}}$ die Summe wahrscheinlich besser zusammenfassen lässt und ${\frac {1}{2^{n+1}-1}}>{\frac {1}{2^{n+1}}}$ ist, versuchen wir mal die Abschätzung mit ${\frac {1}{2^{n+1}}}$. Wir erhalten:

$\sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{k}}\geq \sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{2^{n+1}}}={\frac {1}{2^{n+1}}}\cdot \sum _{k=2^{n}}^{2^{n+1}-1}1$

Frage: Wie viele Summanden hat nun die Summe $\sum _{k=2^{n}}^{2^{n+1}-1}$?

Die Summe hat $2^{n+1}-1-2^{n}+1=2^{n}\cdot (2-1)=2^{n}$ Summanden.

Damit ergibt sich die Ungleichung:

$\sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{k}}\geq {\frac {1}{2^{n+1}}}\cdot \sum _{k=2^{n}}^{2^{n+1}-1}1={\frac {1}{2^{n+1}}}\cdot 2^{n}={\frac {1}{2}}$

Somit haben wir den Beweis für die Induktionsbehauptung gefunden.

Beweis

Die Aussageform, deren Allgemeingültigkeit zu beweisen ist, lautet:

$A(n):\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}\geq {\frac {n}{2}}$

1. Induktionsanfang:

Für $n=1$ ist

$\sum _{k=1}^{2^{1}-1}{\frac {1}{k}}=\sum _{k=1}^{1}{\frac {1}{k}}={\frac {1}{1}}=1\geq {\frac {1}{2}}$

2a. Induktionsvoraussetzung:

Sei $\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}\geq {\frac {n}{2}}$ .

2b. Induktionsbehauptung:

Wenn $\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}\geq {\frac {n}{2}}$ ist, dann ist $\sum _{k=1}^{2^{n+1}-1}{\frac {1}{k}}\geq {\frac {n+1}{2}}$.

2c. Beweis der Induktionsbehauptung:

Zunächst gilt für alle $n\in \mathbb {N} _{\geq 1}$:

$\sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{k}}\geq \sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{2^{n+1}}}={\frac {1}{2^{n+1}}}\cdot \sum _{k=2^{n}}^{2^{n+1}-1}1={\frac {1}{2^{n+1}}}\cdot 2^{n}={\frac {1}{2}}$

Damit ist wegen der Induktionsvoraussetzung:

$\sum _{k=1}^{2^{n+1}-1}{\frac {1}{k}}=\sum _{k=1}^{2^{n}-1}{\frac {1}{k}}+\sum _{k=2^{n}}^{2^{n+1}-1}{\frac {1}{k}}\geq {\frac {n}{2}}+{\frac {1}{2}}={\frac {n+1}{2}}$

Ungleichung ohne Summenformel

Aufgabe

Bestimmen Sie alle $n\in \mathbb {N} _{>0}$ für die gilt:

${\frac {4^{n}}{n+1}}<{\frac {(2n)!}{(n!)^{2}}}$

Lösungsweg

Vorüberlegung: Wie kommen wir an unsere $n$, welche die Ungleichung erfüllen?

Zunächst können wir für die ersten natürlichen Zahlen $n$ überprüfen, ob sie die Bedingung erfüllen:

${\begin{array}{l|rcl|c}n&{\dfrac {4^{n}}{n+1}}&<&{\dfrac {(2n)!}{(n!)^{2}}}&?\\\hline 1&2&<&2&\color {red}{f}\\\hline 2&{\frac {16}{3}}&<&{\frac {72}{12}}&\color {green}{w}\\\hline 3&16&<&20&\color {green}{w}\end{array}}$

Die Aussage ist für $n=2$ und $n=3$ wahr. Wir vermuten deswegen, dass die Ungleichung für alle $n\geq 2$ erfüllt ist.

Beweis

Die Ungleichung ${\frac {4^{n}}{n+1}}<{\frac {(2n)!}{(n!)^{2}}}$ ist für alle $n\geq 2$ erfüllt.

Aussageform, deren Allgemeingültigkeit für $n\in \mathbb {N}$ mit $n\geq 2$ bewiesen werden soll:

${\frac {4^{n}}{n+1}}<{\frac {(2n)!}{(n!)^{2}}}$

1. Induktionsanfang:

${\begin{array}{lrcl}&{\dfrac {4^{2}}{2+1}}&<&{\dfrac {(2\cdot 2)!}{(2!)^{2}}}\\[5pt]\iff &{\dfrac {16}{3}}&<&{\dfrac {4!}{4}}\\[5pt]\iff &{\dfrac {64}{12}}&<&{\dfrac {72}{12}}\end{array}}$

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

${\frac {4^{n}}{n+1}}<{\frac {(2n)!}{(n!)^{2}}}$

2b. Induktionsbehauptung:

${\frac {4^{n+1}}{n+2}}<{\frac {(2n+2)!}{((n+1)!)^{2}}}$

2c. Beweis des Induktionsschritts:

${\begin{array}{lrcl}&{\dfrac {4^{n+1}}{n+2}}&<&{\dfrac {\left(2(n+1)\right)!}{\left((n+1)!\right)^{2}}}\\[5px]\iff &{\dfrac {4^{n}\cdot 4}{n+2}}&<&{\dfrac {(2n+2)!}{((n+1)!)^{2}}}\\[5px]\iff &{\dfrac {4(n+1)}{n+2}}\cdot {\dfrac {4^{n}}{n+1}}&<&{\dfrac {(2n+2)(2n+1)(2n)!}{((n+1)\cdot n!)^{2}}}\\[5px]\iff &{\dfrac {4(n+1)}{n+2}}\cdot {\dfrac {4^{n}}{n+1}}&<&{\dfrac {(2n+2)(2n+1)(2n)!}{(n+1)^{2}\cdot (n!)^{2}}}\\[5px]\iff &\color {OliveGreen}{\dfrac {4(n+1)}{n+2}}\cdot \color {Orange}{\dfrac {4^{n}}{n+1}}&<&\color {OliveGreen}{\dfrac {(2n+2)(2n+1)}{(n+1)^{2}}}\cdot \color {orange}{\dfrac {(2n)!}{(n!)^{2}}}\\[5px]\end{array}}$

Aus der Induktionsvoraussetzung wissen wir bereits, dass ${\textstyle \color {Orange}{\frac {4^{n}}{n+1}}<\color {Orange}{\frac {(2n)!}{(n!)^{2}}}}$ gilt. Beweisen wir nun deswegen die fehlende Ungleichung:

${\begin{array}{lrcl}&{\dfrac {4(n+1)}{n+2}}&<&{\dfrac {(2n+2)(2n+1)}{(n+1)^{2}}}\\[5pt]\iff &4(n+1)^{3}&<&(2n+2)(2n+1)(n+2)\\[5pt]\iff &4(n+1)^{3}&<&2(n+1)\cdot 2\left(n+{\dfrac {1}{2}}\right)\cdot (n+2)\\[5pt]\iff &(n+1)^{3}&<&(n+1)\left(n+{\dfrac {1}{2}}\right)(n+2)\\[5pt]\iff &(n+1)^{2}&<&\left(n+{\dfrac {1}{2}}\right)(n+2)\\[5pt]\iff &n^{2}+2n+1&<&n^{2}+{\dfrac {5}{2}}n+1\\[5pt]\iff &2n&<&{\dfrac {5}{2}}n\end{array}}$

Die untere Ungleichung kann direkt miteinander verglichen werden und ist insbesondere für alle $n\geq 2$ wahr.

Beweis von Teilbarkeit

Aufgabe

Beweise, dass alle Zahlen der Form $a_{m}=m^{3}+5m$ mit $m\in \mathbb {N} _{\geq 0}$ durch 6 teilbar sind.

Lösungsweg

Als letztes Beispiel betrachten wir eine Aufgabe zur Teilbarkeit.

Frage: Über welche Variable ist die Induktion zu führen?

Die Induktionsvariable ist $m$.

Frage: Wie lautet die Aussageform, deren Allgemeingültigkeit zu beweisen ist?

$A(m):a_{m}=m^{3}+5m{\text{ ist durch }}6{\text{ teilbar.}}$

Im Induktionsanfang musst du wie bei den obigen Beispielen die kleinste sinnvoll einsetzbare Zahl einsetzen und die so ausgerechnete Zahl auf die gewünschte Teilbarkeit überprüfen (beachte dabei, dass jede ganze Zahl ein Teiler von $0$ ist).

Frage: Wie lautet der Induktionsanfang?

Der Induktionsanfang ist laut Aufgabenstellung für $m=0$ zu führen. Wir erhalten $a_{0}=0^{3}+5\cdot 0=0$, was durch sechs teilbar ist.

Frage: Wie lautet die Induktionsvoraussetzung?

Die Zahl $a_{m}=m^{3}+5m$ ist durch 6 teilbar.

Frage: Wie lautet die Induktionsbehauptung?

Die Zahl $a_{m+1}=(m+1)^{3}+5(m+1)$ ist durch 6 teilbar.

Im Beweis des Induktionsschritts hilft es meist, den erhaltenen Term, den du auf Teilbarkeit überprüfen sollst, durch Termumformungen auf eine Summe zu bringen, bei der du weißt, dass jeder seiner Summanden durch die gewünschte Zahl teilbar ist. Versuche dabei die Summe in so eine Struktur zu bringen, dass du die Induktionsvoraussetzung verwenden kannst.

Frage: Wie lautet der Beweis für den Induktionsschritt?

Wir erhalten nach obiger Vorgehensweise:

${\begin{aligned}a_{m+1}&=(m+1)^{3}+5(m+1)\\&=m^{3}+3m^{2}+3m+1+5m+5\\&=(m^{3}+5m)+6+(3m^{2}+3m)\\&=(m^{3}+5m)+6+3\cdot m\cdot (m+1)\\\end{aligned}}$

Nach Induktionsvoraussetzung wissen wir, dass $m^{3}+5m$ durch 6 teilbar ist. Der Summand $6$ ist auch durch sechs teilbar. Und wie sieht es mit $3\cdot m\cdot (m+1)$ aus? Da entweder $m$ oder $m+1$ gerade ist, ist entweder $m$ oder $m+1$ durch zwei teilbar. Damit muss auch $3\cdot m\cdot (m+1)$ durch 6 teilbar sein.

Beweis

Aufgabe: Schreibe den Beweis auf.

Die Aussageform, deren Allgemeingültigkeit zu beweisen ist, lautet:

$A(m):\ a_{m}=m^{3}+5m{\text{ ist durch }}6{\text{ teilbar.}}\!\,$

1. Induktionsanfang:

Für $m=0$ ist $a_{0}=0^{3}+5\cdot 0=0$ durch 6 teilbar.

2a. Induktionsvoraussetzung:

Es ist $m^{3}+5m$ durch 6 teilbar.

2b. Induktionsbehauptung:

$(m+1)^{3}+5(m+1)$ ist durch 6 teilbar.

2c. Beweis der Induktionsbehauptung:

Es ist $a_{m+1}=(m+1)^{3}+5(m+1)=m^{3}+3m^{2}+3m+1+5m+5$. Normalerweise würdest du jetzt Potenzen von m zusammenfassen zu $a_{m+1}=m^{3}+3m^{2}+8m+6$. Das ist zwar richtig, aber nicht zielführend. Vielmehr musst du den Term $m^{3}+5m$ der Induktionsvoraussetzung ins Spiel bringen, hier durch Umordnen, so dass sich $a_{m+1}=(m^{3}+5m)+3m^{2}+3m+6$ ergibt. Am Term $3m^{2}+3m$ kannst du nicht sofort ablesen, dass er für alle $m\in \mathbb {N}$ durch 6 teilbar ist. Ein weiterer Induktionsbeweis lässt sich jedoch vermeiden, denn wenn du ausklammerst $3m^{2}+3m=3m(m+1)$, ist die Teilbarkeit sofort zu erkennen, weil m oder m+1 durch 2 teilbar ist. Damit sind alle 3 Summanden von $a_{m+1}=(m^{3}+5m)+3m(m+1)+6$ durch 6 teilbar und der Induktionsbeweis in allen Einzelheiten nachvollziehbar geführt.