ZU DEN KURSEN!

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

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 werden einige Beispiele für die Anwendung der vollständigen Induktion aufgezeigt.

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 mit vollständiger Induktion!

Das bedeutet:

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

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. Es wird statt dem Einsetzen von $n = 2,3,4,...$ stattdessen $n = n + 1$ eingesetzt und geschaut, ob die linke und rechte Seite äquivalent sind. Es wird mit der linken Seite begonnen:

$n = n + 1$:

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


Dies kann man auch schreiben zu:

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

Es wird demnach von $i = 1, ..., n$ die Summe gebildet und für $n+1$ hinten draufaddiert.

Einsetzen von: $ \sum_{i = 1}^n i =  \frac{n(n+1)}{2}$:

$= \frac{n(n+1)}{2} + (n + 1) $

$= \frac{n(n+1)}{2} + \frac{2(n + 1)}{2}$

$= \frac{n(n+1)  + 2(n + 1)}{2}$

$= \frac{n^2 + 3n + 2}{2}$


Für die rechte Seite wird direkt für $n = n+1$ eingesetzt:

$\frac{(n + 1) (n + 1 + 1)}{2}$

$= \frac{(n + 1) (n + 2)}{2}$

$= \frac{n^2 + 2n + n + 2}{2}$

$= \frac{n^2 + 3n + 2}{2}$

Es ist deutlich zu erkennen, dass sowohl die rechte als auch die linke Seite äquivalent sind.

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

Das bedeutet also:

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

1. Induktionsschritt:

 $A(1)$, dh. 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 (2 \cdot 1 - 1)\cdot (2 \cdot 1 + 1)}{3} = 1$

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

2. Induktionsschritt:

Zunächst wird die linke Seite betrachtet mit $i = n+1$:

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

Dies kann man auch schreiben zu:

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

Es wird demnach von $i = 1, ..., n$ die Summe gebildet und für $n+1$ hinten draufaddiert.

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

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

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

Alles auf einen Nennern bringen:

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

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

$= \frac{n(4n^2 + 2n - 2n - 1)}{3} + \frac{3(4n^2 + 4n + 1)}{3}$

$= \frac{4n^3 - n}{3} + \frac{12n^2 + 12n + 3}{3}$

$= \frac{4n^3 - n + 12n^2 + 12n + 3}{3}$

$= \frac{4n^3 + 12n^2 + 11n + 3}{3}$

Für die rechte Seite wird direkt für $n = n+1$ eingesetzt:

$ \frac{(n+1)(2(n+1)-1)\cdot (2(n+1)+1)}{3}$

$= \frac{(n+1) \cdot (2n+1) \cdot (2n+3)}{3}$

$= \frac{(2n^2+n+2n+1)(2n+3)}{3}$

$= \frac{(2n^2+3n+1)(2n+3)}{3}$

$= \frac{4n^3+6n^2 + 6n^2 + 9n + 2n + 3}{3}$

$= \frac{4n^3 + 12n^2 + 11n + 3}{3}$

Beide Seiten sind gleich, denmach handelt es sich hier um Vollständige Induktion.

Beispiel 3 zur vollständigen Induktion

Beispiel

Hier klicken zum Ausklappen

Aussage: $A(n)= n^2 + n$ ergibt immer eine durch zwei-teilbare, gerade Zahl! Diese Aussage gilt für alle natürlichen Zahlen $n \ge 0$. Prüfe diese Aussage mit vollständiger Induktion!

1. Induktionsschritt:

$n = 1: 1^2 + 1 = 2$  [Bedingung erfüllt]

2. Induktionsschritte:

$n = 2: 2^2 + 2 = 6$  [Bedingung erfüllt]
$n = 3: 3^2 + 3 = 12$  [Bedingung erfüllt]
$n = 4: 4^2 + 4 = 20$  [Bedingung erfüllt]

Auch hier zeigt sich, dass diese Aussage auf alle natürlichen Zahlen angewandt werden kann. Für $n+1$ gilt demnach:

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

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

Zusammenziehen, so dass obige Form $n^2 + n$ entsteht, da für diese bereits gezeigt wurde, dass es sich hierbei um Teiler von $2$ handelt:

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

Auch der zweite Term und dritte Term ist teilbar durch $2$. Einsetzen von $n = 1$:

$=  2 + 2 + 2$

Alle drei Terme sind teilbar durch 2 und damit ist auch die Summe teilbar durch 2.

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:

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

