Vollständige Induktion bei Ungleichung

Neue Frage »

20.12.2009, 18:44	Tatiana	Auf diesen Beitrag antworten »
Vollständige Induktion bei Ungleichung Hallo, ich habe ein Problem bei dem Beweis dieser Aussage mithilfe vollständiger Induktion: Zu zeigen ist, dass die Ungleichung $\begin{eqnarray} 2n+1 \le 2^n \end{eqnarray}$ für alle natürlichen Zahlen größer gleich 3 gilt. Der Induktionsanfang ist mir klar. Doch beim Induktionsschritt von n auf n+1 komme ich nicht weiter: $\begin{eqnarray} 2(n+1)+1\le2^{n+1} \Longleftrightarrow 2n+3\le2^n \cdot 2 \end{eqnarray}$ Ich bitte ganz herzlich um Eure Hilfe. Liebe Grüße Tatiana
20.12.2009, 18:55	Airblader	Auf diesen Beitrag antworten »
$\begin{eqnarray} 2n+3 = 2n + 1 + 2 \end{eqnarray}$ Und jetzt die Voraussetzung anwenden. air
21.12.2009, 17:35	Tatiana	Auf diesen Beitrag antworten »
Also dann probiere ich es mal: $\begin{eqnarray} ... \Leftrightarrow (2n+1)+2 \le 2^{n+1} \end{eqnarray}$ Nach Induktionsvoraussetzung gilt: $\begin{eqnarray} 2n+1 \le 2^{n} \end{eqnarray}$ Damit ergibt sich: $\begin{eqnarray} 2^n + 2 \le 2 \cdot 2^{n} \Leftrightarrow 2 \le 2^n \Leftrightarrow 2 \le \underbrace{2 \cdot ... \cdot 2}_{\mbox{n-mal}} \end{eqnarray}$ Die letzte Ungleichung gilt für alle natürlichen Zahlen (wenn man die Null nicht hinzuzählt). Stimmt das so? Vielen Dank für die Antworten! Schöne Feiertage! Tatiana
21.12.2009, 17:58	Airblader	Auf diesen Beitrag antworten »
Um ehrlich zu sein kann ich nichtmal nachvollziehen, wie du überhaupt zu argumentieren versucht. Du musst zeigen: $\begin{eqnarray} 2(n+1)+1 \leq 2^{n+1} \end{eqnarray}$ Mit der Voraussetzung erhält man $\begin{eqnarray} 2(n+1)+1 = \underbrace{2n+1}_{\leq 2^n} + 2 \leq 2^n + 2 \stackrel{\text{()}}{\leq} 2 \cdot 2^n = 2^{n+1} \end{eqnarray}$ () gilt dabei deswegen, weil $\begin{eqnarray} n \geq 1 ~\Leftrightarrow~ 2^n \geq 2^1 ~\Leftrightarrow~ 2^n + 2^n = 2\cdot 2^n \geq 2^n + 2 \end{eqnarray}$ Edit: Ah, jetzt habe ich gesehen was du machst Blind bin. Nun, was bei dir einfach komplett fehlt ist die wichtigste Abschätzung - nämlich die, in der du die Voraussetzung verwendest. Du schreibst die Voraussetzung nochmal hin, es ist aber nicht ersichtlich, wo du sie eigentlich verwendest. air
21.12.2009, 18:03	Tatiana	Auf diesen Beitrag antworten »
Aha, jetzt habe ich es verstanden... Vielen lieben Dank, Airblader! Gruß Tatiana
21.12.2009, 18:05	Airblader	Auf diesen Beitrag antworten »
Gern geschehen. Beachte bitte, dass das nun sozusagen eine Komplettlösung war. Mache also was draus, schreibe nicht einfach ab, sondern verstehe es auch und wende es in anderen Aufgaben an. Beachte auch mein Edit oben. air
Anzeige

