Leitfaden für Lehrer: Vollständige Induktion

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

Lektion präsentierenSchülerseite anzeigen

Diese Lektion im Unterricht nutzen

Kostenlos, keine Schülerkonten nötig.

Mit Schülern teilen

Die Schüler öffnen die Lektion und üben mit sofortigem Feedback.

Arbeitsblatt zum Drucken

Alle Übungsaufgaben auf Papier, mit separatem Lösungsblatt.

Arbeitsblatt Lösungen

Klassenquiz

10 Fragen zu Mathematische Beweise. Die Schüler machen mit einem Namen mit, du siehst alle Ergebnisse.

Für Lehrer

Lernziele

Das Dominoprinzip hinter der vollständigen Induktion erklären
Induktionsanfang, Induktionsvoraussetzung, Induktionsschritt und Schlussfolgerung eines Induktionsbeweises aufschreiben
Summenformeln, Teilbarkeitsaussagen und Ungleichungen mit Induktion beweisen
Fehler in fehlerhaften Induktionsbeweisen finden und korrigieren

Voraussetzungen

• Einführung in mathematische Beweise: was ein Beweis ist
• Direkter Beweis: Aussagen aus Definitionen beweisen
• Ausmultiplizieren und Faktorisieren von Termen wie $(k+1)^2$ und $(k+1)^3$
• Rechnen mit Potenzen, zum Beispiel $2 \cdot 2^k = 2^{k+1}$

Diskussionsstarter

1. Wenn du weißt, dass der erste Dominostein fällt und jeder Stein den nächsten umwirft, woher weißt du, dass der 1000. Stein fällt?
2. Warum reicht es nicht, eine Formel für die ersten 40 Werte von n zu prüfen?
3. Was würde schiefgehen, wenn wir den Induktionsanfang weglassen?
4. Fällt dir eine Situation im Alltag ein, in der ein Schritt immer zum nächsten führt?

Häufige Missverständnisse

$P(k)$ anzunehmen heißt, das anzunehmen, was man beweisen will

Abhilfe: Betone, dass wir $P(k)$ nur für EINEN Wert annehmen, um die Verbindung von $k$ zu $k+1$ zu zeigen. Der Induktionsanfang startet die Kette. Benutze die Dominosteine: Wir nehmen nur an, dass ein Stein fällt, um zu prüfen, ob er den nächsten trifft.

Der Induktionsanfang ist eine Formalität, die man weglassen kann

Abhilfe: Zeige die falsche Behauptung $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ . Ihr Induktionsschritt funktioniert perfekt, aber der Induktionsanfang scheitert, also ist die Behauptung für jedes $n$ falsch.

Mehrere geprüfte Werte beweisen eine Formel

Abhilfe: Benutze $n^2 + n + 41$ , das für $n = 0$ bis $39$ eine Primzahl ist, aber für $n = 40$ gleich $41^2$ ist. Muster legen eine Formel nahe, nur ein Beweis bestätigt sie.

Differenzierungsideen

Für Schüler mit Schwierigkeiten:

• Gib eine Vorlage mit vier beschrifteten Kästen: Induktionsanfang, Voraussetzung, Schritt, Schlussfolgerung
• Prüfe vor der Algebra $P(k)$ und $P(k+1)$ mit Zahlen, zum Beispiel $k = 4$
• Beginne nur mit Summenformeln, bei denen der nächste Summand leicht zu erkennen ist

Für Schüler auf Niveau:

• Die Summe der ungeraden Zahlen und die Summe der Zweierpotenzen ohne Vorlage beweisen
• Den Fehler in drei fehlerhaften Induktionsbeweisen finden
• Beweisen, dass $n^3 - n$ durch $3$ teilbar ist

Für fortgeschrittene Schüler:

• $2^n > n^2$ für $n \ge 5$ beweisen und erklären, warum der Induktionsanfang bei $5$ liegt
• $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ beweisen
• Die starke Induktion kennenlernen und beweisen, dass jede ganze Zahl $n \ge 2$ ein Produkt von Primzahlen ist

Standardausrichtung

MP3 (CCSS.MATH.PRACTICE.MP3)
Konstruiere tragfähige Argumente und kritisiere die Argumentation anderer
HSA-APR.C.4 (CCSS.MATH.CONTENT.HSA.APR.C.4)
Beweise Polynomidentitäten und verwende sie, um numerische Beziehungen zu beschreiben
HSA-SSE.B.4 (CCSS.MATH.CONTENT.HSA.SSE.B.4)
Leite die Formel für die Summe einer endlichen geometrischen Reihe her und verwende sie, um Probleme zu lösen

Lektionsressourcen

visualFolgen-Visualisierung
Setze das erste Glied auf 1 und die Differenz auf 2: Die Summenzeile zeigt, dass die ersten 8 ungeraden Zahlen zusammen 64 ergeben, also 8 zum Quadrat
activityDomino-Vorführung
Die Schülerinnen und Schüler stellen eine Reihe Dominosteine auf und testen, was ohne ersten Anstoß oder mit einer Lücke in der Reihe passiert
worksheetInduktionsbeweise ergänzen
Fünf Induktionsbeweise mit fehlenden Induktionsanfängen, Voraussetzungen und Rechenschritten zum Vervollständigen

Lektionsinhalt

Alles, was die Schüler sehen: Definition, Beispiele, typische Fehler, Anwendungen. Zum Öffnen tippen.

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.

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

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

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.

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.

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

Leitfaden für Lehrer: Vollständige Induktion

Diese Lektion im Unterricht nutzen

Für Lehrer

Für Schüler mit Schwierigkeiten:

Für Schüler auf Niveau:

Für fortgeschrittene Schüler:

Lektionsinhalt

Definition

Lösungsbeispiele

Häufige Fehler

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