Vollständige Induktion: n² <= 2^n

26.09.2015, 16:17

Kaffeevernichter

Abgespalten von Umschreiben einer Summe. (Guppi12)

------------------------------------------------------------------------------------------------

Hallo Guppi12,

also wieso man

Zitat:

Original von Kaffeevernichter Ich ziehe die Aussage für $\begin{eqnarray*} n \end{eqnarray*}$ heran und füge das $\begin{eqnarray*} n+1 \end{eqnarray*}$ Glied hinzu.

nicht so stehen lassen kann habe ich vertsanden.

Nun hat klarsoweit bei der Lösung meines ersten Problems ein neues aufgeworfen: $\begin{eqnarray*} 2^n\geq n^2 \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ . Hammer

Deine Kritik an meine Lösung, dass wenn ich weiß, dass der Logarithmus langsamer wächst als $\begin{eqnarray*} n \end{eqnarray*}$ , dass ich auch weiß, dass die Ungleichung die wir zeigen wollen gültig ist, finde ich einleuchtend.

Deshalb noch ein Versuch (ich versuche einen Schritt zurück zu treten und die Aufgabe elementarer lösen):
Induktionsanfang: für $\begin{eqnarray*} n=4 \end{eqnarray*}$ gilt $\begin{eqnarray*} 16=16 \end{eqnarray*}$ , ist also erfüllt.
Induktionsschluss: (aktuell mein Knackpunkt bei dem Beispiel)
$\begin{eqnarray*} 2^{n+1}\geq \left(n+1\right)^2=n^2+2n+1 \end{eqnarray*}$
Ich habe also $\begin{eqnarray*} n \end{eqnarray*}$ durch $\begin{eqnarray*} n+1 \end{eqnarray*}$ ersetzt. Passt das so?

Ich könnte ja auch in $\begin{eqnarray*} 2^n\geq n^2 \end{eqnarray*}$ beide Seiten mit zwei multiplizieren um auf $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$ zu kommen.

Irgendwie ist diese vollständige Induktion nicht ganz kompatibel mit meinem Hirnkastel verwirrt

Ich kann es nur immer wieder sagen: Danke an alle die sich die Zeit nehmen mir hier zu helfen! Gott

26.09.2015, 18:21

Guppi12

Auf diesen Beitrag antworten »

Ich würde an deiner Stelle wenn es geht, eher den Weg gehen, die Induktionsvoraussetzung vorauszusetzen und dann damit die Behauptung zu folgern, anstatt umgekehrt die Behauptung hinzuschreiben und dann durch Äquivalenzumformungen zur Voraussetzung zu gelangen.

Erstens ist so ein Beweis meist viel besser zu lesen und besser strukturiert und zweitens ist es leichter, Fehler zu vermeiden. Man ist bei der anderen Richtung leicht dazu verleitet, bei einigen Schritten nur $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ zu zeigen, obwohl man ja eigentlich genau die umgekehrte Richtung, nämlich $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ braucht. Am Ende steht ja ganz rechts die Voraussetzung und ganz links die Behauptung bei dieser Methode.

Deinen zweiten Ansatz, mit $\begin{eqnarray*} 2^n\geq n^2 \end{eqnarray*}$ zu beginnen, finde ich also besser.
Wenn du das mit $\begin{eqnarray*} 2 \end{eqnarray*}$ multiplizierst, hast du ja $\begin{eqnarray*} 2^{n+1}\geq 2n^2 \end{eqnarray*}$ . Jetzt kannst du $\begin{eqnarray*} 2n^2 \end{eqnarray*}$ noch weiter nach unten abschätzen, bis du dann letztendlich $\begin{eqnarray*} n^2+2n+1 \end{eqnarray*}$ erhälst. Ein Tipp dazu: Spalte auf in $\begin{eqnarray*} n^2+n^2 \end{eqnarray*}$ , das eine $\begin{eqnarray*} n^2 \end{eqnarray*}$ lässt du stehen, das soll ja auch am Ende noch da sein, in dem anderen $\begin{eqnarray*} n^2 \end{eqnarray*}$ verwendest du jetzt für eine Abschätzung, dass $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ . Kommst du drauf? Augenzwinkern

