Bitte Erklärung für Induktionsbeweis n^2 < 2^n

06.04.2012, 23:56

fachfremd

Auf diesen Beitrag antworten »

Bitte Erklärung für Induktionsbeweis n^2 < 2^n

Hallo!

Ich sitze seit Tagen an dem Beweis für n^2 < 2^n. Ich habe den Beweis aus der Vorlesung fertig vor mir liegen, aber ich kann ihn nicht nachvollziehen. Einzelne Schritte darin sind mir schleierhaft.

Ich habe bislang Folgendes:

n^2 < 2^n soll bewiesen werden für n Element der nat. Zahlen (ohne 0). Dass die Aussage - bis auf Anfangswerte so stimmt, weiß ich, aber das tut ja erst mal nichts zur Sache.

Um die ersten "holperigen" Werte beweistechnisch zu umgehen, rechne ich sie aus mit dem Ziel, mit dem Beweis erst für größere n zu beginnen, um mir die Sache etwas einfacher zu machen. Also:

Für n = 1
1^2 < 2^1 = 1 < 2 wahr

Für n = 2 ... = 4 < 4 falsch (Beweis nicht möglich)
Für n = 3 ... = 9 < 8 falsch
Für n = 4 ... = 16 < 16 falsch
Für n = 5 ... = 25 < 32 wahr
Für n = 6 ... = 36 < 64 wahr
Für n = 7 ... = 49 < 128 wahr
u.s.w.

Ich kann aufgrund dieser Werte und ihres Verlaufs davon ausgehen, dass o.g. Aussage stimmt für n >= 5. Dies möchte ich als Bedingung zu meinem Beweis hinzunehmen, also:

n^2 < 2^n
für n >= 5 und n Element nat. Zahlen

Als nächstes wäre für n = n + 1 die zu beweisende Aussage bzw. muss Folgendes am Ende - sofern die Aussage wahr ist - stehen:

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

Den linken Teil kann ich direkt umformen (die Klammer auflösen):
(n + 1)^2
<=> (n + 1) (n + 1)
<=> n^2 + 1n + 1n +1
<=> n^2 + 2n + 1

Über den rechten Teil weiß ich folgendes:
2^n bedeutet 2 n-mal, also z.B. 2*2*2*2*...*n
Demnach ist 2^n + 1 (also einmal " *2 " mehr, und darum geht es ja)
2^n * 2
<=> 2^n + 2^n

Bis hierher komme ich. Das ist das, was ich weiß. Weiter komme ich allein nicht bzw. kann nachfolgende Schritte nicht nachvollziehen.

Kann mir bitte jemand weiterhelfen? Und zwar genau so für "Doofe", wie ich es eben bis hierhin selbst aufgeschrieben habe?

Viele Grüße,
Fachfremd

07.04.2012, 00:15

Che Netzer

Auf diesen Beitrag antworten »

RE: Bitte Erklärung für Induktionsbeweis n^2 < 2^n
Du bist also schon so weit, dass du unter der Annahme, dass $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ ist, zeigen musst, dass $\begin{eqnarray*} n^2+2n+1<2^n+2^n \end{eqnarray*}$ .

Dann nutze doch diese Annahme: $\begin{eqnarray*} \underbrace{n^2}_{<2^n}+2n+1<2^n+(2n+1) \end{eqnarray*}$ .
Ist das noch verständlich?

Jetzt musst du nur noch den Term 2n+1 mit $\begin{eqnarray*} 2^n \end{eqnarray*}$ nach oben abschätzen können (Tipp: Bernoulli - Edit: Doch nicht smile

smile

). Dann hast du gezeigt: $\begin{eqnarray*} (n+1)^2=n^2+2n+1<2^n+2n+1\leq2^n+2^n=2^{n+1} \end{eqnarray*}$ und bist fertig.

Ach ja, benutze aber Gleichheitszeichen, wenn dort welche hingehören:
$\begin{eqnarray*} (n+1)^2 {\color{red}=} n^2+2n+1 \end{eqnarray*}$
Das $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ ist ein Äquivalenzpfeil und verknüpft Aussagen bzw. Gleichungen.

mfg,
Ché Netzer

07.04.2012, 00:36

fachfremd

Auf diesen Beitrag antworten »

Wie kommst Du von

2^n + 2^n auf
2^n + (2n + 1)