Es muss gezeigt werden, dass $3$ auch ein Teiler von $n = n+1$ ist:

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

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

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

Auch der zweite Term ist teilbar durch $3$. Einsetzen von $n = 1$:

$= 0 + 6$

Beide Terme sind teilbar durch 3 und damit ist auch die Summe teilbar durch 3.

Beispiel 5 zur vollständigen Induktion

Beispiel

Hier klicken zum Ausklappen

Gegeben sei der binomische Lehrsatz:

$\sum_{k = 0}^n {n \choose k} x^{n-k} y^k = (x+y)^n$

Prüfen Sie die Gültigkeit mittels vollständiger Induktion!

Es gilt:

Methode

Hier klicken zum Ausklappen

(1) ${n \choose 0} = 1$

(2) ${n \choose n} = 1$

(3) ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$


Zunächst wird der 1. Induktionsschritt für beide Seiten durchgeführt.


1. Induktionsschritt
: $n = 1$

$\sum_{k = 0}^1 {1 \choose k} x^{1-k} y^k = (x+y)^1$

${1 \choose 0} x^{1-0} y^0 + {1 \choose 1} x^{1-1} y^1 = x+y$

${1 \choose 0} x^{1-0} y^0 + {1 \choose 1} x^{1-1} y^1 = x+y$

(1) und (2) anwenden:

$1 \cdot x^{1-0} y^0 + 1 \cdot x^{1-1} y^1 = x+y$

$x + y = x+y$

Beide Seiten sind gleich, demnach gilt die Gleichung für den 1. Induktionsschritt. Als nächstes wird der 2. Induktionsschritt durchgeführt.

2. Induktionsschritt: $n = n+1$

$\sum_{k = 0}^{n+1} {n+1 \choose k} x^{n+1-k} y^k = (x+y)^{n+1}$

Es wird nun die rechte Seite weiter betrachtet und gezeigt, dass diese gleich der linken Seite ist:

$= (x+y)^{n+1}$

Das kann man auch schreiben zu:

$=(x +y)^n \cdot (x+y)^1$

Der erste Term ist genau der binomische Lehrsatz:

$= \sum_{k = 0}^n {n \choose k} x^{n-k} y^k \cdot (x+y)$

Auflösen der Klammer:

$=x \cdot  \sum_{k = 0}^n {n \choose k} x^{n-k} y^k + y \cdot  \sum_{k = 0}^n {n \choose k} x^{n-k} y^k$

Zusammenfassen von $x \cdot x^{n-k} = x^{n-k+1}$ und $y \cdot y^k = y^{k+1}$:

$= \sum_{k = 0}^n {n \choose k} x^{n-k+1} y^k + \sum_{k = 0}^n {n \choose k} x^{n-k} y^{k+1}$

Methode

Hier klicken zum Ausklappen

Anwendung von (3):

${n+1 \choose k} = {n \choose k} + {n \choose k-1}$


Es folgt demnach zunächst:

$\sum_{k = 0}^{n+1} {n+1 \choose k} = \sum_{k = 0}^{n+1} ({n \choose k} + {n \choose k-1})$

$\sum_{k = 0}^{n+1} {n+1 \choose k} = \sum_{k = 0}^{n+1} {n \choose k} + \sum_{k = 0}^{n+1} {n \choose k-1}$

Einsetzen:

$= \sum_{k = 0}^{n+1} {n \choose k} x^{n-k+1} y^k + \sum_{k = 0}^{n+1} {n \choose k-1} x^{n-(k-1)} y^{k - 1 + 1}$

Dabei muss der zweite Summand mit $k = k-1$ ersetzt werden für alle $k$. Der 1. Summand bleibt bestehen. 

$= \sum_{k = 0}^{n+1} {n \choose k} x^{n-k+1} y^k + \sum_{k = 0}^{n+1} {n \choose k-1} x^{n-k+1} y^k$

Beide Summanden sind gleich. Ausklammern:

$= (\sum_{k = 0}^{n+1} x^{n-k+1} y^k ({n \choose k} +  {n \choose k-1} )$

Methode

Hier klicken zum Ausklappen

Wieder Anwendung von (3):

$ {n+1 \choose k} = {n \choose k} + {n \choose k-1}$

$= \sum_{k = 0}^{n+1} {n+1 \choose k} x^{n-k+1} y^k$

Die rechte Seite entspricht der linken Seite. Der binomische Lehrsatz wurde mittels vollständiger Induktion bewiesen.