01 – Vollständige Induktion

 

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

  1. \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}

  2. \sum\limits_{k = 0}^n {k^3 = \frac{{n^2 \left( {n+1} \right)^2 }} {4}} für alle n \in \mathbb{N}

  3. \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\}

  4. Für alle n \in \mathbb{N} ist 6 ein Teiler von n^3 -n

  5. 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}

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

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

So, fertig! Die linke Hälfte ist natürlich durch 11 teilbar, da sie 11 als Faktor hat und die Klammer ist nach Voraussetzung auch durch 11 teilbar.

Ähnliche Artikel

1 Kommentar zu “01 – Vollständige Induktion”

Hab bei a) ein fehlendes ^2 bei

    \[\left( n+1 \right)^2\]

ergänzt.

Kommentar verfassen