???

07.04.2012, 00:41

Che Netzer

Auf diesen Beitrag antworten »

In der Richtung: Gar nicht.
Aber du möchtest zeigen, dass $\begin{eqnarray*} n^2+2n+1<2^n+2^n \end{eqnarray*}$ . Dazu kannst du nach Annahme zuerst aussagen, dass $\begin{eqnarray*} n^2+2n+1<2^n+2n+1 \end{eqnarray*}$ , indem du $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ benutzt. Jetzt musst du nur noch zeigen, dass $\begin{eqnarray*} 2^n+2n+1\leq2^n+2^n \end{eqnarray*}$

Sauber aufgeschrieben:
Induktionsannahme: $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ für ein beliebiges, aber festes $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ .

Induktionsschritt: Es soll gezeigt werden, dass $\begin{eqnarray*} (n+1)^2<2^{n+1} \end{eqnarray*}$
Dazu schreiben wir $\begin{eqnarray*} (n+1)^2=n^2+2n+1 \end{eqnarray*}$ (soweit warst du).
Nach Induktionsannahme gilt $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ , also $\begin{eqnarray*} n^2+2n+1<2^n+2n+1 \end{eqnarray*}$ .

Es bleibt zu zeigen, dass $\begin{eqnarray*} 2^n+2n+1\leq 2^n+2^n \end{eqnarray*}$ . Das ist äquivalent zu $\begin{eqnarray*} 2n+1\leq 2^n \end{eqnarray*}$ .

Edit: Moment, den Tipp mit Bernoulli nehme ich zurück...

07.04.2012, 00:53

fachfremd

Auf diesen Beitrag antworten »

Hm. Ich hänge an derselben Stelle, ich kann mit dem

2^n + 2n + 1

nichts anfangen. Wie kommst Du darauf?

Deine letzte Zeile kann ich nachvollziehen, da fällt auf beiden Seiten das 2^n weg (-> minus 2^n).

07.04.2012, 00:56

Che Netzer

Auf diesen Beitrag antworten »

Naja, wie du auf n²+2n+1 gekommen bist, weißt du ja wohl. Und die Induktionsannahme war $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ . Das setzt man dort nun einfach ein.

(Was den weiteren Verlauf betrifft, habe ich mich allerdings etwas geirrt...)

Anzeige

07.04.2012, 01:17

fachfremd

Auf diesen Beitrag antworten »

Was meinst Du genau?

n^2 + 2n + 1 ergab sich aus der Umformung von (n + 1)^2

Induktionsannahme n^2 < 2^n ist klar.

Auch n^2 + 2n + 1 < 2^n + 1

Aber was setzt Du jetzt wo ein?
Noch einmal: Wo nimmst Du die 2^n + 2n + 1 her? Vielleicht ist es ja offensichtlich - aber ich SEHE es nicht.

Und was Du danach geschrieben hast, ist falsch???

07.04.2012, 01:28

Che Netzer

Auf diesen Beitrag antworten »

Wenn du eine Ungleichung a<b hast. Dann ist auch a+c kleiner als b+c, oder?

Hier ist es genauso:
$\begin{eqnarray*} {\color{red}n^2}\qquad\qquad<\quad{\color{red}2^n} \end{eqnarray*}$ (Annahme)
$\begin{eqnarray*} \underbrace{{\color{red}n^2}+{\color{blue}2n+1}}_{(n+1)^2}<{\color{red}2^n}+{\color{blue}2n+1} \end{eqnarray*}$ (Die Folgerung daraus)

Das, was ich danach geschrieben habe, war eigentlich noch richtig, nur mein Tipp nicht. Aber erstmal solltest du die Ungleichung oben verstehen.

07.04.2012, 09:53

fachfremd

Auf diesen Beitrag antworten »

Ich verstehe :-)

Du hast entsprechend Deiner Erklärung und analog zu n^2 + 2n + 1
die linke Seite mit 2n + 1 erweitert:

n^2 + 2n + 1 < 2^n + 2n + 1

Bis hierher muss ich mir das jetzt noch mal komplett aufschreiben und anschauen.

07.04.2012, 11:31

Che Netzer

Auf diesen Beitrag antworten »

So könnte man das auch sehen. Ich bin aber eher so vorgegangen:
(n+1)² auflösen und einen der Summanden nach oben abschätzen; damit schätzt man ja auch die gesamte Summe ab.

