Top-Themen

Thank you! Your submission has been received!

Oops! Something went wrong while submitting the form.

Induktionsbeweis

Bei einem Induktionsbeweis benutzt du das Prinzip der vollständigen Induktion, um eine Aussage über alle natürlichen Zahlen zu beweisen. Der Beweis geschieht immer in den drei Schritten Induktionsanfang, Induktionsvoraussetzung, Induktionsschritt.

Beweisidee

Die Idee des Induktionsbeweises ist es, eine Aussage

für die kleinstmögliche Zahl zu beweisen,
für jede Zahl, auch für ihren Nachfolger zu beweisen.

Das ist das Prinzip der vollständigen Induktion!!

Das kannst du dir am besten an dem Dominoeffekt vorstellen!

Du stößt den ersten Dominostein um!
Für jeden Dominostein, der umfällt, fällt auch der Folgestein um.

Beweisaufbau

Ein Induktionsbeweis (auch Beweis durch vollständige Induktion) wird häufig verwendet, wenn eine Aussage über natürliche Zahlen getroffen wird.

Du erkennst solche Sätze meist an der Formulierung: "für alle n\in\N $n\in\N$ bzw. für alle natürlichen Zahlen gilt".

Manchmal ist eine Aussage aber auch nur für alle natürlichen Zahlen n\geq m $n\geq m$ gültig. Auch das kann mittles vollständiger Induktion bewiesen werden.

Der Induktionsbeweis gliedert sich immer in drei Schritte:

Induktionsanfang \text{(IA)} $\text{(IA)}$
Induktionsvoraussetzung \text{(IV)} $\text{(IV)}$
Induktionsschritt \text{(IS)} $\text{(IS)}$

1. Induktionsanfang

Beim Induktionsanfang überprüfst du immer, ob die Aussage für die kleinstmögliche Zahl n_0 $n_0$ gilt. Dies ist üblicherweise n_0 = 0 $n_0 = 0$ oder n_0 =1 $n_0 =1$ . Es kann aber auch sein, dass eine Aussage nur für alle n \geq m $n \geq m$ gilt. Dann musst du mit n_0 = m $n_0 = m$ anfangen.

2. Induktionsvoraussetzung

Die Induktionsvoraussetzung (auch Induktionsbehauptung, Induktionsbedingung oder Induktionshypothese) ist ein einfacher, aber wichtiger Schritt.

Nach dem Induktionsanfang nimmst du an, dass die Behauptung für ein n $n$ gilt!

Das war's!

Du schreibst also fast den Satz nochmal ab.

Beachte, dass du "es existiert ein n $n$ " schreiben musst und nicht: "für alle n $n$ gilt:"

3. Induktionsschritt

Der Induktionsschritt ist erfahrungsgemäß der schwierigste Schritt.

Du musst zeigen, dass die Aussage gilt, wenn du statt n $n$ jetzt n+1 $n+1$ einsetzt.

Im Laufe dieses Schrittes musst du die Induktionsvoraussetzung aus Schritt 2 benutzen!

Beispiele

Noch nicht genug?

In der App warten noch mehr Inhalte zu diesem Thema auf dich!

Auf dich warten weitere Inhalte zu diesem Thema.

Summenbeweis

Beweise die folgende Aussage mit vollständiger Induktion!

Für alle n\in\N $n\in\N$ gilt:

\boxed{1+2+4+\ldots +2^{n-1} + 2^n = 2^{n+1}-1}

\boxed{1+2+4+\ldots +2^{n-1} + 2^n = 2^{n+1}-1}

Beweis:

Induktionsanfang

Beim Induktionsanfang musst du die Aussage für die kleinstmögliche Zahl prüfen.

In diesem Fall ist das \col[1]{n_0=1} $\col[1]{n_0=1}$ . (Manchmal ist bei \N $\N$ auch die 0 $0$ mit drin, dann musst du damit anfangen!)

1 + \ldots + 2^\col[1]{1} = 1+2=3

1 + \ldots + 2^\col[1]{1} = 1+2=3

2^{\col[1]{1}+1}-1 = 2^2-1 = 4-1=3 ~\checkmark

2^{\col[1]{1}+1}-1 = 2^2-1 = 4-1=3 ~\checkmark

Auf beiden Seiten kommt das gleiche raus. Damit ist der Induktionsanfang geschafft!

Induktionsvoraussetzung

