Summe der ersten n positiven ganzen Zahlen

Beweise, dass $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ für jedes $n \ge 1$ gilt.

Induktionsanfang: prüfe $n = 1$: Linke Seite: $1$. Rechte Seite: $\dfrac{1 \cdot 2}{2} = 1$ = $P(1)$ ist wahr

Induktionsvoraussetzung: nimm $P(k)$ für ein $k \ge 1$ an: Angenommen, $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ = Diese Gleichung dürfen wir benutzen

Induktionsschritt: addiere den nächsten Summanden $k+1$ auf beiden Seiten: $1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ = $= \dfrac{(k+1)(k+2)}{2}$

Vergleiche mit $P(k+1)$: $P(k+1)$ besagt, dass die Summe gleich $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ ist = $P(k+1)$ ist wahr

Answer: Nach dem Prinzip der vollständigen Induktion gilt $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ für jedes $n \ge 1$. Zum Beispiel ist $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$.

Summe der ersten n ungeraden Zahlen

Beweise, dass $1 + 3 + 5 + \dots + (2n-1) = n^2$ für jedes $n \ge 1$ gilt.

Induktionsanfang: prüfe $n = 1$: Linke Seite: $1$. Rechte Seite: $1^2 = 1$ = $P(1)$ ist wahr

Induktionsvoraussetzung: Angenommen, $1 + 3 + \dots + (2k-1) = k^2$ für ein $k \ge 1$ = Diese Gleichung dürfen wir benutzen

Bestimme die nächste ungerade Zahl: Die ungerade Zahl nach $2k-1$ ist $2(k+1) - 1 = 2k + 1$ = Addiere $2k + 1$

Induktionsschritt: $1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1$ = $= (k+1)^2$, also ist $P(k+1)$ wahr

Answer: Nach dem Prinzip der vollständigen Induktion ist die Summe der ersten $n$ ungeraden Zahlen gleich $n^2$. Probe: $1 + 3 + 5 + 7 + 9 = 25 = 5^2$.

Summe von Zweierpotenzen

Beweise, dass $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ für jedes $n \ge 0$ gilt.

Induktionsanfang: hier ist der erste Wert $n = 0$: Linke Seite: $2^0 = 1$. Rechte Seite: $2^{1} - 1 = 1$ = $P(0)$ ist wahr

Induktionsvoraussetzung: Angenommen, $1 + 2 + \dots + 2^k = 2^{k+1} - 1$ für ein $k \ge 0$ = Diese Gleichung dürfen wir benutzen

Induktionsschritt: addiere den nächsten Summanden $2^{k+1}$: $1 + 2 + \dots + 2^k + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1}$ = $= 2 \cdot 2^{k+1} - 1$

Vereinfache und vergleiche mit $P(k+1)$: $2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1 = 2^{(k+1)+1} - 1$ = $P(k+1)$ ist wahr

Answer: Nach dem Prinzip der vollständigen Induktion gilt $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ für jedes $n \ge 0$. Probe für $n = 6$: $1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 = 2^7 - 1$.

Ein Teilbarkeitsbeweis

Beweise, dass $n^3 - n$ für jedes $n \ge 1$ durch $3$ teilbar ist. (In der Lektion Direkter Beweis wurde das durch Faktorisieren gezeigt; jetzt benutzen wir Induktion.)

Induktionsanfang: prüfe $n = 1$: $1^3 - 1 = 0 = 3 \cdot 0$ = $P(1)$ ist wahr

Induktionsvoraussetzung: Angenommen, $k^3 - k = 3m$ für eine ganze Zahl $m$ = $k^3 - k$ ist ein Vielfaches von $3$

Multipliziere den Ausdruck für $k+1$ aus: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$ = $= (k^3 - k) + 3k^2 + 3k$

Benutze die Induktionsvoraussetzung: $(k^3 - k) + 3k^2 + 3k = 3m + 3(k^2 + k)$ = $= 3(m + k^2 + k)$

Schließe ab: $m + k^2 + k$ ist eine ganze Zahl, also ist der Ausdruck ein Vielfaches von $3$ = $P(k+1)$ ist wahr

Answer: Nach dem Prinzip der vollständigen Induktion teilt $3$ die Zahl $n^3 - n$ für jedes $n \ge 1$. Probe für $n = 5$: $125 - 5 = 120 = 3 \cdot 40$.

Eine Ungleichung: 2 hoch n ist größer als n

Beweise, dass $2^n > n$ für jedes $n \ge 1$ gilt.

Induktionsanfang: prüfe $n = 1$: $2^1 = 2$ und $2 > 1$ = $P(1)$ ist wahr

Induktionsvoraussetzung: Angenommen, $2^k > k$ für ein $k \ge 1$ = Diese Ungleichung dürfen wir benutzen

Schreibe $2^{k+1}$ mithilfe von $2^k$: $2^{k+1} = 2 \cdot 2^k > 2 \cdot k$ = $2^{k+1} > 2k$

Vergleiche $2k$ mit $k+1$: $2k = k + k \ge k + 1$, weil $k \ge 1$ = $2k \ge k + 1$

Verkette die Ungleichungen: $2^{k+1} > 2k \ge k + 1$ = $2^{k+1} > k + 1$, also ist $P(k+1)$ wahr

