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

  1. für die kleinstmögliche Zahl zu beweisen,
  2. 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!

  1. Du stößt den ersten Dominostein um!

  2. 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\NnNn\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 mnmn\geq m gültig. Auch das kann mittles vollständiger Induktion bewiesen werden.

Der Induktionsbeweis gliedert sich immer in drei Schritte:

  1. Induktionsanfang \text{(IA)}(IA)\text{(IA)}

  2. Induktionsvoraussetzung \text{(IV)}(IV)\text{(IV)}

  3. Induktionsschritt \text{(IS)}(IS)\text{(IS)}

1. Induktionsanfang

Beim Induktionsanfang überprüfst du immer, ob die Aussage für die kleinstmögliche Zahl n_0n0n_0 gilt. Dies ist üblicherweise n_0 = 0n0=0n_0 = 0 oder n_0 =1n0=1n_0 =1. Es kann aber auch sein, dass eine Aussage nur für alle n \geq mnmn \geq m gilt. Dann musst du mit n_0 = mn0=mn_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 nnn gilt!

Das war's!

Du schreibst also fast den Satz nochmal ab.

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

3. Induktionsschritt

Der Induktionsschritt ist erfahrungsgemäß der schwierigste Schritt.

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

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


Beispiele

Summenbeweis

Beweise die folgende Aussage mit vollständiger Induktion!

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

\boxed{1+2+4+\ldots +2^{n-1} + 2^n = 2^{n+1}-1}1+2+4++2n1+2n=2n+11\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}n0=1\col[1]{n_0=1}. (Manchmal ist bei \NN\N auch die 000 mit drin, dann musst du damit anfangen!)

1 + \ldots + 2^\col[1]{1} = 1+2=31 + \ldots + 2^\col[1]{1} = 1+2=32^{\col[1]{1}+1}-1 = 2^2-1 = 4-1=3 ~\checkmark21+11=221=41=32^{\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\NnNn \in\N mit der Eigenschaft:

\col[3]{1+2+\ldots+2^{n-1} + 2^n = 2^{n+1}-1}1+2++2n1+2n=2n+11\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}nn+1n\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}-11+2++2n+2n+1=2n+1+111+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)}}(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}1+2+2n(IV)+2n+1=2n+11+2n+1=22n+11=2n+1+11\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 nnn ist n^2 +nn2+nn^2 +n durch 222 teilbar.

In mathematischer Notation sagt man "222 teilt n^2+nn2+nn^2+n":

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

Beweis:

Induktionsanfang

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

1^2+1 = 2 ~\checkmark12+1=21^2+1 = 2 ~\checkmark

Offensichtlich ist 222 durch 222 teilbar.

Induktionsvoraussetzung

Es existiert ein n \in\NnNn \in\N mit der Eigenschaft, dass n^2+nn2+nn^2+n durch 222 teilbar ist.

Also:

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

Induktionsschritt

Führe den Induktionsschritt n\to \col[2]{n+1}nn+1n\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}(n+1)2+(n+1)=n2+2n+1+n+1=n2+n(IV)+2n+2=n2+n2+2(n+1)2\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+nn2+nn^2+n durch 222 teilbar und 2(n+1)2(n+1)2(n+1) ist ebenfalls durch 222 teilbar.

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

No items found.

Jetzt unlimited holen!

Mit simpleclub unlimited bekommst du Vollzugang zur App: Du boostest deine Noten, hast mehr Freizeit und gehst sicher in jede Klausur!

Jetzt unlimited holen

Jetzt simpleclub Azubi holen!

Mit simpleclub Azubi bekommst du Vollzugang zur App: Wir bereiten dich in deiner Ausbildung optimal auf deine Prüfungen in der Berufsschule vor. Von Ausbilder*innen empfohlen.

Jetzt simpleclub Azubi holen