01 – Vollständige Induktion

Mit Hilfe von vollständiger Induktion beweise man folgende Aussagen:

$\sum\limits_{k = 0}^n {k^2 = \frac{{n\left( {n+1} \right)\left( {2n+1} \right)}} {6}}$ für alle $n \in \mathbb{N}$
$\sum\limits_{k = 0}^n {k^3 = \frac{{n^2 \left( {n+1} \right)^2 }} {4}}$ für alle $n \in \mathbb{N}$
$\sum\limits_{k = 1}^{2n} {\frac{{(-1)^{k-1} }} {k} = \sum\limits_{K = 1}^n {\frac{1} {{n+k}}} }$ für alle $n \in \mathbb{N}\backslash \left\{ 0 \right\}$
Für alle $n \in \mathbb{N}$ ist 6 ein Teiler von $n^3 -n$
Für alle $n \in \mathbb{N}$ ist 11 ein Teiler von $2^{4n+3} +5^{2+n}$

Lösung

a )

Zunächst der Induktionsansatz für

n = 0: $\sum\limits_{k = 0}^0 {k^2 } = 0^2 = 0 = \frac{{0\left( {0+1} \right)\left( {2 \cdot 0+1} \right)}} {6}$

n = 1: $\sum\limits_{k = 0}^1 {k^2 } = 0^2 +1^2 = 1 = \frac{{1\left( {1+1} \right)\left( {2 \cdot 1+1} \right)}} {6}$

Nun der Induktionsschritt n+1:

Ziel ist:

$\sum\limits_{k = 0}^{n+1} {k^2 = \frac{{\left( {n+1} \right)\left( {n+1+1} \right)\left( {2\left( {n+1} \right)+1} \right)}} {6}}$

also:

links = rechts

$\sum\limits_{k = 0}^{n+1} {k^2 = \sum\limits_{k = 0}^n {k^2 +\left( {n+1} \right)^2 = } \frac{{n\left( {n+1} \right)\left( {2n+1} \right)}} {6}} +\left( {n+1} \right)^2 = \frac{{\left( {n+1} \right)\left( {n+1+1} \right)\left( {2\left( {n+1} \right)+1} \right)}} {6}$

$\frac{{n\left( {n+1} \right)\left( {2n+1} \right)}} {6}+\frac{{6\left( {n+1} \right)^2 }} {6}$ = $\frac{{\left( {n+1} \right)\left( {n+2} \right)\left( {2n+2+1} \right)}} {6}$

$\frac{{n\left( {n+1} \right)\left( {2n+1} \right)+6\left( {n+1} \right)^2 }} {6}$ = $\frac{{\left( {n+1} \right)\left( {n+2} \right)\left( {2n+2+1} \right)}} {6}$

$\frac{{\left( {n+1} \right)\left( {n\left( {2n+1} \right)+6\left( {n+1} \right)} \right)}} {6}$ = $\frac{{\left( {n+1} \right)\left( {n+2} \right)\left( {2n+3} \right)}} {6}$

$\frac{{\left( {n+1} \right)\left( {2n^2 +n+6n+6} \right)}} {6}$ = $\frac{{\left( {n+1} \right)\left( {2n^2 +3n+4n+6} \right)}} {6}$

$\frac{{\left( {n+1} \right)\left( {2n^2 +7n+6} \right)}} {6}$ = $\frac{{\left( {n+1} \right)\left( {2n^2 +7n+6} \right)}} {6}$

Damit sind wir schon fertig!

b )

Induktionsansatz für n = 0:
0 = 0 → stimmt.

Für den Induktionsschritt n+1 ist zu zeigen:

$\sum\limits_{k = 0}^{n+1} {k^3 = \frac{{\left( {n+1} \right)^2 \left( {n+1+1} \right)^2 }} {4}}$

Also nun Umformen der linken Seite zur rechten zunächst durch herabsetzen der Grenze und Anwenden der Induktionsvorraussetzung:

$\sum\limits_{k = 0}^{n+1} {k^3 } = \sum\limits_{k = 0}^n {k^3 } +\left( {n+1} \right)^3 = \frac{{n^2 \left( {n+1} \right)^2 }} {4}+\left( {n+1} \right)^3$