Jetzt musst du die Induktionsvoraussetzung formulieren:

Es existiert ein n \in\N $n \in\N$ mit der Eigenschaft:

\col[3]{1+2+\ldots+2^{n-1} + 2^n = 2^{n+1}-1}

\col[3]{1+2+\ldots+2^{n-1} + 2^n = 2^{n+1}-1}

Induktionsschritt

Jetzt machst du den Induktionsschritt n\to \col[2]{n+1} $n\to \col[2]{n+1}$ .

D.h. du musst zeigen, dass folgendes gilt:

1+2+\ldots+2^{n} + 2^{\col[2]{n+1}} = 2^{\col[2]{n+1}+1}-1

1+2+\ldots+2^{n} + 2^{\col[2]{n+1}} = 2^{\col[2]{n+1}+1}-1

Beginne zum Beispiel mit der linken Seite und benutze dann die Induktionsvoraussetzung \col[3]{\text{(IV)}} $\col[3]{\text{(IV)}}$ :

\begin{aligned} \col[3]{\underbrace{1+2+\ldots 2^n}_{\text{(IV)}}} + 2^{n+1} &= \col[3]{2^{n+1}-1} + 2^{n+1} \\ &= 2\cdot 2^{n+1} -1 \\[3mm] &= 2^{n+1+1}-1 ~\checkmark\\ \end{aligned}

\begin{aligned} \col[3]{\underbrace{1+2+\ldots 2^n}_{\text{(IV)}}} + 2^{n+1} &= \col[3]{2^{n+1}-1} + 2^{n+1} \\ &= 2\cdot 2^{n+1} -1 \\[3mm] &= 2^{n+1+1}-1 ~\checkmark\\ \end{aligned}

Teilbarkeitsbeweis

Beweise die folgende Aussage mit vollständiger Induktion!

Für alle natürlichen Zahlen n $n$ ist n^2 +n $n^2 +n$ durch 2 $2$ teilbar.

In mathematischer Notation sagt man "2 $2$ teilt n^2+n $n^2+n$ ":

\boxed{2~|~n^2+n}

\boxed{2~|~n^2+n}

Beweis:

Induktionsanfang

Überprüfe für \col[1]{n_0 =1} $\col[1]{n_0 =1}$ die Behauptung:

1^2+1 = 2 ~\checkmark

1^2+1 = 2 ~\checkmark

Offensichtlich ist 2 $2$ durch 2 $2$ teilbar.

Induktionsvoraussetzung

Es existiert ein n \in\N $n \in\N$ mit der Eigenschaft, dass n^2+n $n^2+n$ durch 2 $2$ teilbar ist.

Also:

\col[3]{2~|~n^2+n}

\col[3]{2~|~n^2+n}

Induktionsschritt

Führe den Induktionsschritt n\to \col[2]{n+1} $n\to \col[2]{n+1}$ durch.

\begin{aligned} (\col[2]{n+1})^2 + (\col[2]{n+1}) &= n^2+2n+1+n+1 \\[3mm] &= \col[3]{\underbrace{n^2+n}_{\text{(IV)}}} + 2n+2\\[3mm] &= \col[3]{\underbrace{n^2+n}_{2~|~}} + \underbrace{2(n+1)}_{2~|~}\\ \end{aligned}

\begin{aligned} (\col[2]{n+1})^2 + (\col[2]{n+1}) &= n^2+2n+1+n+1 \\[3mm] &= \col[3]{\underbrace{n^2+n}_{\text{(IV)}}} + 2n+2\\[3mm] &= \col[3]{\underbrace{n^2+n}_{2~|~}} + \underbrace{2(n+1)}_{2~|~}\\ \end{aligned}

Nach Induktionsvoraussetzung ist n^2+n $n^2+n$ durch 2 $2$ teilbar und 2(n+1) $2(n+1)$ ist ebenfalls durch 2 $2$ teilbar.

Also ist der gesamte Ausdruck durch 2 $2$ teilbar. Der Beweis ist abgeschlossen!

No items found.

simpleclub ist am besten in der App.

Mit unserer App hast du immer und überall Zugriff auf: Lernvideos, Erklärungen mit interaktiven Animationen, Übungsaufgaben, Karteikarten, individuelle Lernpläne uvm.

Web-Version

Top-Themen

Get the best learning hacks!

Induktionsbeweis

Beweisidee