Beweis durch vollständige Induktion - Anwendung einer bestimmten Ungleichung bei n^2 < 2^n

07.10.2012, 12:36

Kris_

Beweis durch vollständige Induktion - Anwendung einer bestimmten Ungleichung bei n^2 < 2^n

Meine Frage:
Hallo!

Für einer Kreuzerlübung in Mathe 1 muss ich beweisen, dass n^2 < 2^n ist. Das war auch kein Problem, dieser Beweis ist mit Erklärungen in vielen Foren erläutert.

Ich schreibe also für A(n+1):

(n+1)^2 < 2^(n+1)

2^(n+1) = 2^n * 2

2 * n^2 < 2 * 2^n

2* n^2 > n^2 +2n +1 weil n^2 > 2n +1

dh. 2^(n+1) > 2*n^2 > (n+1)^2

dh. 2^(n+1) > (n+1)^2 q.e.d.

Meine Frage lautet jetzt aber: woher weiß ich, dass ich beim Induktionsschritt die Ungleichung n^2 > 2n +1 verwenden muss?
Ich wäre von alleine nie darauf gekommen, dass ich das hier verwenden kann, gibt es einen Trick, wie ich herausfinde, wie ich A(n) und A(n+1) verknüpfen kann?

Meine Ideen:
Ich denke, es könnte etwas damit zu tun haben, dass ich eine Wahre Aussage suche, in der mein Ausgangswert A(n) vorkommt. Aber mir fehlt noch die "mathematische Kreativität" um diese Zusammenhänge zu sehen.

07.10.2012, 12:49

Mystic

Auf diesen Beitrag antworten »

RE: Beweis durch vollständige Induktion - Anwendung einer bestimmten Ungleichung bei n^2 < 2^n
Dieser Beweisteil ist - so wie du ihn angeschrieben hast - extrem unübersichtlich und du würdest von mir höchstens 6 Punkte von 10 dafür bekommen... Versuch mal die nachfolgende Zeile

$\begin{eqnarray*} n^2<2^n \Rightarrow (n+1)^2=n^2+\underbrace{2n+1}_{<n^2 \text{ für } n \ge \ldots} < \ldots <2\cdot 2^n= 2^{n+1} \end{eqnarray*}$

sinnvoll zu ergänzen... Hier wäre dann natürlich auch die unterklammerte Aussage noch zu beweisen...

07.10.2012, 13:15

Kris_

Auf diesen Beitrag antworten »

RE: Beweis durch vollständige Induktion - Anwendung einer bestimmten Ungleichung bei n^2 < 2^n
Da hast du Recht, danke!
Habs mit deiner Zeile probiert, der IS schaut nun so aus:

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

Den Beweis für n^2 > 2n +1 habe ich mir schon gestern angeschaut, er ist nicht schwer und ich kann ihn erklären.

Trotzdem verstehe ich nicht, warum ich ausgerechnet diese Ungleichung benutze. Wie kann ich dem Vortragenden erklären, wie ich darauf komme bzw. wie kann ich lernen, in Zukunft auf solche Dinge zu kommen? verwirrt

07.10.2012, 13:20

Mystic

Auf diesen Beitrag antworten »

RE: Beweis durch vollständige Induktion - Anwendung einer bestimmten Ungleichung bei n^2 < 2^n

Zitat:

Original von Kris_
Da hast du Recht, danke!
Habs mit deiner Zeile probiert, der IS schaut nun so aus:

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

Der rote Teil gehört weg (was ist dir denn da eingefallen?)... geschockt

Zitat:

Original von Kris_
Trotzdem verstehe ich nicht, warum ich ausgerechnet diese Ungleichung benutze. Wie kann ich dem Vortragenden erklären, wie ich darauf komme bzw. wie kann ich lernen, in Zukunft auf solche Dinge zu kommen? verwirrt

Naja, die Abschätzung

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

wird ja im Beweis explizit verwendet... Irgendwie versteh ich also deine Frage nicht? verwirrt

07.10.2012, 13:26

Kris_

Auf diesen Beitrag antworten »

Oh, wird das so angezeigt? Dann muss ich mir den Formeleditor noch einmal vornehmen. Ich meinte eigentlich, dass nach dieser Zeile eben herauskommt, dass

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

Mit meiner Frage meinte ich, dass ich den Beweis so verstehe, wie er da steht, aber als ich versucht habe, selber zu beweisen, dass

$\begin{eqnarray*} n^{2} < 2^{n} \end{eqnarray*}$

mir beim IS nicht eingefallen ist, wie ich A(n) einbauen kann. Ich wäre selbstständig eben nicht, auf diese Ungleichung gekommen. Ich hoffe, dass mein Anliegen jetzt etwas klarer ist o.o

Danke jedenfalls!!

07.10.2012, 13:36

Mystic

Auf diesen Beitrag antworten »

Wenn du eine Ungleichungskette hast von der Art

$\begin{eqnarray*} (n+1)^2 < ... < ... < 2^{n+1} \end{eqnarray*}$

dann folgt daraus automatisch, dass auch

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

gilt, ohne dass du das zum Schluss noch einmal (noch dazu an total unpassender Stelle!) hervorhebst... geschockt

Was die zweite Frage betrifft, so musst du ja zeigen, dass

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

gilt... Wenn du immer dieses "Ziel" vor Augen hast und andererseits von der Darstellung

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

ausgehst, folgt doch mehr oder weniger automatisch, dass man

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

zeigen muss... Wenn nicht, dann üben, üben, üben... Augenzwinkern

07.10.2012, 13:39

Kris_

Auf diesen Beitrag antworten »

Danke =) Ich glaub ich habs jetzt endlich kapiert!
Und ja, ich muss noch viel üben, aber dafür studiere ich ja ^^ Freude

Neue Frage »

Antworten »

Beweis durch vollständige Induktion - Anwendung einer bestimmten Ungleichung bei n^2 < 2^n

Verwandte Themen