Logik der vollständigen Induktion

04.11.2009, 00:12

_off

Logik der vollständigen Induktion

Hallo,

zunächst einmal ein freundliches Hallo in die Runde! Freude

Ich bin Studienanfänger (Wirtschaftswissenschaften) und stehe nach ein paar Mathematikvorlesungen nun auch schon vor meinem ersten ernsthaften Verständnisproblem. BWL hab ich nicht angefangen, weil ich mich vor Mathe drücken will, sondern mich durchaus mit der Materie beschäftigen möchte, aber dennoch bin ich kein Held in Mathematik und muss mich zuerst mal selbst in die richtige Spur bringen. Hoffentlich kann man mir hier jemand helfen.

Mein Logikverständnis setzt bei einem gewissen Punkt einer vollständigen Induktion leider aus. Der Übungsleiter in der dazugehörigen Matheveranstaltung hat diesen Schritt als "mathematische Intuition" bezeichnet - was mir allerdings nicht viel bringt, da ich mir diese wohl erst antrainieren muss. Bewiesen werden soll (1:1 aus dem "Lehrbuch für Ökonomen" von Opitz, 9. Auflage, S. 76, Annahme 5):

$\begin{eqnarray*} A(n): 2^n \geq n^2 \end{eqnarray*}$

Der Anstoßstein dieser Induktion ist mir noch verständlich:

$\begin{eqnarray*} A(1): 2^1 \geq 1^2 \end{eqnarray*}$

Und auch die Folgerung

$\begin{eqnarray*} A(n) \Rightarrow A(n+1) : 2^n \geq n^2 \Rightarrow 2^{n+1} \geq (n+1)^2 \end{eqnarray*}$

macht für mich Sinn, da die Annahme ja für jedes n+1 gelten muss, um sicher bewiesen zu werden. Nun habe ich zwar die Lösung vor mir, kann damit aber wenig anfangen. Ich verstehe einzelne Umformungen und Zusammenhänge nicht. Ich hoffe, mir kann jemand in dieser Verständnisfrage weiterhelfen, sodass ich das auch auf andere vollständige Induktionen anwenden kann, die ebenfalls in diesem Stil ablaufen.

Lösung: (Der erste Schritt an dieser Stelle ist ja nur eine banale Umformung nach den Potenzregeln, aber Schritt zwei leuchtet mir leider schlichtweg nicht ein.)

$\begin{eqnarray*} 2^{n+1} = 2*2^n \geq 2n^2 \geq n^2+2n+1 = (n+1)^2 \end{eqnarray*}$

Wegen $\begin{eqnarray*} 2n^2 \geq n^2 + 2n+1 \Leftrightarrow n^2 \geq 2n+1 \Leftrightarrow n \geq 3 \end{eqnarray*}$ ist der Induktionsschlus nur für n = 3,4, ... möglich

Liebe Grüße und vielen Dank,
off

04.11.2009, 05:29

Mazze

Auf diesen Beitrag antworten »

Zitat:

Der Anstoßstein dieser Induktion ist mir noch verständlich: $\begin{eqnarray*} A(1): 2^1 \geq 1^2 \end{eqnarray*}$

$\begin{eqnarray*} 2 \geq 1 \end{eqnarray*}$ ? Eins zum Quadrat ist immernoch 1. Die Aussage $\begin{eqnarray*} 2^n \geq n^2 \end{eqnarray*}$ ist erst ab n = 2 gültig. D.h die Induktion beginnt man hier für n = 2.

Zitat:

Lösung: (Der erste Schritt an dieser Stelle ist ja nur eine banale Umformung nach den Potenzregeln, aber Schritt zwei leuchtet mir leider schlichtweg nicht ein.)

Bei der Induktion zeigt man zunächst das eine Aussage für eine bestimmte natürliche Zahl gilt. Dieses nennt man Induktionsanfang oder Induktionsverankerung. Danach zeigt man die Aussage allgemein auch für den Nachfolger. Dazu muss man immer die Induktionsvoraussetzung benutzen. Es passiert folgendes :

$\begin{eqnarray*} 2^{n+1} = 2*2^n \end{eqnarray*}$ und bei $\begin{eqnarray*} 2^n \end{eqnarray*}$ können wir die Induktionsvoraussetzung benutzen. Wir wissen nämlich das es ein n gibt mit $\begin{eqnarray*} 2^n \geq n^2 \end{eqnarray*}$ , das benutzen wir einfach, also erhalten wir $\begin{eqnarray*} 2*2^n \geq 2*n^2 \end{eqnarray*}$ . Der Dritte Schritt ergibt sich aus

Zitat:

$\begin{eqnarray*} 2n^2 \geq n^2 + 2n+1 \Leftrightarrow n^2 \geq 2n+1 \Leftrightarrow n \geq 3 \end{eqnarray*}$

Denn für n > 3 ist $\begin{eqnarray*} n^2 \geq 2n + 1 \end{eqnarray*}$ , damit ergibt sich

