Muss der Induktionsanfang immer bei n = 1 liegen?

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

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

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.

Was ist starke Induktion?

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.

Lehrermaterialien

Vollständige Induktion

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

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.

Lerne, Aussagen für jede positive ganze Zahl mit vollständiger Induktion zu beweisen: Induktionsanfang, Induktionsvoraussetzung, Induktionsschritt und Schlussfolgerung.

Fortgeschritten30 MinLektion

Arbeitsblatt zum Drucken

Definition

Die vollständige Induktion ist eine Beweismethode für Aussagen über jede positive ganze Zahl

n

(oder jede ganze Zahl ab einem Startwert). Wir nennen die Aussage

P(n)

. Statt unendlich viele Fälle einzeln zu prüfen, beweist du nur zwei Dinge:

1.Induktionsanfang: $P(1)$ ist wahr.
2.Induktionsschritt: Für jedes $k \ge 1$ gilt: Wenn $P(k)$ wahr ist, dann ist auch $P(k+1)$ wahr. Die Annahme " $P(k)$ ist wahr" heißt Induktionsvoraussetzung.

Zusammen ergeben sie die Schlussfolgerung:

P(n)

ist für jedes

n \ge 1

wahr.

P(1) \ \text{und} \ \big(P(k) \Rightarrow P(k+1)\big) \ \Longrightarrow \ P(n) \text{ für alle } n \ge 1

Stell dir eine unendlich lange Reihe von Dominosteinen vor. Der Induktionsanfang stößt den ersten Stein um. Der Induktionsschritt garantiert, dass jeder fallende Stein den nächsten umwirft. Also fallen alle Steine:

P(1)

, dann

P(2)

, dann

P(3)

und so weiter, ohne Ende.

Probier es gleich aus

Welche zwei Teile muss jeder Beweis durch vollständige Induktion enthalten?

Lösungsbeispiele

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

Antwort: 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$ .

Häufige Fehler

Den Induktionsanfang weglassen

Warum es falsch ist: 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$ .

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

Annehmen, was man beweisen will

Warum es falsch ist: 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.

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

Falsche Algebra im Induktionsschritt

Warum es falsch ist: 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.

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

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

Warum es falsch ist: 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.

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

Interaktive Visualisierung

Folgen-Explorer

Erstes Glied (a₁ = 1)

Konstante Differenz (d = 2)

11,

13,

, ...

Formel

a_n = 1 + 2(n - 1) = 2n - 1

Summenformel: S_8 = 8/2 × (2×1 + 7×2) = 64

Teilsummen

S₁ = 1S₂ = 4S₃ = 9S₄ = 16S₅ = 25S₆ = 36S₇ = 49S₈ = 64

a_1

a_5

a_10

a_20

Folgen-Explorer

Erstes Glied (a₁ = 1)

Quotient (r = 2)

16,

32,

64,

128

, ...

Formel

a_n = 1 × 2^(n-1)

Summenformel: S_8 = 1 × (1 - 2^8) / (1 - 2) = 255

Teilsummen

S₁ = 1S₂ = 3S₃ = 7S₄ = 15S₅ = 31S₆ = 63S₇ = 127S₈ = 255

|r| ≥ 1: Die Teilsummen nähern sich keinem festen Wert, die unendliche Reihe hat keine Summe.

a_1

a_5

a_10

512

a_20

524.288

Interaktiver Sandkasten

Ausdrucksrechner

Probiere diese:

Verlauf

Noch keine Berechnungen

Übungsaufgaben

18 Aufgaben

Aufgabe 1 von 18

Einfach

Welche zwei Teile muss jeder Beweis durch vollständige Induktion enthalten?

Warum es wichtig ist

Die Induktion ist das wichtigste Werkzeug, um Aussagen über unendlich viele Fälle zu beweisen:

Summenformeln: Du kannst beweisen, dass $1 + 2 + \dots + 100 = 5050$ aus einer allgemeinen Formel folgt und kein Zufall ist
Informatik: Programmierer beweisen, dass Schleifen und rekursive Funktionen für jede Eingabegröße das richtige Ergebnis liefern
Muster, die wahr aussehen: Ein Muster, das in 40 Fällen stimmt, kann im 41. Fall scheitern; die Induktion zeigt, wann ein Muster wirklich für immer gilt
Rätsel und Spiele: Die Türme von Hanoi, Parkettierungsprobleme und viele Wettbewerbsaufgaben werden mit Induktion gelöst
Höhere Mathematik: Fast jedes Gebiet der Mathematik benutzt irgendwo die Induktion

