Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

In der letzten Vorlesung haben wir ja über verschiedene Beweismethoden gesprochen. Den

direkten Beweis, wo man einfach eine Kette von Schlussfolgerungen hat, von den Voraussetzungen

zu der Behauptung, die man beweisen möchte. Dann gibt es den indirekten Beweis. Da geht

man auch davon aus, dass die Voraussetzungen stimmen und nimmt an, dass die Behauptung

falsch ist. Das führt man dann zu einem Widerspruch. Das kann also nicht sein und dann muss also

die Behauptung gelten. Dieser indirekte Beweis oder Widerspruchsbeweis ist manchmal auch sehr

geeignet. Jetzt kommen wir zu der dritten Beweismethode, dem Beweis durch vollständige Induktion.

Damit kann man eine Folge von Aussagen beweisen. Für jede natürliche Zahl N aus N hat man

eine Aussage. Man will also zeigen, dass die Aussage für alle natürlichen Zahlen gilt,

für so endlich viele. Natürliche Zahlen kann man das immer durch Einsetzen verifizieren,

aber es gibt ja eine ganze unendliche Menge natürlicher Zahlen. Um zu beweisen, dass das

wirklich für alle natürlichen Zahlen gilt, braucht man eine Beweismethode, die vollständige

Induktion. Man hat also eine Folge von Aussagen. Aussage 1, Aussage 2, Aussage 3 und so weiter.

Die sollen für alle N aus den natürlichen Zahlen, also 1, 2, 3 und so weiter, bewiesen

werden. Wenn diese Aussagen an für alle natürlichen Zahlen stimmen sollen, dann müssen ja insbesondere

für die ersten paar natürlichen Zahlen stimmen. Das ist immer eine gute Idee, da einzusetzen.

Bei der Beweismethode muss man N gleich 1 einsetzen. Also zumindest A1 muss man einfach

durch Einsetzen prüfen. Das ist der sogenannte Induktionsanfang. Also dazu fängt man an

mit dem ersten Schritt, Induktionsanfang, die erste Aussage A1 gilt. Jetzt kann man

ja nicht alle natürlichen Zahlen einsetzen, deshalb braucht man hier das Beweisverfahren.

Jetzt kommt der zweite Schritt dieses Verfahrens, das ist die Induktionsvoraussetzung. Wir setzen

voraus, dass für eine natürliche Zahl N Element 1, 2, 3 und so weiter diese Aussage

A n gilt. Für N gleich 1 ist diese Induktionsvoraussetzung zum Beispiel schon erfüllt. Und davon ausgehend

ist jetzt der wesentliche Beweisschritt, der dritte Schritt in dem Induktionsbeweis, das

ist der Induktionsschritt. Da geht man von N nach N plus 1. In diesem dritten Schritt

darf man die Induktionsvoraussetzung verwenden. Also man geht davon aus, dass A n gilt und

zu zeigen ist dann, dass auch A n plus 1 gilt, also die Nachfolge Aussage. Zum Beispiel wenn

N gleich 1 ist, zeigt man hier A2 gilt. Also aus der Induktionsvoraussetzung 2 folgert

man durch richtige Schlüsse, dass auch A n plus 1 gilt, die Nachfolge in der Aussage.

Und wenn man das hat, dann gilt diese Aussage A n für alle natürlichen Zahlen. Und das

kann man sich so vorstellen, also A1 hat man ja geprüft. Dann gilt also diese Induktionsvoraussetzung

für N gleich 1 und mit dem Induktionsschritt folgert man dann, dass A2 auch gilt. Und

mit A2 kann man jetzt aber wieder in die Induktionsvoraussetzung mit N gleich 2 einsteigen. Und der Induktionsschritt

sagt, dann gilt es ja auch für die nachfolgende natürliche Zahl, das ist N gleich 3. Also

kommt man von der 2 auf die 3 und von der 3 auf die 4. Und nach der Konstruktion dieser

natürlichen Zahlen kommt man so nach endlich vielen Schritten zu jeder gegebenen festen

natürlichen Zahl. Also man erreicht alle natürlichen Zahlen. Also hat man hiermit bewiesen,

dass diese Aussage A n für alle natürlichen Zahlen gilt. Das ist die abstrakte Beweismethode.

Wir werden das jetzt an zahlreichen Beispielen auch anschauen und dann verstehen Sie, wie

das funktioniert. Das ist ein sehr strukturierter Beweis. Also diese Struktur, die hat man immer

bei dem Beweis durch vollständige Induktion und das hilft Ihnen im Grunde, weil das so

eine feste Form ist, ein festes Format, das vorgegeben ist. Dann gilt die Aussage A n

für alle N aus den natürlichen Zahlen. Schauen wir uns also direkt das erste Beispiel an.

Beispiel 1. Da ist die Behauptung für alle N aus N gilt die Summe von i gleich 1 bis

n i. Also das ist jetzt, ich schreibe besser j gleich 1 bis n j. Also das ist hier nicht

das Komplettste i, sondern das war einfach nur ein zähl i. Also hier summiert man von

1 bis n die natürlichen Zahlen auf. Also das ist 1 plus 2 plus 3 plus und so weiter bis

plus n. Diese Summe, die kann man auch leicht direkt auswerten. Da kommt nämlich heraus

n mal n plus eins halbe. Das ist eine typische Summenformel. Man hat eine Summe mit n Termen