$\begin{eqnarray*} 2n^2 = n^2 + n^2 \geq n^2 + 2n + 1 \end{eqnarray*}$

was ja dann ein vollständiges Quadrat ist.

04.11.2009, 06:35

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von Mazze
$\begin{eqnarray*} 2 \geq 1 \end{eqnarray*}$ ? Eins zum Quadrat ist immernoch 1. Die Aussage $\begin{eqnarray*} 2^n \geq n^2 \end{eqnarray*}$ ist erst ab n = 2 gültig. D.h die Induktion beginnt man hier für n = 2.

Ja $\begin{eqnarray*} 2\geq 1 \end{eqnarray*}$ ! Außerdem:
"Drei mal drei ist neune widiwidiwitt[...]" oder so ähnlich. Ach und 2^3 ist übrigens 8 Big Laugh

04.11.2009, 07:33

Mazze

Auf diesen Beitrag antworten »

Da bin ich heut entschieden zu früh aufgestanden. 2 Antworten, 2 Fehler Augenzwinkern

04.11.2009, 11:13

_off

Auf diesen Beitrag antworten »

Guten Morgen,

zunächst Danke für die erste Hilfe! Ich darf also 2^n durch n^2 ersetzen, weil es sicher mindestens eine Lösung gibt, die hier zutrifft?

Und weil $\begin{eqnarray*} (n+1)^2 = n² +2n+1 \end{eqnarray*}$ , ist auch $\begin{eqnarray*} 2n^2 \geq n^2+2n+1 \end{eqnarray*}$ . Soweit bin ich schon mal.

Aber wieso kann ich dann nachfolgend schließen, dass

$\begin{eqnarray*} 2n^2 \geq n^2+2n+1 \Leftrightarrow n^2 \geq 2n+1 \Leftrightarrow n\geq3 \end{eqnarray*}$ ?

Die letzten zwei Schritten bleiben mir vollkommen unverständlich. Und wie ich dann abschließend daraus auf die Lösung kommen soll, dass A(n) für alle natürlichen Zahlen für $\begin{eqnarray*} n\geq4 \end{eqnarray*}$ und außerdem für n=1,2 gilt, verstehe ich ebenfalls nicht. Es macht für mich rein logisch Sinn, ja, aber aus dieser Induktion heraus kann ich das nicht herauslesen. verwirrt

Habt Geduld mit mir! traurig

04.11.2009, 11:27

Mazze

Auf diesen Beitrag antworten »

Zitat:

Ich darf also 2^n durch n^2 ersetzen, weil es sicher mindestens eine Lösung gibt, die hier zutrifft?

Das darfst Du hier aber nur machen, weil Du vollständige Induktion benutzt.

Zitat:

Die letzten zwei Schritten bleiben mir vollkommen unverständlich.

Das ist eine Äquivalenzumformung von zwei Ungleichungen. In Worten heisst es:

$\begin{eqnarray*} 2n^2 \geq n^2 + 2n +1 \end{eqnarray*}$

genau dann wenn

$\begin{eqnarray*} n^2 \geq 2n + 1 \end{eqnarray*}$ (Schritt 1)

genau dann wenn

$\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ (Schritt 2)

Du kennst sowas ja schon von Gleichungen, man kanns genauso für Ungleichungen machen. Nur wenn man mit negativen multipliziert oder Kehrwerte bildet ändert sich etwas mehr bei Ungleichungen als bei Gleichungen.

Bei Schritt 1 wurde zum Beispiel von beiden Seiten der Ungleichung n² abgezogen.

Der Induktionsbeweis ist ja

$\begin{eqnarray*} 2^{n+1} = 2*2^n \underbrace{ \geq }_{*} 2n^2 \underbrace{\geq}_{**} n^2+2n+1 = (n+1)^2 \end{eqnarray*}$

An der Stelle * wird die Induktionsvoraussetzung benutzt. An der Stelle ** wird die Äquivalenz die wir durchgekaut haben benutzt. Am ende kommt $\begin{eqnarray*} 2^{n+1} \geq (n+1)^2 \end{eqnarray*}$ raus, was zu zeigen war.

04.11.2009, 12:18

_off

Auf diesen Beitrag antworten »

Ah, ich glaub, ich bin langsam auf dem richtigen Dampfer. Hab es größtenteils verstanden und werde mir das am Nachmittag noch verinnerlichen.

Nur noch eine kurze Frage: Die Annahme im 3. Schritt der Umformung $\begin{eqnarray*} n\geq3 \end{eqnarray*}$ setzt sich aus meinen Vorkenntnissen zusammen, die ich beim Induktionsbeginn aufgestellt habe, richtig? Hab noch nicht ganz begriffen, welcher Gedankengang genau an dieser Stelle dahinter steht - für den Rest bin ich dir sehr dankbar. Freude

Neue Frage »

Antworten »

Logik der vollständigen Induktion

Verwandte Themen