Answer: Nach dem Prinzip der vollständigen Induktion gilt $2^n > n$ für jedes $n \ge 1$. Zum Beispiel ist $2^{10} = 1024 > 10$.

Mistake: Den Induktionsanfang weglassen

Why: Der Induktionsschritt allein beweist nichts: Er sagt nur, WENN ein Dominostein fällt, fällt auch der nächste. Beispiel: Die falsche Behauptung $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ hat einen funktionierenden Induktionsschritt, aber für $n = 1$ ist die linke Seite $1$ und die rechte Seite $2$.

Correct: Prüfe den ersten Fall immer ausdrücklich. Ohne einen ersten fallenden Stein fällt gar nichts.

Mistake: Annehmen, was man beweisen will

Why: Wer "angenommen, $P(n)$ ist für alle $n$ wahr" oder "angenommen, $P(k+1)$" schreibt, argumentiert im Kreis: Er setzt die Behauptung schon voraus.

Correct: Nimm $P(k)$ für EINEN Wert $k$ an (die Induktionsvoraussetzung) und beweise daraus $P(k+1)$.

Mistake: Falsche Algebra im Induktionsschritt

Why: Ein häufiger Fehler ist, den falschen nächsten Summanden zu addieren, zum Beispiel $2k - 1$ statt $2k + 1$ bei der Summe der ungeraden Zahlen, oder den neuen Summanden nur auf einer Seite zu addieren.

Correct: Schreibe zuerst $P(k+1)$ vollständig auf (ersetze jedes $n$ durch $k+1$) und arbeite dann genau auf diesen Ausdruck hin.

Mistake: Glauben, dass viele geprüfte Fälle ein Beweis sind

Why: Der Term $n^2 + n + 41$ liefert Primzahlen für $n = 0, 1, \dots, 39$, aber für $n = 40$ ergibt er $1681 = 41^2$, und das ist keine Primzahl.

Correct: Beispiele helfen, eine Formel zu vermuten. Nur Induktionsanfang plus Induktionsschritt beweisen sie für jedes $n$.

Computerprogramme überprüfen

Programmierer beweisen mit Induktion, dass eine Schleife nach beliebig vielen Durchläufen das richtige Ergebnis liefert: Stimmt es nach $k$ Durchläufen, dann stimmt es auch nach $k+1$ Durchläufen.

Eine Schleife addiert $1, 2, 3, \dots$ zu einer laufenden Summe. Die Induktion beweist, dass die Summe nach $n$ Durchläufen $\dfrac{n(n+1)}{2}$ ist.

Die Türme von Hanoi

Bei diesem Rätsel versetzt du einen Stapel Scheiben auf einen anderen Stab, immer nur eine Scheibe auf einmal und nie eine größere auf eine kleinere. Die Induktion beweist, dass $n$ Scheiben $2^n - 1$ Züge brauchen.

Um $k+1$ Scheiben zu versetzen, bewegst du die oberen $k$ Scheiben weg, dann die größte Scheibe und danach die $k$ Scheiben wieder obendrauf: $2(2^k - 1) + 1 = 2^{k+1} - 1$ Züge.

Reiskörner auf dem Schachbrett

Eine alte Legende: Lege $1$ Reiskorn auf das erste Feld, $2$ auf das zweite, $4$ auf das dritte und verdopple jedes Mal. Die Summe der Zweierpotenzen verrät dir die Gesamtzahl.

Auf den ersten $3$ Feldern liegen $1 + 2 + 4 = 7 = 2^3 - 1$ Körner.

Q: Warum beweist die Induktion die Aussage wirklich für ALLE n?

A: Der Induktionsanfang liefert $P(1)$. Der Schritt mit $k = 1$ liefert $P(2)$, mit $k = 2$ liefert er $P(3)$ und so weiter. Jede positive ganze Zahl wird nach endlich vielen Schritten erreicht, also wird kein $n$ ausgelassen.

Q: Muss der Induktionsanfang immer bei n = 1 liegen?

A: Nein. Beginne beim ersten Wert, ab dem die Aussage gelten soll. Die Summe der Zweierpotenzen beginnt bei $n = 0$. Die Aussage $2^n > n^2$ ist für $n = 2, 3, 4$ falsch (zum Beispiel $2^4 = 16 = 4^2$) und gilt für jedes $n \ge 5$, also benutzt dieser Beweis den Induktionsanfang $n = 5$.

Q: Ist die vollständige Induktion dasselbe wie induktives Schließen in den Naturwissenschaften?

A: Nein. Beim induktiven Schließen vermutet man aus Beispielen eine allgemeine Regel, und die kann falsch sein. Die vollständige Induktion ist ein deduktiver Beweis: Sind Induktionsanfang und Induktionsschritt bewiesen, steht das Ergebnis sicher fest.

Q: Was ist starke Induktion?

A: Bei der starken Induktion nimmt man an, dass $P(1), P(2), \dots, P(k)$ alle wahr sind, nicht nur $P(k)$. Das ist nützlich, wenn $P(k+1)$ von mehreren früheren Fällen abhängt, zum Beispiel bei Beweisen über Primfaktorzerlegungen.