In den vorherigen Lektionen hast du direkte Beweise kennengelernt. Die Induktion fügt eine starke neue Idee hinzu: Beweise einen Schritt und lass ihn sich endlos wiederholen.

Anwendungen im echten Leben

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.

Beispiel:

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.

1Probiere es selbst

Ein Programm addiert in einer Schleife die Zahlen von $1$ bis $100$ .

Welche Summe gibt das Programm aus?

Schritt 1: Schreibe den mathematischen Ausdruck

Benutze $\dfrac{n(n+1)}{2}$ mit $n = 100$ :

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.

Beispiel:

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.

2Probiere es selbst

Ein Turm hat $6$ Scheiben. Für $5$ Scheiben braucht man $31$ Züge.

Wie viele Züge brauchen $6$ Scheiben?

Schritt 1: Schreibe den mathematischen Ausdruck

Benutze Züge für 6 Scheiben $= 2 \cdot$ (Züge für 5 Scheiben) $+ 1$ :

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.

Beispiel:

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

3Probiere es selbst

Du füllst die ersten $10$ Felder. Auf Feld $10$ liegen $2^9$ Körner.

Wie viele Körner liegen auf den ersten $10$ Feldern zusammen?

Schritt 1: Schreibe den mathematischen Ausdruck

Benutze $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ mit $n = 9$ :

Wichtige Erkenntnisse

1Die vollständige Induktion beweist eine Aussage $P(n)$ für jede ganze Zahl $n$ ab einem Startwert
2Induktionsanfang: Zeige, dass der erste Fall, meist $P(1)$ , wahr ist
3Induktionsvoraussetzung: Nimm an, dass $P(k)$ für ein beliebiges $k$ wahr ist
4Induktionsschritt: Beweise mithilfe der Voraussetzung, dass $P(k+1)$ gilt
5Schlussfolgerung: Wie bei einer Reihe von Dominosteinen gilt die Aussage für jedes $n$
6Beide Teile sind nötig: Ein Induktionsschritt ohne Induktionsanfang oder ein paar geprüfte Fälle ohne Schritt beweisen nichts

Häufig gestellte Fragen

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.

Glossar

Vollständige Induktion: Eine Beweismethode, die $P(n)$ für jede ganze Zahl $n$ ab einem Startwert beweist, mit Induktionsanfang und Induktionsschritt
Induktionsanfang: Der erste Fall der Aussage, meist $P(1)$ , der direkt geprüft wird
Induktionsvoraussetzung: Die Annahme, dass $P(k)$ für eine beliebige ganze Zahl $k$ wahr ist
Induktionsschritt: Der Beweis, dass aus $P(k)$ die Aussage $P(k+1)$ folgt, für jedes $k$ ab dem Startwert
P(n): Die Aussage, die wir beweisen wollen, geschrieben in Abhängigkeit von der ganzen Zahl $n$
Schlussfolgerung: Der letzte Satz eines Induktionsbeweises: $P(n)$ ist für jedes $n$ ab dem Startwert wahr

Formelkarte

Prinzip der vollständigen Induktion

P(1) \text{ und } \big(P(k) \Rightarrow P(k+1)\big) \Rightarrow P(n) \text{ für alle } n \ge 1

Induktionsanfang plus Induktionsschritt beweist die Aussage für jedes $n$

Summe der ersten n ganzen Zahlen

1 + 2 + \dots + n = \dfrac{n(n+1)}{2}

Für $n = 5$: $15$

Summe der ersten n ungeraden Zahlen

1 + 3 + \dots + (2n-1) = n^2

Für $n = 5$: $25$

Summe von Zweierpotenzen

1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1

Für $n = 6$: $127$

Mehr zu diesem Thema

Definition

Lösungsbeispiele

Häufige Fehler

Interaktive Visualisierung

Folgen-Explorer

Formel

Teilsummen

Folgen-Explorer

Formel

Teilsummen

Interaktiver Sandkasten

Ausdrucksrechner

Verlauf

Übungsaufgaben

Warum es wichtig ist

Anwendungen im echten Leben

Computerprogramme überprüfen

Die Türme von Hanoi

Reiskörner auf dem Schachbrett

Wichtige Erkenntnisse

Häufig gestellte Fragen

Glossar

Formelkarte

Prinzip der vollständigen Induktion

Summe der ersten n ganzen Zahlen

Summe der ersten n ungeraden Zahlen

Summe von Zweierpotenzen

Mehr zu diesem Thema

Einführung in mathematische Beweise

Direkter Beweis

Zwei-Spalten-Beweise

Beweise in Textform