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.

This Post Has One Comment

  1. Hab bei a) ein fehlendes ^2 bei

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

    ergänzt.

Leave a Reply

Close Menu