28.09.2015, 20:44

Kaffeevernichter

Auf diesen Beitrag antworten »

Ad Verständnis:
1. Induktionsschluss: zeigen, dass Behauptung für möglichst kleines $\begin{eqnarray*} n \end{eqnarray*}$ erfüllt ist.
2. Induktionsschluss: von Induktionsvoraussetztung $\begin{eqnarray*} A\left(n\right) \end{eqnarray*}$ auf Induktionsbehauptung $\begin{eqnarray*} A\left(n+1\right) \end{eqnarray*}$ schließen, mittels Umformung.

Ad Beispiel:
Ich gehe von folgender Gleichung aus:
$\begin{eqnarray*} 2^{n}\geq n^2 \end{eqnarray*}$
Multipliziere beide Seiten der Ungleichung mit $\begin{eqnarray*} 2 \end{eqnarray*}$
$\begin{eqnarray*} 2^{n+1}\geq 2n^2 \end{eqnarray*}$

Nun mache ich eine Abschätzung wobei ich weiterhin $\begin{eqnarray*} n\geq4 \end{eqnarray*}$ annheme:
$\begin{eqnarray*} n^2\geq2n+1 \end{eqnarray*}$
$\begin{eqnarray*} n\left(n-2\right)\geq1 \end{eqnarray*}$
Diese Ungleichung ist für alle $\begin{eqnarray*} n\geq4 \end{eqnarray*}$ eindeutig erfüllt da für zwei Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ mit $\begin{eqnarray*} m>1 \end{eqnarray*}$ gilt $\begin{eqnarray*} m^2>1 \end{eqnarray*}$ (Wäre also schon erfüllt bei $\begin{eqnarray*} n>2 \end{eqnarray*}$ )

$\begin{eqnarray*} 2^{n+1}\geq 2n^2=n^2+n^2\geq n^2+2n+1=\left(n+1\right)^2 \end{eqnarray*}$
Also habe ich gezeigt:
$\begin{eqnarray*} 2^{n}\geq n^2\Rightarrow 2^{n+1}\geq \left(n+1\right) ^2 \end{eqnarray*}$ (Darf ich das so anschreiben? verwirrt

)
Womit der Beweis erbracht sein sollte? Hammer

28.09.2015, 23:47

Guppi12

Auf diesen Beitrag antworten »

Hi,

Zitat:

Diese Ungleichung ist für alle $\begin{eqnarray*} n\geq4 \end{eqnarray*}$ eindeutig erfüllt da für zwei Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ mit $\begin{eqnarray*} m>1 \end{eqnarray*}$ gilt $\begin{eqnarray*} m^2>1 \end{eqnarray*}$ (Wäre also schon erfüllt bei $\begin{eqnarray*} n>2 \end{eqnarray*}$ )

Meinst du hier zufällig, dass für zwei Zahlen $\begin{eqnarray*} m,n \end{eqnarray*}$ mit $\begin{eqnarray*} m,n>1 \end{eqnarray*}$ gilt $\begin{eqnarray*} mn > 1 \end{eqnarray*}$ ?
Das könntest du hier in der Tat als Argument anführen.

Man könnte alles in einem Rutsch so aufschreiben:

$\begin{eqnarray*} 2^{n+1} = 2\cdot 2^n\overset{IV}{\geq}2n^2 = n^2 + n^2 = n^2+n\cdot n \geq n^2+4\cdot n = n^2+2n+2n\geq n^2+2n+1 = (n+1)^2 \end{eqnarray*}$ .

29.09.2015, 08:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Kaffeevernichter
1. Induktionsschluss: zeigen, dass Behauptung für möglichst kleines $\begin{eqnarray*} n \end{eqnarray*}$ erfüllt ist.

