Wie formuliert man die Induktionsvorraussetzung (vollständige Induktion)?

Question

Aufgabe:

Text erkannt:

Der Induktionsschritt ist schon etwas schwieriger: Wir setzen die Gültigkeit von \( A(n) \), also von \( n \leq n^{2} \) für ein nicht näher konkretisiertes \( n \) voraus - das nennen wir Induktionsvoraussetzung, in der folgenden Rechnung mit „IV" abgekürzt und müssen daraus die Gültigkeit von \( A(n+1) \), also von \( n+1 \leq(n+1)^{2} \) folgern:
\( \begin{aligned} (n+1)^{2} &=n^{2}+2 n+1 \text { binomischen Formel } \\ & \text { IV } \\ & \geq n+2 n+1 \\ &=(n+1)+2 n \\ & \geq n+1 \end{aligned} \)

Problem/Ansatz:

Blicke momentan nicht durch wie man die Infuktionsvoraussetzung formuliert.

Man muss also beweisen, dass (n+1)^2 größer gleich (n+1) ist.

Zuerst wird mithilfe der binomischen Formel die Klammer aufgelöst. Ab da verstehe ich die weiteren Schritte nicht...

Warum verschwindet ^2 und das kleiner Zeichen wird umgedreht??

Answer 1

Aloha :)

Wir wollen die Gültigkeit einer Aussage \(A(n)\) für alle \(n\in\mathbb N\) beweisen. Hier ist:$$A(n)\colon\;n\le n^2$$

Das machen wir mit vollständiger Induktion.

1) Induktionsveankerung bei \(n=1\):$$A(1)\colon\; 1\le1^2\quad\checkmark$$Für \(n=1\) haben wir die Aussage damit bewiesen.

2) Induktionsschritt von \(A(n)\) nach \(A(n+1)\):

Wir gehen davon aus, dass die Aussage bereits für ein bestimmtes \(n\) bewiesen wurde und folgern daraus, dass die Behauptung auch für das folgende \(n\) gilt. Wir gehen also davon aus, dass \(n\le n^2\) gilt und rechnen:$$n\le n^2\implies n+1\le n^2+1\stackrel{(0<\pink{2n})}{<}n^2+\pink{2n}+1=(n+1)^2\quad\checkmark$$Wenn die Behauptung für \(n\) gilt, gilt sie also auch für \((n+1)\).

Wiederholt man Schitt 2 immer wieder, gilt \(A(n)\) für alle \(n\in\mathbb N\).

Euer Leerer hat die Rechnung leider etwas ungeschickt formuliert. Auch er hat die Induktionsvoraussetzung \(\red{n\le n^2}\) verwendet, aber in der Form \(\green{n^2\ge n}\). Dann ist er nicht von der Induktionsvoraussetzung ausgegangen, sondern hat "von hinten" aus gerechnet und die Induktionsvoraussetzung in der Rechnung "versteckt"$$(n+1)^2=\green{n^2}+2n+1\green{\ge n}+2n+1>\green n+\cancel{2n}+1=\green n+1$$

Comments

Vielen Dank:))bin nur noch etwas verwirrt woher die 2n kommt

---

Text erkannt:

\( n+1 \leq(n+1)^{2} \)
\( n+1 \leq n^{2}+2 n+1 \)

Nach dem schritt bin ich total lost :/

---

Nach der Induktionsvoraussetzung gilt ja:$$n\le n^2$$

Jetzt addierst du auf beiden Seiten eine \(1\) und erhältst:$$n+1\le n^2+1$$

Jetzt addierst du auf der rechten Seite \(2n\) dazu, wodurch die rechte Seite noch größer wird. Das Kleiner-Zeichen gilt also dann erst recht:$$n+1<n^2+2n+1$$

Der Sinn dieser \(2n\)-Addition ist, dass wir nun auf der rechten Seite die 1-te binomische Formel \((a+b)^2=a^2+2ab+b^2\) anwenden können:$$n+1<(n+1)^2$$Damit haben wir gezeigt, dass aus \(n<n^2\) auch \((n+1)<(n+1)^2\) folgt.

Dein Leerer hat vom Ende her gerechnet und mit der binomischen Formel angefangen:$$(n+1)^2=n^2+2n+1$$Dann hat er auf der rechten Seite \(2n\) weggelassen, wodurch die rechte Seite verkleinert wird:$$(n+1)^2\ge n^2+1$$Nun hat er die Induktionsvoraussetzung \(n^2\ge n\) verwendet und die rechte Seite nochmal verkleinert, indem er \(n^2\) durch \(n\) ersetzt hat:$$(n+1)^2\ge n+1$$

Answer 2

Das \( n^2 \) verschindet nicht sondern wird mit der IV durch \( n \) ageschätzt, da ja \( n^2 \ge n \) gilt.