Die vollständige Induktion ist ein Beweisprinzip, das sich zum Beweisen von Aussagen über Teilmengen der natürlichen Zahlen sehr gut eignet. Die Menge der natürlichen Zahlen ist induktiv, definiert d.h. sehr vereinfacht gesagt, dass es eine kleinste Zahl gibt und jede Zahl einen fest vorgegebenen Nachfolger hat. Und genau diese Tatsache machen wir uns bei der vollständigen Induktion zu Nutze. Wir beweisen für ein beliebiges Element aus N, dass die Aussage gilt. Das ist der Induktionsanfang. Dann kommt der in der Regel anspruchsvollere Teil, in dem wir beweisen, dass wenn die Aussage für eine natürliche aber feste Zahl n gilt (Induktionsvoraussetzung), dass sie dann auch für den Nachfolger, sprich (n+1), gilt. Und zusammen mit diesem Induktionsschritt haben wir die Aussage für alle natürlichen Zahlen gezeigt, die größer oder gleich n sind. Das kannst du dir vorstellen wie eine unendliche Kette von Dominosteinen. Der erste Stein ist der Induktionsanfang und mit dem Induktionsschritt schmeißen wir immer den nächsten Dominostein um. Denn schließlich haben wir mit dem Induktionsanfang bewiesen, dass die Aussage für eine konkrete natürliche Zahl n gilt und mit dem Induktionsschritt, dass sie für (n+1) gilt. Da die Aussage für (n+1) richtig ist, ist sie also auch für (n+2) richtig. Da sie für (n+2) gilt, gilt sie auch für (n+3), usw.
Beispiel: Gaußsche Summenformel
Das war jetzt sehr abstrakt. Am besten ist es, das ganze anhand eines Beispiels nachzuvollziehen. Nehmen wir dazu doch einfach mal die Gaußsche Summenformel. Diese ist eine Formel mit der gegeben einer natürlichen Zahl n, die Summe aus allen natürlichen Zahlen von 1 bis einschließlich n bestimmen lassen. Die Gauß-Summe von 4 ist also z.B. 1 + 2 + 3 + 4 = 10. Die Definition der Gaußschen Summenformel lautet:
\(\sum_{i=1}^n i = \frac{n(n+1)}{2}=\frac{n^2 + n}{2}\)
Auf der linken Seite der Gleichung siehst du ein Summenzeichen, dass eben einfach aussagt, dass wir alle natürlichen Zahlen von 1 bis n aufsummieren. Und die Aussage ist hier eben einfach, dass wir anstelle alle Zahlen aufzusummieren auch einfach n in den Term auf der rechten Seite einsetzen können und das gleiche Ergebnis erhalten. Dann lass uns mal beginnen, das ganze mit Hilfe von vollständiger Induktion zu beweisen.
Induktionsbehauptung:
Zu Beginn unserer Beweisführung notieren wir uns noch einmal welche Aussage wir beweisen möchten.
\(\text{Zu zeigen: }\ \sum_{i=1}^n i = \frac{n(n+1)}{2}=\frac{n^2 + n}{2}\ \text{fuer alle natuerlichen Zahlen}\)
Induktionsanfang:
Wir zeigen, dass unsere Aussage für eine natürliche Zahl n gilt. Da wir die Aussage für alle natürlichen Zahlen zeigen wollen beginnen wir mit der ersten natürlichen Zahl. Es gibt riesige Diskussionen darüber, ob die natürlichen Zahlen mit 0 oder 1 beginnen. Wir sagen in dem Beispiel einfach, dass sie mit 1 beginnen. Wir setzen also n=1 in unsere Induktionsbehauptung ein und schauen, ob eine wahre Aussage dabei herauskommt.
\( \text{Sei n=1}\\\sum_{i=1}^n i =\frac{n^2 + n}{2}<=>\\\sum_{i=1}^1 i=\frac{1^2 + 1}{2}<=>\\1=1\)
Die Aussage ist offensichtlich wahr.
Induktionsvoraussetzung:
Die Induktionsbehauptung ist wahr für beliebiges aber fixes n. Anfänglich erscheint es vielleicht schwer nachzuvollziehen wofür das gut ist, aber wir brauchen das gleich in unserem Induktionsschritt.
Induktionsschritt:
Nun haben wir eine natürliche Zahl n für die unsere Aussage gilt, nämlich 1. Nun kommt der knifflige Teil. Wir zeigen im Allgemeinen, dass wenn unsere Aussage für eine beliebige aber feste Zahl n gilt (Induktionsvoraussetzung), dass sie dann auch für den Nachfolger n+1 gilt. Formal sieht das dann so aus:
\(\sum_{i=1}^n i = \frac{n(n+1)}{2}\ =>\ \sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2}\)
Wir müssen nun zeigen, dass die Aussage auf der rechten Seite richtig ist und dürfen dafür dabei davon ausgehen, dass die Aussage auf der linken Seite für ein beliebiges aber festes n richtig ist. Das haben wir ja schon im Induktionsanfang gezeigt. Das ist leider die Stelle an der man etwas kreativ werden muss und wofür es nicht immer ein Patentrezept gibt. Wichtig ist aber an dieser Stelle die Induktionsvoraussetzung immer im Blick zu behalten. Wir dürfen die Induktionsvoraussetzung also in unserer Beweisführung verwenden und ggf. Terme ersetzen. Der Trick bei bei diesem Beweis ist das letzte Glied aus der Summe herauszuziehen und dann die Induktionsvoraussetzung anzuwenden.
\(\text{Zu zeigen: }\sum_{i=1}^{n+1} i =\frac{(n+1)(n+2)}{2}=\frac{n^2+3n+2}{2}\\\sum_{i=1}^{n+1} i = \\\sum_{i}^{n} i\ + n+1=\\\frac{n^2+n}{2}+n+1 =\text{(Induktionsvoraussetzung)}\\\frac{n^2+n+2}{2}+\frac{2n+2}{2}=\\\frac{n^2+3n+2}{2} \)
Unsere Beweisführung ist nun abgeschlossen und wir haben die Korrektheit der Gaußschen Summenformel bewiesen. Nochmal zusammengefasst: Wir haben zuerst im Induktionsanfang die Korrektheit der gaußschen Summenformel für die erste natürliche Zahl 1 bewiesen. Mit der Induktionsvoraussetzung haben wir festgehalten, dass die die Formel für ein beliebiges aber fixes n gilt. Im Induktionsschritt haben wir allgemein gezeigt, dass wenn sie für eine beliebig aber feste natürliche Zahl n gilt, dass sie dann auch für den Nachfolger (n+1) gilt. Und damit setzen wir eine unendliche Beweiskaskade in Gang. Mit dem Induktionsanfang haben wir die Korrektheit der Formel für n=1 gezeigt. Für die Erfüllung der Induktionsvoraussetzung wird die Gültigkeit der Formel mit einer beliebigen aber festen natürlichen Zahl n verlangt. Und bei n=1 ist eben genau dies der Fall. Mit dem Induktionsschritt folgt dann, dass die Aussage dann auch für den Nachfolger gilt, also auch für n=2. Aber für n=2 haben wir wieder eine natürliche Zahl für die die gaußsche Summenformel stimmt. Folglich liefert sie also auch für n=3 das richtige Ergebnis. Und so geht das bis in die Unendlichkeit weiter. Es folgt also demnach induktiv, dass die gaußsche Summenformel für jede beliebige natürliche Zahlen das korrekte Ergebnis liefert.
Ich hoffe dir hat meine Erklärung über die vollständige Induktion gefallen. Wenn du dir das Thema vollständige Induktion nochmal in Videoform erklären lassen möchtest und mehr über die Gaußsche Summenformel erfahren willst, dann schaue dir gerne dieses Video von dem guten Sebastian ein mal an.