So formuliert trifft es die Sache nicht: Im vorliegenden Fall ist die Behauptung etwa für n=0,1,2 erfüllt, für n=3 jedoch nicht.

Es muss also ein $\begin{align*} n_0 \end{align*}$ gefunden werden, für das die Behauptung gilt UND der Induktionsschritt $\begin{align*} n\to n+1 \end{align*}$ tatsächlich für alle $\begin{align*} n\geq n_0 \end{align*}$ greift. Letzterer Punkt ist es nämlich, an dem eine Wahl von z.B. $\begin{align*} n_0=0 \end{align*}$ in der vorliegenden Aufgabe scheitert.

In der Regel ist das $\begin{align*} n_0 \end{align*}$ allerdings vorgegeben (hier wohl auch, ist durch die Threadabtrennung nicht so ganz deutlich).

29.09.2015, 10:20

Kaffeevernichter

Auf diesen Beitrag antworten »

Zitat:

Original von Guppi12
Meinst du hier zufällig, dass für zwei Zahlen $\begin{eqnarray*} m,n \end{eqnarray*}$ mit $\begin{eqnarray*} m,n>1 \end{eqnarray*}$ gilt $\begin{eqnarray*} mn > 1 \end{eqnarray*}$ ?

Ja, das meine ich. Deine Formulierung ist allgemeiner und damit natürlich schöner.

Aha, deine Lösung ist etwas flotter (und Verständlicher), da man keine Nebenrechnung braucht - meine gefällt mir aber besser, da ich sie selber gemacht habe smile

Zitat:

Original von HAL 9000

Zitat:

Original von Kaffeevernichter
1. Induktionsschluss: zeigen, dass Behauptung für möglichst kleines $\begin{eqnarray*} n \end{eqnarray*}$ erfüllt ist.

So formuliert trifft es die Sache nicht: Im vorliegenden Fall ist die Behauptung etwa für n=0,1,2 erfüllt, für n=3 jedoch nicht.

Könnte man also sagen(?):
Induktionsschluss: zeigen, dass Behauptung für möglichst kleines $\begin{eqnarray*} n\in D \end{eqnarray*}$ erfüllt ist, wobei $\begin{eqnarray*} D \end{eqnarray*}$ der Definitionsbereich für $\begin{eqnarray*} n \end{eqnarray*}$ ist.

29.09.2015, 10:32

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Kaffeevernichter
Könnte man also sagen(?):
Induktionsschluss: zeigen, dass Behauptung für möglichst kleines $\begin{eqnarray*} n\in D \end{eqnarray*}$ erfüllt ist, wobei $\begin{eqnarray*} D \end{eqnarray*}$ der Definitionsbereich für $\begin{eqnarray*} n \end{eqnarray*}$ ist.

Naja, das habe ich ja mit

Zitat:

Original von HAL 9000
In der Regel ist das $\begin{align*} n_0 \end{align*}$ allerdings vorgegeben

gemeint.

Mein letzter Beitrag bezog sich also eher auf eine Aufgabenformulierung der Art:

Zitat:

Man zeige, dass es eine natürliche Zahl $\begin{align*} n_0 \end{align*}$ gibt, so dass für alle $\begin{align*} n\geq n_0 \end{align*}$ die Ungleichung $\begin{align*} 2^n\geq n^2 \end{align*}$ gilt.

oder noch schärfer:

Zitat:

Man finde die kleinste natürliche Zahl $\begin{align*} n_0 \end{align*}$ , so dass für alle $\begin{align*} n\geq n_0 \end{align*}$ die Ungleichung $\begin{align*} 2^n\geq n^2 \end{align*}$ gilt.

01.10.2015, 11:40

Kaffeevernichter

Auf diesen Beitrag antworten »

Danke HAL9000 und Guppi12, habe noch ein paar beispiele zur vollständigen Induktion gerechnet und die haben jetzt alle geklappt. Ich glaube vollständige Induktion sitzt jetzt! Tanzen

Neue Frage »

Antworten »

Vollständige Induktion: n² <= 2^n

Verwandte Themen