07.04.2012, 17:54

frank09

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} \underbrace{{\color{red}n^2}+{\color{blue}2n+1}}_{(n+1)^2}<{\color{red}2^n}+{\color{blue}2n+1}. \end{eqnarray*}$

...ist nicht zu zeigen, vielmehr (wie oben schon erwähnt)
$\begin{eqnarray*} 2n+1<2^n \end{eqnarray*}$

nach Induktionsannahme genügt es zu zeigen.
$\begin{eqnarray*} 2n+1<n^2 \end{eqnarray*}$
bzw.
$\begin{eqnarray*} (n-1)^2>2 \end{eqnarray*}$

07.04.2012, 18:01

Che Netzer

Auf diesen Beitrag antworten »

@frank09: Das war ja auch nur der erste Schritt.
Ich schätze n² und 2n+1 jeweils mit $\begin{eqnarray*} 2^n \end{eqnarray*}$ nach oben ab, das ist der Induktionsschritt.

Ich bin nur etwas länger auf diese erste Abschätzung eingegangen, da die anscheinend nicht verstanden wurde.

07.04.2012, 22:42

fachfremd

Auf diesen Beitrag antworten »

Ich habe mal zusammengefasst, was ich bisher habe:

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

Linke Seite: (n+1)^2 = (n+1) (n+1) = n^2 + 1n + 1n +1 = n^2 + 2n + 1
Rechte Seite: 2^n+1 = 2^n * 2 = 2^n + 2^n

Also n^2 + 2n + 1 < 2^n + 2^n

Laut Ausgangsannahme:
n^2 + 2n + 1 < 2^n
An dieser Stelle ist mir nicht klar, warum man hier wieder mit 2^n arbeitet, und nicht mit 2^n+1 ? Ich will doch beweisen, dass die Annahme für alle n gilt (daher n+1).

n^2 + 2n + 1 < 2^n + 2n + 1 / rechts: 2^n analog zur linken Seite mit 2n+1 erweitert

Irgendwie komme ich hier wieder nicht weiter. Die Zusammenhänge zwischen den letzten Schritten ist mir auch nicht klar.

07.04.2012, 22:47

Che Netzer

Auf diesen Beitrag antworten »

Zitat:

Original von fachfremd
Also n^2 + 2n + 1 < 2^n + 2^n

Genau das will man zeigen. Und dass ist äquivalent zu $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ und $\begin{eqnarray*} 2n+1<2^n \end{eqnarray*}$ . Denn dann kann man die Ungleichungen addieren und erhält das, was man zeigen möchte.
Die erste dieser Ungleichungen gilt nach unserer Annahme.
Es bleibt noch $\begin{eqnarray*} 2n+1<2^n \end{eqnarray*}$ . Konntest du bis hierhin folgen?

Wenn nicht:
-Verstehst du, wieso man diese beiden Ungleichungen zeigen kann anstatt der einen?
-Weißt du, wieso die erste davon gilt? (bzw. wieso man davon ausgehen kann, dass sie gilt)

07.04.2012, 22:58

fachfremd

Auf diesen Beitrag antworten »