Nun nur noch umformen:

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

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

Ausklammern:

$= \frac{{\left( {n+1} \right)^2 \left( {n^2 +4\left( {n+1} \right)} \right)}} {4}$

$= \frac{{\left( {n+1} \right)^2 \left( {n^2 +4n+4} \right)}} {4}$

$= \frac{{\left( {n+1} \right)^2 \left( {n+2} \right)^2 }} {4}$

q.e.d.

c )

Induktionsansatz:

$n = 1:1-\frac{1} {2} = \frac{1} {2}$ stimmt.

Nun für n+1:
Zu zeigen:

$\sum\limits_{k = 1}^{2\left( {n+1} \right)} {\frac{{(-1)^{k-1} }} {k} = \sum\limits_{K = 1}^{n+1} {\frac{1} {{\left( {n+1} \right)+k}}} }$

Ansatz:

Zuerst wird die linke Seite der Gleichung wieder zur ursprünglichen Grenze hin umgeformt, denn dann kann man nachher einfach die Induktionsvorraussetzung auf den Term anwenden:

$\sum\limits_{k = 1}^{2\left( {n+1} \right)} {\frac{{\left( {-1} \right)^{k-1} }} {k}} = \sum\limits_{k = 1}^{2n+2} {\frac{{\left( {-1} \right)^{k-1} }} {k}} = \sum\limits_{k = 1}^{2n+1} {\frac{{\left( {-1} \right)^{k-1} }} {k}} +\frac{{\left( {-1} \right)^{\left( {2n+2} \right)-1} }} {{2n+2}}$

$= \sum\limits_{k = 1}^{2n} {\frac{{\left( {-1} \right)^{k-1} }} {k}} +\frac{{\left( {-1} \right)^{\left( {2n+1} \right)-1} }} {{2n+1}}+\frac{{\left( {-1} \right)^{\left( {2n+2} \right)-1} }} {{2n+2}}$

Termzusammenfassung:

$= \sum\limits_{k = 1}^{2n} {\frac{{\left( {-1} \right)^{k-1} }} {k}} +\frac{{\left( {-1} \right)^{2n} }} {{2n+1}}+\frac{{\left( {-1} \right)^{2n+1} }} {{2n+2}}$

Nun wird die Induktionsvorraussetzung angewendet:

$\sum\limits_{k = 1}^{2n} {\frac{{(-1)^{k-1} }} {k} = \sum\limits_{K = 1}^n {\frac{1} {{n+k}}} }$

Man sieht, dass der Exponent des zweiten Terms 2n ist, das bedeutet, der Exponent nimmt nur gerade Zahlen an, womit $\left( {-1} \right)^{2n}$ gleichbedeutend mit 1 ist.

Weiter sieht man, dass der Exponent des dritten Terms 2n+1 ist und somit immer ungerade.
$\left( {-1} \right)^{2n+1}$ ist also gleich 1.

Somit erhält man:

$= \sum\limits_{K = 1}^n {\frac{1} {{n+k}}} +\frac{1} {{2n+1}}+\frac{{-1}} {{2n+2}}$

Uns ist nun ja bekannt, dass $\sum\limits_{k = 1}^{2\left( {n+1} \right)} {\frac{{(-1)^{k-1} }} {k} = \sum\limits_{K = 1}^{n+1} {\frac{1} {{\left( {n+1} \right)+k}}} }$ sein soll, also müssen wir die Gleichung, die wir nun haben, nach ${\sum\limits_{K = 1}^{n+1} {\frac{1} {{\left( {n+1} \right)+k}}} }$ umformen. Dazu wird als erstes durch Verschiebung der Summationsgrenzen der Nenner angepasst:

$= \sum\limits_{K = 0}^{n-1} {\frac{1} {{n+\left( {k+1} \right)}}} +\frac{1} {{2n+1}}-\frac{1} {{2n+2}}$

Nun wird durch Veränderung der Grenzen weiter nach ${\sum\limits_{K = 1}^{n+1} {\frac{1} {{\left( {n+1} \right)+k}}} }$ umgeformt:

