In diesem Artikel zeige ich dir, wie du quasi jede Summenformel durch vollständige Induktion beweisen kannst. Das Verfahren läuft nämlich sehr algorithmisch ab und im Prinzip scheitern die meisten Studenten nur an den ersten beiden Umformungen im Induktionsschritt.
In dem Video zeige ich den vollständigen Induktionsbeweis an 3 Beispielen und an 5 weiteren Problemen jeweils die wichtigen Schritt im Induktionsschritt.
Zunächst definieren wir die Problemklasse, um die es geht:
Sei \(\mathcal{A}(n)\) eine Aussage, die eine Summenformel der Form \(\sum_{k=k_0}^{n}{f(k)}=g(n)\) beschreibt. Diese soll für alle natürlichen Zahlen \(n\in\mathbb{N}_{\geq n_0}\) bewiesen werden. Es ist zu zeigen: \[ \forall n\in\mathbb{N}_{\geq n_0}:\sum\limits_{k=k_0}^{n}{f(k)}=g(n) \] 1. Induktionsanfang (Umwerfen des ersten Dominosteins
Teste, ob die Aussage \(\mathcal{A}(n)\) für den Startwert \(n=n_0\) wahr ist, indem du \(n_0\) in beide Seiten der Gleichung \[ \sum\limits_{k=k_0}^{n}{f(k)} = g(n) \] einsetzt und prüfst, ob \(\sum_{k=k_0}^{n_0}{f(k)}\) und \(g(n_0)\) gleich sind. Sind beide Seiten ungleich (\(\mathcal{A}(n_0)\) ist also keine wahre Aussage), so bist du an dieser Stelle bereits fertig und die Behauptung \(\forall n\in\mathbb{N}_{\geq n_0}:\sum_{k=k_0}^{n}{f(k)}=g(n)\) ist falsch
2. Induktionsvoraussetzung
Formuliere die Induktionsvoraussetzung:
- formalisiert: \(\exists n\in\mathbb{N}_{\geq n_0}:\sum_{k=k_0}^{n}{f(k)}=g(n)\) (bzw. \(\exists n\in\mathbb{N}_0:\sum_{k=k_0}^{n}{f(k)}=g(n)\)),
- verbalisiert: "Die Summe \(\sum_{k=k_0}^{n}{f(k)}\) kann für (mindestens) ein \(n\in\mathbb{N}_{\geq n_0}\) durch den Ausdruck \(g(n)\) berechnet werden."
3. Induktionsbehauptung
Formuliere die Induktionsbehauptung. Es ist zu zeigen:
- formalisiert: \(\sum_{k=k_0}^{n}{f(k)}=g(n) \Longrightarrow\sum_{k=k_0}^{n+1}{f(k)}=g(n+1)\),
- verbalisiert: "Unter der Voraussetzung, dass die Summe \(\sum_{k=k_0}^{n}{f(k)}\) für ein \(n\in\mathbb{N}\) (bzw. \(n\in\mathbb{N}_0\)) durch den Ausdruck \(g(n)\) berechnet werden kann, kann die Summe \(\sum_{k=k_0}^{n+1}{f(k)}\) durch den Ausdruck \(g(n+1)\) (mit dem direkten Nachfolger von \(n\)) berechnet werden."
4. Induktionsschluss (der Nachfolger eines beliebigen Dominosteins fällt um)
Beweise die Induktionsbehauptung, indem du zuerst \(\sum_{k=k_0}^{n+1}{f(k)}\) mit dem Summensplit \(\sum_{k=k_0}^{n+1}{f(k)}=\left(\sum_{k=k_0}^{n}{f(k)}\right)+f(n+1)\) aufspaltest. Verwende als Nächstes die Induktionsbehauptung, um \(\sum_{k=k_0}^{n}{f(k)}\) durch \(g(n)\) zu ersetzen. Forme den entstandenen Ausdruck \(g(n)+f(n+1)\) algebraisch so lange um, bis du \(g(n+1)\) erhältst.
5. Beweisende (z. B. mit der Beweisbox \(\square\)) kennzeichnen
Autor: Florian André Dalwigk
Zur weiteren Lektüre empfohlen z.B. https://www.mathelounge.de/507303/mathe-artikel-vollstandige-induktion und weitere Videos in den Kommetaren wie z.B. https://www.mathelounge.de/507303/mathe-artikel-vollstandige-induktion?show=601780#c601780 wieder zu einer Summenformel.
Dieser Artikel hat 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
