Kursangebot | Höhere Mathematik 1: Analysis und Lineare Algebra | Beispiele: Vollständige Induktion

Höhere Mathematik 1: Analysis und Lineare Algebra

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

Beispiel

Hier klicken zum Ausklappen

Die Gaußsche Summenformel stellt einen einfachen Fall von vollständiger Induktion dar:

Aussage: $1 + 2 + 3.... + n = \frac{n(n+1)}{2}$   (Die Herleitung dieser Formel ist hierbei irrelevant).

Prüfe diese Aussage mittels vollständiger 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:

Methode

Hier klicken zum Ausklappen

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

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:

Methode

Hier klicken zum Ausklappen

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

 
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}$       

 

Methode

Hier klicken zum Ausklappen

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


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:

Methode

Hier klicken zum Ausklappen

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

Hinweis

Hier klicken zum Ausklappen

Es wird demnach von $i = 1, ..., k$ die Summe gebildet und für $i = k+1$ am Ende des Terms aufaddiert. Wichtig ist hierbei, dass $i = k+1$ auf der linken Seite eingesetzt wird und der resultierende Term auf der rechten Seite ebenfalls berücksichtigt wird.


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

Beispiel

Hier klicken zum Ausklappen

Aussage: Die Summe $1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 $ der ungeraden Quadratzahlen bis $2n-1$ ist $\frac{n(2n-1)\cdot (2n+1)}{3}$.

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:

Methode

Hier klicken zum Ausklappen

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

 


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

Methode

Hier klicken zum Ausklappen

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


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:

Methode

Hier klicken zum Ausklappen

 (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$

Hinweis

Hier klicken zum Ausklappen

Wenn wir $i = k+1$ einsetzen, so erhalten wir auf der linken Seite $(2 (k+1) - 1)^2$. Diesen Term müssen wir auch auf der rechten Seite berücksichtigen.

 


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

Beispiel

Hier klicken zum Ausklappen

Aussage: $A(n)= n^2 + n$ ergibt stets eine durch zwei-teilbare, gerade Zahl! Diese Aussage gilt für alle natürlichen Zahlen $n \ge 0$. Prüfe diese Aussage mittels vollständiger 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

Beispiel

Hier klicken zum Ausklappen

Aussage: 3 ist stets ein Teiler von $A (n) = n^3 - n$ für alle $n \in \mathbb{N}$

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!