:-(

Ehrlich gesagt, nein.

n^2 + 2n + 1 < 2^n + 2^n
Das hier ist mir klar. Da wurde die Ausgangsannahme bzw. der Induktionsschritt lediglich umgeformt. Nur beweisen tut das nichts. Im Gegenteil. Das ist ja immernoch das, was man beweisen soll.

07.04.2012, 23:07

Che Netzer

Auf diesen Beitrag antworten »

Ja, das wollen wir zeigen.
Also formuliere ich mal die verbliebene Aufgabe:
Unter der Annahme, dass $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ , soll gezeigt werden, dass $\begin{eqnarray*} n^2+2n+1<2^n+2^n \end{eqnarray*}$ .

Ich nummeriere mal meine Aussagen durch. Nenn mir dann die erste, die du nicht mehr verstehst. (wenn du denn eine nicht verstehen solltest Augenzwinkern

Augenzwinkern

)

Und wenn wir in einer Summe einen Summanden durch etwas ersetzen, was größer ist, dann wird auch die ganze Summe größer, oder? [1]

Und da nach Annahme $\begin{eqnarray*} n^2 \end{eqnarray*}$ kleiner als $\begin{eqnarray*} 2^n \end{eqnarray*}$ ist, kann man daraus auch folgern, dass $\begin{eqnarray*} n^2+2n+1<2^n+2n+1 \end{eqnarray*}$ , indem wir den ersten Summanden durch einen größeren ersetzen. [2]

Es soll aber nicht gezeigt werden, dass $\begin{eqnarray*} n^2+2n+1<2^n+2n+1 \end{eqnarray*}$ ist, sondern, dass $\begin{eqnarray*} n^2+2n+1<2^n+2^n \end{eqnarray*}$ ist. [3]

Wenn wir jetzt zeigen können, dass $\begin{eqnarray*} 2n+1<2^n \end{eqnarray*}$ , dann können wir den Summanden (2n+1) durch $\begin{eqnarray*} 2^n \end{eqnarray*}$ ersetzen und die Summe wird noch größer. [4]

Wir wissen dann also, dass $\begin{eqnarray*} n^2+2n+1<2^n+2n+1 \end{eqnarray*}$ und dass $\begin{eqnarray*} 2^n+2n+1<2^n+2^n \end{eqnarray*}$ gelten. [5]

Und wenn eine erste Zahl kleiner ist als eine zweite und diese zweite Zahl kleiner ist als eine dritte, dann ist auch die erste kleiner als die dritte. [6]

Aus Aussage [6] können wir dann folgern, dass $\begin{eqnarray*} n^2+2n+1<2^n+2^n \end{eqnarray*}$ ist. Und das war die Aufgabe. (siehe oben)

08.04.2012, 01:34

fachfremd

Auf diesen Beitrag antworten »

Hallo!

Ich hab eben erst geshen, dass Du noch geantwortet hast. Hatte mich in der Zwischenzeit selbst weiter auf die Suche nach der Lösung des (meines) Problems begeben.

Aussage [1] ist klar.

Bei Aussage [2] geht es schon los mit "Und da nach Annahme n^2 kleiner als 2^n ist, kann man daraus auch folgern, dass ..."
Hiermit habe ich ein "philosophisches" Problem: Wie kann ich aus etwas, dass ich beweisen soll - erst noch beweisen muss - etwas FOLGERN? Die Behauptung n^2 < 2^n könnte doch völliger Mumpitz sein - ich weiß ja noch gar nichts darüber. Ich will/muss ja erst zeigen, dass das so stimmt.

???

So, und den Rest schau ich mir morgen an, jetzt bin ich zu müde dafür.

Ich wünsche schon einmal Frohe Ostern :-)

08.04.2012, 01:48

Che Netzer

Auf diesen Beitrag antworten »

Das liegt am grundsätzlichen Verfahren bei der Induktion:
Man nimmt an, dass die Aussage für ein n gilt. Dann folgert man daraus, dass sie auch für n+1 gilt. Also können wir voraussetzen, dass $\begin{eqnarray*} n^2<2^n \end{eqnarray*}$ . Allerdings nur für ein festes n. Wenn wir zeigen, dass es einen Wert gibt, für den diese Aussage gilt und dass sie - wenn sie für n gilt - auch für n+1 gilt, gilt sie ja für alle Zahlen ab dem ersten Wert; wie beim Domino Augenzwinkern

Augenzwinkern

Was übrigens kein schlechter Vergleich ist: Angenommen, Dominostein Nummer n fällt um. Dann ist zu zeigen, dass daraufhin auch Dominostein Nummer n+1 umfallen würde (dabei darf man dann voraussetzen, dass Stein Nummer n umfällt). Und wenn man dann im Induktionsanfang einen ersten Stein umkippt, fallen alle (weiteren) um.

08.04.2012, 08:55

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von fachfremd
Die Behauptung n^2 < 2^n könnte doch völliger Mumpitz sein - ich weiß ja noch gar nichts darüber. Ich will/muss ja erst zeigen, dass das so stimmt.

Doch, du weisst etwas darüber, nämlich dass es überhaupt ein n gibt, für welches die Behauptung stimmt... Das ist tatsächlich sehr wichtig und mit diesem Nachweis (=Induktionsanfang) beginnt ja auch jeder Induktionsbeweis...

Im übrigen habe ich dem, was Che Netzer oben schon sehr schön gesagt hat (mit den Dominosteinen) nichts hinzuzufügen... Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »