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

In der letzten Vorlesung haben wir über Beweise durch vollständige Induktion gesprochen. Die

vollständige Induktion ist eine Beweismethode, mit der man Folgen von Aussagen beweisen kann.

Also man hat eine Aussage Nummer eins, dann Aussage Nummer zwei, Aussage Nummer drei und so weiter.

Also eine unendliche Folge von Aussagen. Und der Beweis durch vollständige Induktion funktioniert

in drei Schritten. Also man muss erstmal mit der Aussage eins anfangen und die prüfen. Und wenn die

gilt, dann macht man die Induktionsvoraussetzung, dass eine Aussage n gilt für ein n größer

gleich eins. Und damit beweist man dann, dass auch die Nachfolgen der Aussage gilt. Und damit

kann man sich dann vorhangeln, sodass man damit gezeigt hat, dass die Aussage für alle

natürlichen Zahlen gilt. Das schauen wir uns nochmal an einem Beispiel an. Folgende Aussage,

n ist zu beweisen. Zwei hoch n ist echt größer als n Quadrat. Also das ist diese Ungleichung,

um die es geht. Und was ist die Behauptung? Behauptung a n gilt für alle n größer gleich fünf.

Wenn Sie da die drei zum Beispiel einsetzen, haben Sie hier auf der linken Seite die acht und rechts

die neun. Also dann gilt diese Ungleichung nicht. Wir fangen hier bei der fünf an. Also es ist immer

wichtig zu wissen, ab wann das gilt. Die Aussage eins, die wäre ja hier zwei größer eins, das gilt.

Aber Aussage zwei, zwei Quadrat größer zwei Quadrat ist falsch. Da steht ja echt größer und hier haben

wir auf beiden Seiten eine vier. Bei der Aussage drei haben wir dann zwei hoch drei. Das ist gleich

acht größer neun ist auch falsch. Aussage vier, da haben wir zwei hoch vier, das ist 16 und die rechte

Seite ist vier Quadrat, das ist auch 16. Aber weil er echt größer ist, ist das auch falsch. Und deshalb

fangen wir hier bei n gleich fünf an. Davor geht es nicht. Also obwohl die Aussage für die eins ja

stimmt, haben wir dazwischen eine Lücke und deshalb können wir es erst ab der fünf beweisen. Daher

hier Induktionsanfang bei n gleich fünf. Der Induktionsanfang ist der erste Schritt des Beweises

durch vollständige Induktion. Dieser Beweis ist ja sehr klar strukturiert, also man kann immer diese

drei Elemente deutlich unterscheiden. Induktionsanfang. Die Aussage Nummer fünf ist zwei hoch fünf,

das muss man jetzt ausrechnen. Das ist zwei mal zwei hoch vier, also 32 und das ist größer als 25 und

das ist 15 Quadrat. Also das gilt. Dann kommt die Induktionsvoraussetzung. Die Induktionsvoraussetzung

sagt, es gilt diese Ungleichung a n, also zwei hoch n größer n Quadrat für ein n größer gleich fünf.

Also wir wissen, das gilt irgendwann und versuchen zu zeigen im Induktionsschritt,

dass es dann auch für n plus eins gilt.

Also drittens Induktionsschritt von n auf n plus eins. Die linke Seite für n plus eins ist ja zwei hoch n plus eins.

Und wir wollen zeigen, dass es dann größer als n plus eins in Klammern zum Quadrat und dabei

speisen wir die Induktionsvoraussetzung ein. Also wir müssen irgendwo das zwei hoch n auch haben,

aber das zwei hoch n plus eins ist ja gleich zwei mal zwei hoch n. Hier kommt das zwei hoch n vor

und man kann die Induktionsvoraussetzung hier einspeisen. Nach Induktionsvoraussetzung ist das größer als zwei mal n Quadrat.

Und jetzt müssen wir nur noch die zwei n Quadrat nach unten abschätzen durch n plus eins in Klammern zum Quadrat,

aber das ist nicht so schwierig. Zweimal n Quadrat ist ja n Quadrat plus n Quadrat. Das n Quadrat kommt ja in n plus eins

in Klammern zum Quadrat vor. N plus eins in Klammern zum Quadrat würden Sie ja nach der binomischen Formel ausmultiplizieren.

Dann haben Sie n Quadrat plus zwei n plus eins. Das n Quadrat haben wir schon, also n Quadrat hier muss größer sein als zwei n plus eins.

Aber unser n ist ja größer als fünf, also insbesondere größer als vier. Das ist also größer als n Quadrat plus vier mal n.

Das n Quadrat ist ja n mal n und unser n ist größer als fünf. Fünf ist größer als vier, also das ist größer als n Quadrat plus vier mal n.

Und das ist gleich n Quadrat plus zwei n plus zwei n. Ja, und jetzt haben Sie schon n Quadrat plus zwei n.

Jetzt brauchen Sie nur noch die eins, aber da steht ja sogar noch ein n, ein zwei n hinten. Das ist also natürlich größer als eins.

Das ist ja eine natürliche Zahl und das ist gleich n plus eins in Klammern zum Quadrat.

Also bei diesen Ungleichungen müssen Sie natürlich immer wissen, wo Sie am Ende ankommen wollen.

Man kann das ja von beiden Seiten hinschreiben. Sie wollen am Ende ja n plus eins in Klammern zum Quadrat haben und das kennen Sie ja.

Und dann müssen Sie halt auf diese Terme kommen und so sind diese Schritte zu erklären. Also man will ja am Ende da auskommen.

Und das ist jetzt ja genau die Ungleichung, die wir beweisen wollen mit einem Echtgröße, wo auf der linken und der rechten Seite das n von unserer Aussage in dem farbigen Kasten, in dem weißen Kasten, wo da das n ersetzt ist durch n plus eins.

Also hier steht jetzt zwei hoch n plus eins statt zwei hoch n und unten steht n plus eins in Klammern zum Quadrat statt n Quadrat.

Also damit haben wir gezeigt, dass a n plus eins gilt. Das heißt a n plus eins gilt und damit ist dieser Induktionsschritt auch vollständig.

Mit dieser vollständigen Induktion haben wir gezeigt, dass diese Ungleichung a von n für alle n größer oder gleich fünf gilt.