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:

$\sum_{i = 1}^n i$  

Demnach ergibt sich die obige Aussage zu:

1. Induktionsschritt:

$n = 1$

(linke Seite): $\sum_{i = 1}^1  i = 1$

(rechte Seite): $\frac{1(1+1)}{2} = 1$

2. Induktionsschritt: 

$n = 2: \sum_{i = 1}^2 1+2 = 3$ und $\frac{2(2+1)}{2} = 3$  (Aussage stimmt)

$n = 3: \sum_{i = 1}^3 1+2+3 = \frac{3(3+1)}{2} = 6$  (Aussage stimmt)

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

 
Gilt dieser Ausdruck für $n = k$, so gilt er auch für jede darauffolgende Zahl $k +1$. Wir setzen nun $k + 1$ ein:

$\sum_{i = 1}^{k+1} i  = \frac{(k + 1)(k+1+1)}{2}$       

Um Gleichung (2) zu beweisen betrachten wir Gleichung (1) und berücksichtigen $i = k + 1$, 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?

$\sum_{i = 1}^{k+1} i$

$ \sum_{i = 1}^k i + (k + 1)$

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

 
Wir beginnen mit Gleichung (3):

$ \sum_{i = 1}^k i + (k + 1) = \frac{k(k+1)}{2} + (k + 1) $                         |auf einen Nenner bringen

$\sum_{i = 1}^k i + (k + 1) = \frac{k(k+1)}{2} + \frac{2(k + 1)}{2}$          |Zusammenfassen

$\sum_{i = 1}^k i + (k + 1) = \frac{k(k+1)  + 2(k + 1)}{2}$

$\sum_{i = 1}^k i + (k + 1) = \frac{k^2 + 3k + 2}{2}$

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

$\sum_{i = 1}^{k+1} i = \frac{(k + 1)(k+2)}{2} \; \; $                                 |Zusammenfassen

$\sum_{i = 1}^{k+1} i = \frac{(k^2 + 2k + 1k + 2)}{2} \; \; $

$\sum_{i = 1}^{k+1} i = \frac{(k^2 + 3k + 2)}{2} \; \; $

 
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:

$\sum_{i = 1}^{n} (2i - 1)^2 = \frac{n(2n-1)\cdot (2n+1)}{3}$

1. Induktionsschritt:

 $A(1)$, d. h. die Aussage gilt für $n=1$.

Einsetzen von $n = 1$:

(linke Seite): $\sum_{i = 1}^1 (2 \cdot 1 - 1)^2 = 1$

(rechte Seite): $ \frac{1 \cdot (2 \cdot 1 - 1)\cdot (2 \cdot 1 + 1)}{3} = 1$

Die Behauptung ist im Fall $n = 1$ richtig.

2. Induktionsschritt:

Einsetzen von $n = 2$:

(linke Seite): $\sum_{i = 1}^2 (2 \cdot i - 1)^2 = (2 \cdot 1 - 1)^2 +  (2 \cdot 2 - 1)^2 = 10$

(rechte Seite): $ \frac{2 \cdot (2 \cdot 2 - 1)\cdot (2 \cdot 2 + 1)}{3} = 10$

Auch für $n = 2$ 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 $n = k$, dabei ist $k$ eine beliebige Zahl:

Gilt dieser Ausdruck für $n = k$, so gilt er auch für jede darauffolgende Zahl $k +1$. Wir setzen nun $k + 1$ ein:

Um Gleichung (2) zu beweisen betrachten wir Gleichung (1) und berücksichtigen $i = k + 1$, 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?

$\sum_{i = 1}^{k+1} (2i - 1)^2$

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2$

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

Wir beginnen mit der Gleichung (3):

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{k(2k-1)\cdot (2k+1)}{3} + (2(k+1) - 1)^2$    

Alles auf einen Nenner bringen:

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{k(2k-1)\cdot (2k+1)}{3} + \frac{3(2(k+1) - 1)^2}{3}$

Klammern auflösen:

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{k(4k^2 + 2k - 2k - 1)}{3} + \frac{3(2k+2 - 1)^2}{3}$

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{4k^3 - k}{3} + \frac{3(2k+1)^2}{3}$

Binomische Formel anwenden:

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{4k^3 - k}{3} + \frac{3(4k^2 + 4k +1)}{3}$

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{4k^3 - k}{3} + \frac{12k^2 + 12k +3}{3}$

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{4k^3 - k + 12k^2 + 12k +3}{3} $

$\sum_{i = 1}^{k} (2i - 1)^2 + (2(k+1) - 1)^2 = \frac{4k^3 + 12k^2 + 11k +3}{3} $

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

$\sum_{i = 1}^{k+1} (2i - 1)^2 = \frac{(k+1)(2(k+1)-1)\cdot (2(k+1)+1)}{3}$

$\sum_{i = 1}^{k+1} (2i - 1)^2 = \frac{(k+1)(2k+2-1)\cdot (2k+2+1)}{3}$

$\sum_{i = 1}^{k+1} (2i - 1)^2 = \frac{(k+1)(2k+1)\cdot (2k+3)}{3}$

$\sum_{i = 1}^{k+1} (2i - 1)^2 = \frac{(2k^2 + k + 2k + 1) \cdot (2k+3)}{3}$

$\sum_{i = 1}^{k+1} (2i - 1)^2 = \frac{(2k^2 + 3k + 1) \cdot (2k+3)}{3}$

$\sum_{i = 1}^{k+1} (2i - 1)^2 = \frac{(4k^3 + 6 k^2 + 6k^2 + 9k + 2k + 3 )}{3}$

$\sum_{i = 1}^{k+1} (2i - 1)^2 = \frac{(4k^3 + 12 k^2 + 11k + 3 )}{3}$

 
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

$n = 1: 1^2 + 1 = 2$

2 ist eine gerade Zahl und damit durch 2 teilbar!

2. Induktionsschritt:

Induktionsvoraussetzung: Angenommen die Aussage gilt für $n$, d.h. $n^2 + n$ ist eine gerade Zahl.

Zu zeigen ist das diese Behauptung auch für $n + 1$ gilt:

$(n+1)^2 + (n+1)$

$n^2 + 2n + 1 + n + 1$

So zusammenfassen, dass die Induktionsvoraussetung gegeben ist:

$(n^2 + n) + 2n +2$

$(n^2 + n) + 2(n +1)$

Da nach Induktionsvoraussetzung $(n^2 +n)$ eine gerade Zahl ist und $2(n+1)$ ein ganzzahliges Vielfaches von 2 ist, ist auch die Summe $(n^2 + n) + 2(n+1)$ eine gerade Zahl.

Beispiel 4 zur vollständigen Induktion

1. Induktionsschritt:

$n = 1: 1^3 - 1 = 0$ $\rightarrow \; 3$ ist ein Teiler von $0$.

2. Induktionsschritt:

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

Zu zeigen ist das diese Behauptung auch für $n + 1$ gilt:

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

$ (n+1) \cdot (n+1) \cdot (n+1) - (n+1)$

$ n^3 + 3n^2 + 3n + 1 - n - 1$

Zusammenziehen, so dass obige Form $n^3 -n$ entsteht, da für diese bereits gezeigt wurde, dass es sich hierbei um Teiler von $3$ handelt (Induktionsvorraussetzung):

$ (n^3 - n)+ 3n^2 + 3n$

$ (n^3 - n)+ 3(n^2 + n)$

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