$= \sum\limits_{K = 1}^{n-1} {\frac{1} {{n+k+1}}} +\frac{1} {{n+0+1}}+\frac{1} {{2n+1}}-\frac{1} {{2n+2}}$

$= \sum\limits_{K = 1}^n {\frac{1} {{n+k+1}}} +\frac{1} {{n+0+1}}-\frac{1} {{n+n+1}}+\frac{1} {{2n+1}}-\frac{1} {{2n+2}}$

$= \sum\limits_{K = 1}^{n+1} {\frac{1} {{n+k+1}}} +\frac{1} {{n+0+1}}-\frac{1} {{n+n+1}}-\frac{1} {{n+\left( {n+1} \right)+1}}+\frac{1} {{2n+1}}-\frac{1} {{2n+2}}$

$= \sum\limits_{K = 1}^{n+1} {\frac{1} {{n+k+1}}} +\frac{1} {{n+1}}-\frac{1} {{2n+1}}-\frac{1} {{2n+2}}+\frac{1} {{2n+1}}-\frac{1} {{2n+2}}$

$= \sum\limits_{K = 1}^{n+1} {\frac{1} {{n+k+1}}} +\frac{1} {{n+1}}-\frac{1} {{2n+2}}-\frac{1} {{2n+2}}$

$= \sum\limits_{K = 1}^{n+1} {\frac{1} {{n+k+1}}} +\frac{1} {{n+1}}-\frac{1} {{2\left( {n+1} \right)}}-\frac{1} {{2\left( {n+1} \right)}}$

$= \sum\limits_{K = 1}^{n+1} {\frac{1} {{n+k+1}}} +\frac{1} {{n+1}}-\frac{1} {{\left( {n+1} \right)}}$

$= \sum\limits_{K = 1}^{n+1} {\frac{1} {{n+k+1}}}$

q.e.d.

Linke Seite zu rechter umgeformt. Fertig!

d )

n = 0: 0

n = 1: 0

n = 2: 6 stimmt

n = 3: 24 stimmt

Für n+1:

$\left( {n+1} \right)^3 -\left( {n+1} \right)$

Ausmultiplizieren und anschließend zusammenfassen:

$= \left( {n^2 +2n+1} \right)\left( {n+1} \right)-\left( {n+1} \right)$

$= \left( {n^3 +2n^2 +n+n^2 +2n+1} \right)-\left( {n+1} \right)$

$= \left( {n^3 +3n^2 +3n+1} \right)-n-1$

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

Nun so umformen, dass die Voraussetzung wieder zu erkennen ist:

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

$= \left( {n^3 -n} \right)+3\left( {n^2 +n} \right)$

Wir sehen nun: Nach Vorraussetzung ist $\left( {n^3 -n} \right)$ durch 6 teilbar.

$\left( {n^2 +n} \right)$ ist auf jeden Fall eine gerade Zahl, denn:

gerade² +gerade = gerade+gerade = gerade
ungerade² +ungerade = ungerade+ungerade = gerade

Damit ist $\left( {n^2 +n} \right)$ also auf jeden Fall gerade, also ein Vielfaches von 2. 3 mal 2 ist bekanntlich 6, also ist $3\left( {n^2 +n} \right)$ ein Vielfaches von 6. Fertig!

e )

Ansatz:

n = 0: 33

Für n+1 also:

$2^{4\left( {n+1} \right)+3} +5^{2+\left( {n+1} \right)}$

$= 2^{4n+4+3} +5^{2+n+1}$

In Richtung Induktionsvoraussetzung umformen, denn über die wissen wir ja schon, dass sie durch 11 teilbar ist:

$= 2^4 \cdot 2^{4n+3} +5^1 \cdot 5^{2+n}$

$= 16 \cdot 2^{4n+3} +5 \cdot 5^{2+n}$

Nun die 16 in (11+5) aufteilen, dann bekommen wir schon mal einen Term, der durch 11 teilbar ist. Zudem haben wir dann zweimal den Faktor 5, den wir anschließend ausklammern können:

$= \left( {11+5} \right) \cdot 2^{4n+3} +5 \cdot 5^{2+n}$