18.04.2010, 16:06	dieAnna	Auf diesen Beitrag antworten »
RE: Vollständige Induktion bei Ungleichung Hallo ihr Lieben, ich habe auch mal wieder eine Frage zur Induktion bei Ungleichungen. Die Aufgabe lautet: Beweisen Sie für alle $\begin{eqnarray} n \geq 4 \end{eqnarray}$ , dass gilt: $\begin{eqnarray} 2^{n} < n! \end{eqnarray}$ Ich habe das Prinzip der Induktion schon verstanden, mein Problem ist, dass ich nicht kreaktiv genug bin, die Terme mittels Dehnungsinvarianz, Translationsinvarianz etc. oder einfach nur unter Anwendung einfacher Potenzgesetzte (Bsp.: $\begin{eqnarray} 2^{n+1} = 2 2^{n} \end{eqnarray}$ ) so umzuformen, dass man nacher ganz leicht auf das Ergebnis kommt. Also ich fang mal an: IA) $\begin{eqnarray} n=4<br /> <br /> 2^{4} < 4! \end{eqnarray}$ , da $\begin{eqnarray} 16 < 24 \end{eqnarray}$ IB) $\begin{eqnarray} n \Rightarrow n+1 \end{eqnarray}$ , also: $\begin{eqnarray} 2^{n+1} < (n+1)! \forall n \geq 4 \end{eqnarray}$ 1. Frage: Mit welcher Seite ist es geschickter anzufangen? Ich fang einfach mal mit rechts an: IS) $\begin{eqnarray} (n+1)! = (n+1) * n! \end{eqnarray}$ (ist nach IV und Dehnungsinvarianz) $\begin{eqnarray} > (n+1) * 2^{n} \end{eqnarray}$ Soweit der Anfang. Jetzt muss ich $\begin{eqnarray} (n+1) * 2^{n} \end{eqnarray}$ solange umformen, bis da steht: $\begin{eqnarray} 2^{n+1} \end{eqnarray}$ (ggf. mit einem Faktor multipliziert Bsp.: 5 > 2 und 5 > 22). So. Ich habe also umgeformt zu: $\begin{eqnarray} (n+1) 2^{n} = n2^{n}+2^{n} \end{eqnarray}$ Und da hört es schon auf. Könnt ihr mir vielleicht einen Tip geben, wie es weiter geht? Wenn ich das dann hab, werde ich mal versuchen die Induktion mit der linken Seite anzufangen, so als Übung... Ich hoffe ihr könnt mir helfen. Liebe Grüße, dieAnna
18.04.2010, 16:13	Iorek	Auf diesen Beitrag antworten »
Wird das bei euch wirklich formal so aufgeschrieben? Du weißt, dass $\begin{eqnarray} n\geq 4 \end{eqnarray}$ , also kannst du weiter abschätzen: $\begin{eqnarray} 2^{n+1}=2\cdot 2^n\stackrel{IV}<2\cdot n!<? \end{eqnarray}$ Edit: Ich habs jetzt von der anderen Seite aufgeschrieben, du kannst das natürlich auch von der anderen Seite her umformen: $\begin{eqnarray} (n+1)!=n!\cdot (n+1) \stackrel{IV}> 2^n\cdot (n+1) >? \end{eqnarray}$
18.04.2010, 16:27	dieAnna	Auf diesen Beitrag antworten »
Hey, danke für die schnelle Antwort. Also so weit wie du es aufgeschrieben hast bin ich ja auch gekommen. Wie es danach weiter geht, weiß ich ja leider nicht. Da, wo bei dir Fragezeichen stehen, ist in meinem Kopf ebenfalls ein Fragezeichen... (weder von links, noch von rechts) Was meinst du mit formal korrekt? Ich sollte zuerst das kleinste n heraus finden, für das die Ungleichung gilt und dann für alle n > dieser Zahl die Induktion machen. Liebe Grüße, dieAnna
18.04.2010, 16:33	Iorek	Auf diesen Beitrag antworten »
Also formal würde mir bei dir die Induktionsvorraussetzung fehlen, wo du annimmst, dass die Behauptung für ein n gilt und dann den Induktionsschritt n->n+1 durchführst. $\begin{eqnarray} \text{Behauptung:}~2^n<n!~\forall n\in \mathbb N,~n\geq 4 \end{eqnarray}$ $\begin{eqnarray} \text{Beweis per vollständiger Induktion über n} \end{eqnarray}$ $\begin{eqnarray} \text{IA:}~n=4\dots \end{eqnarray}$ $\begin{eqnarray} \text{IV: Die Behauptung gelte für ein}~n\in\mathbb N,~n\geq 4 \end{eqnarray}$ $\begin{eqnarray} \text{IS:}~n\rightarrow n+1 \end{eqnarray}$ $\begin{eqnarray} 2^{n+1}=2\cdot 2^n\stackrel{IV}<2\cdot n! \end{eqnarray}$ Jetzt müssen wir das weiter umformen, um auf $\begin{eqnarray} (n+1)! \end{eqnarray}$ zu kommen, was fehlt uns denn noch dazu?
18.04.2010, 16:45	dieAnna	Auf diesen Beitrag antworten »
Die 1. Addiere ich einfach auf beiden seiten durch translationsinvarianz die 1? Dann würde da ja stehen: (2n!)+1 Darf ich dann die eins einfach in die Klammer ziehen und schreiben: 2(n+1)! Und das war es dann schon? (Links muss ich ja auch 1 addieren.)
18.04.2010, 16:47	Iorek	Auf diesen Beitrag antworten »
Bei der Fakultät ist addieren nicht sinnvoll. Was fehlt bei $\begin{eqnarray} 2\cdot n! \end{eqnarray}$ um irgendwas mit $\begin{eqnarray} (n+1)! \end{eqnarray}$ da stehen zu haben? Was müsste z.B statt der 2 da stehen, um darauf zu kommen?
18.04.2010, 17:01	dieAnna	Auf diesen Beitrag antworten »
statt 2 müsste da stehen (n+1) und von 2 auf (n+1) komme ich durch Multiplikation mit: $\begin{eqnarray} \frac{n+1}{2} \end{eqnarray}$ Also das wär dann ja die Dehnungsinvarianz, die ich ja leider auch immer auf beiden Seiten durchführen muss. Danke für deine Geduld!
18.04.2010, 17:03	Iorek	Auf diesen Beitrag antworten »
Wieso willst du das immer auf beiden Seiten durchführen? Schätz doch einfach weiter nach oben ab Was weißt du denn über n? Was weißt du dann über n+1? Wie kannst du dir das zu Nutze machen?
18.04.2010, 17:19	dieAnna	Auf diesen Beitrag antworten »
n ist größer/gleich 4 und n+1 ist dann größer/gleich 5 Was meinst du denn mit "nach oben abschätzen"?
18.04.2010, 17:21	Iorek	Auf diesen Beitrag antworten »
Du musst ja nur zeigen, dass $\begin{eqnarray} 2^{n+1}<(n+1)! \end{eqnarray}$ ist, wir sind jetzt bei diesem Schritt: $\begin{eqnarray} 2^{n+1}<2\cdot n! \end{eqnarray}$ . Wenn wir jetzt den Ausdruck auf der rechten Seite noch mehr vergrößern, schätzen wir ihn nach oben ab. Wir wissen jetzt, dass n+1=5>2 ist, wie können wir das jetzt verwerten?
20.04.2010, 20:54	dieAnna	Auf diesen Beitrag antworten »
also ich hab jetzt die rechte seite mit (n+1)/2 multipliziert, denn dadurch wird diese seite ja einfach NOCH größer. dies ist sicher gestellt durch n>=4, denn dadurch kann dieser faktor nicht kleiner als 2.5 werden. so. dann hab ich einfach die 2 weggekürzt und dann steht da: (n+1) * n! = (n+1)! fertig. ich hoffe ich darf das so machen, denn so hab ich das heut abgegeben Liebe Grüße
20.04.2010, 22:59	Iorek	Auf diesen Beitrag antworten »
Auch eine Möglichkeit, ich wollte eigentlich darauf hinaus, die 2 einfach durch das (n+1) zu ersetzen, deine Begründung ist aber auch richtig
21.04.2010, 14:25	dieAnna	Auf diesen Beitrag antworten »
ach ja, das wär ja noch einfacher gewesen^^ Vielen Dank!

Neue Frage »

Antworten »

Vollständige Induktion bei Ungleichung

Verwandte Themen