Beispiele: Vollständige Induktion

In diesem Beispiel zeigen wir einige Beispiele für die Anwendung der vollständigen Induktion.

Beispiel 1 zur vollständigen Induktion

Die linke Seite der obigen Aussage ist nichts anderes alls die Summe der natürlichen Zahlen:

Demnach ergibt sich die obige Aussage zu:

1. Induktionsschritt:

(linke Seite):

(rechte Seite):

2. Induktionsschritt: 

und   (Aussage stimmt)

  (Aussage stimmt)

Dies lässt sich bis unendlich (theoretisch) fortführen. Wir setzen also , dabei ist eine beliebige Zahl:

 
Gilt dieser Ausdruck für , so gilt er auch für jede darauffolgende Zahl . Wir setzen nun ein:

Um Gleichung (2) zu beweisen betrachten wir Gleichung (1) und berücksichtigen , indem wir dieses am Ende der Gleichung (auf beiden Seiten) hinzuaddieren:

Der nächste Schritt ist nun, dass Gleichung (2) und (3) miteinander verglichen werden sollen. Sind also die beiden Ausdrücke identisch?

Beide berücksichtigen die Summe von bis . In der ersten Gleichung hingegen, ist die Zahl innerhalb der Summe berücksichtigt, in der zweiten Gleichung als Summand hinten angehängt.

 
Wir beginnen mit Gleichung (3):

                         |auf einen Nenner bringen

          |Zusammenfassen

 
Als nächstes betrachten wir die Gleichung (2):

                                 |Zusammenfassen

 
Das Ergebnis ist identisch, wir haben also den Beweis erbracht, dass die obige Aussage wahr ist!

Beispiel 2 zur vollständigen Induktion

Wir können hier die linke Seite wieder in Summenform schreiben:

1. Induktionsschritt:

 , d. h. die Aussage gilt für .

Einsetzen von :

(linke Seite):

(rechte Seite):

Die Behauptung ist im Fall richtig.

2. Induktionsschritt:

Einsetzen von :

(linke Seite):

(rechte Seite):

Auch für ist diese Aussage wahr. Wir müssen uns jetzt die Frage stellen, ob die Aussage für alle natürlichen Zahlen gilt.

Wir setzen wieder , dabei ist eine beliebige Zahl:

Gilt dieser Ausdruck für , so gilt er auch für jede darauffolgende Zahl . Wir setzen nun ein:

Um Gleichung (2) zu beweisen betrachten wir Gleichung (1) und berücksichtigen , indem wir dieses am Ende der Gleichung (auf beiden Seiten) hinzuaddieren:

Der nächste Schritt ist nun, dass Gleichung (2) und (3) miteinander verglichen werden sollen. Sind also die beiden Ausdrücke identisch?

Beide berücksichtigen die Summe von bis . In der ersten Gleichung hingegen, ist die Zahl innerhalb der Summe berücksichtigt, in der zweiten Gleichung als Summand hinten angehängt.

Wir beginnen mit der Gleichung (3):

Alles auf einen Nenner bringen:

Klammern auflösen:

Binomische Formel anwenden:

 
Als nächstes betrachten wir die Gleichung (2) und fassen diese so weit wie möglich zusammen:

 
Wir erhalten für beide Gleichungen dasselbe Ergebnis, also dieselbe rechte Seite. Damit ist die Aussage wahr!

Beispiel 3 zur vollständigen Induktion

Hier mal ein anderer Aufgabentyp zur vollständigen Induktion:

1. Induktionsschritt

2 ist eine gerade Zahl und damit durch 2 teilbar!

2. Induktionsschritt:

Induktionsvoraussetzung: Angenommen die Aussage gilt für , d.h. ist eine gerade Zahl.

Zu zeigen ist das diese Behauptung auch für gilt:

So zusammenfassen, dass die Induktionsvoraussetung gegeben ist:

Da nach Induktionsvoraussetzung eine gerade Zahl ist und ein ganzzahliges Vielfaches von 2 ist, ist auch die Summe eine gerade Zahl.

Beispiel 4 zur vollständigen Induktion

1. Induktionsschritt:

ist ein Teiler von .

2. Induktionsschritt:

Induktionsvoraussetzung: Angenommen die Aussage gilt für , d.h. ist stets ein Teiler von 3.

Zu zeigen ist das diese Behauptung auch für gilt:

(n+1)^3 - (n + 1)3$ handelt (Induktionsvorraussetzung):

Auch der zweite Term ist infolge der Multiplikation der Klammer mit 3 immer durch 3 teilbar!