vollständige Induktion einer Ungleichung

23.10.2012, 22:08

Sasu132

Auf diesen Beitrag antworten »

vollständige Induktion einer Ungleichung

Meine Frage:
Guten Abend alle zusammen,

bisher habe ich die Übungsaufgaben für die Analysis Vorlesung immer ganz gut zusammengebastelt bekommen.

Doch nun bin ich auf eine Aufgabe gestoßen, über die ich mir schon viele Stunden lang den Kopf zerbrochen habe und einfach nicht auf die richtige Lösung komme.

Hier die Aufgabe:

Zeigen sie mittels vollständiger Induktion, dass für alle $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} \sqrt{2n} \begin{pmatrix} 2n \\ n \end{pmatrix} \leq 4^{n} \end{eqnarray*}$ gilt.

Meine Professorin meinte schon das wäre "etwas" kniffelig Big Laugh

Big Laugh

Könnt ihr mir da vielleicht einen Tipp geben, wie ich die Induktion durchführen könnte? Ungleichungen sind wirklich nicht meine Spezialität unglücklich

unglücklich

Ich würde mich über Antworten sehr freuen!

Wünsche euch noch einen schönen Abend

Ich werde derweilen noch ander Aufgabe weiterbrüten Big Laugh

Big Laugh

Meine Ideen:
Also eine vollständige Induktion durchführen ist kein Problem.
Wir hatten bisher welche mit Summenzeichen, leider noch nie mit Ungleichungen unglücklich

unglücklich

23.10.2012, 22:59

Causal

Auf diesen Beitrag antworten »

RE: vollständige Induktion einer Ungleichung
Hast du denn schon überhaupt schon was aufgeschrieben, bevor du die Frage gestellt hast?
Zeig uns mal, wo du nicht weiterkommst und wir geben dir dann einige Tipps.

Gruß, Causal

24.10.2012, 18:36

Sasu132

Auf diesen Beitrag antworten »

klar habe ich schon was aufgeschrieben smile

smile

hier mal mein ansatz:

$\begin{eqnarray*} \sqrt{2n} \begin{pmatrix} 2n \\ n \end{pmatrix} \leq 4^{n} \end{eqnarray*}$

Induktionsanfang

n=0 setzen

$\begin{eqnarray*} \sqrt{2*0} \begin{pmatrix} 2*0 \\ 0 \end{pmatrix} 4^{0} \end{eqnarray*}$
$\begin{eqnarray*} 0\leq 1 \end{eqnarray*}$

also wahr!

Induktionsschritte

n --> n+1

$\begin{eqnarray*} \sqrt{2(n+1)} \begin{pmatrix} 2(n+1) \\ n+1 \end{pmatrix} \leq 4^{n+1} \end{eqnarray*}$
$\begin{eqnarray*} \sqrt{2n+2} \begin{pmatrix} 2n+2 \\ n+1 \end{pmatrix} \leq 4^{n+1} \end{eqnarray*}$
$\begin{eqnarray*} \sqrt{2n+2} * (2n+2) + \sqrt{2n+2} * (n+1) \leq 4^{n+1} \end{eqnarray*}$
$\begin{eqnarray*} \sqrt{8n^{3}+8n^{2}+8n+8 } * (2n+2) + \sqrt{2n^{3}+2n^{2}+2n+2} \leq 4^{n}*4 \end{eqnarray*}$

sooo...soweit bin ich jetzt
ich hoffe ich habe mich nicht vertippt Big Laugh

Big Laugh

nun muss ich irgendwie die Induktionsvoraussetzung einsetzen, aber ich weiß nicht wie ich weiterrechnen soll....ist bis hierhin alles richtig?

unser übungsleiter meinte da gäbe es einen trick bei der aufgabe

24.10.2012, 18:52

HAL 9000

Auf diesen Beitrag antworten »

Mein Tipp ist: Beweise "etwas" mehr, nämlich

$\begin{eqnarray*} \sqrt{2n+1} \binom{2n}{n} \leq 4^n \end{eqnarray*}$ .

Der Grund dafür ist haargenau hier erläutert.

Nachtrag: War wohl zu subtil, dieser Tipp, wo dich doch noch viel grundsätzlichere Probleme bei der Induktion plagen. Na vielleicht weißt du ihn ja später zu schätzen. Augenzwinkern

Augenzwinkern

24.10.2012, 23:03

Sasu132

Auf diesen Beitrag antworten »

nein

Big Laugh

vielen dank für den tipp smile

smile

habe vorher noch gar nicht ins forum geschaut.

ich werde mir den link anschaun und dann hoffentlich die aufgabe lösen können.

ich werde die antwort dann nochmal posten, dann kannst du schaun, ob ich es richtig verstanden habe Augenzwinkern

Augenzwinkern

viele grüße

25.10.2012, 19:41

Sasu132

Auf diesen Beitrag antworten »

soo ich habe mir das Beispiel angeschaut und nochmal alles durchgerechnet smile

smile

wäre nett, wenn ihr mal draufschauen könntet, ob ich alles richtig gemacht habe oder ob evtl.
noch Fehler drin sind???

hier meine Lösung:

$\begin{eqnarray*} \sqrt{2n} * \begin{pmatrix} 2n \\ n \end{pmatrix} \leq 4^{n} \end{eqnarray*}$

$\begin{eqnarray*} \sqrt{2n+2} * \begin{pmatrix} 2n+2 \\ n+1 \end{pmatrix} \leq 4^{n} \end{eqnarray*}$

$\begin{eqnarray*} 4*4^{n} \geq \sqrt{2n+2} * \frac{(2n+2)!}{(n+1)!(2n+2-n-1)!} \end{eqnarray*}$

$\begin{eqnarray*} 4*\sqrt{2n} \begin{pmatrix} 2n \\ n \end{pmatrix} \geq \sqrt{2n+2} * \frac{(2n+2)!}{(n+1)! (n+1)!} \end{eqnarray*}$

$\begin{eqnarray*} 4*\sqrt{2n} * \frac{2n!}{n!(2n-n)!} \geq \sqrt{2n+2} * \frac{(2n+2)(2n+1)2n!}{(n+1)(n+1)n!n!} \end{eqnarray*}$

$\begin{eqnarray*} 4*\sqrt{2n} * \frac{2n!}{n!n!} \geq \sqrt{2n+2} * \frac{2(2n+1)}{n+1} * \frac{2n!}{n!n!} \end{eqnarray*}$

$\begin{eqnarray*} 4*\sqrt{2n} \geq \sqrt{2n+2} * \frac{4n+2}{n+1} \end{eqnarray*}$

$\begin{eqnarray*} 16 * 2n \leq 2(n+1) * \frac{16n^{2}+16n+4 }{(n+1)^{2} } \end{eqnarray*}$

$\begin{eqnarray*} 16n * (n+1) \leq 16n^{2}+16n+4 \end{eqnarray*}$

$\begin{eqnarray*} 16n^{2}+16n \leq 16n^{2}+16n+4 \end{eqnarray*}$

q.e.d.

smile

smile

Anzeige

25.10.2012, 20:04

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Sasu132
$\begin{eqnarray*} 4*\sqrt{2n} ~{\color{red}\geq}~ \sqrt{2n+2} * \frac{4n+2}{n+1} \end{eqnarray*}$

$\begin{eqnarray*} 16 * 2n ~{\color{blue}\leq}~ 2(n+1) * \frac{16n^{2}+16n+4 }{(n+1)^{2} } \end{eqnarray*}$

Welches wundersame Ereignis hat die Relationszeichen so plötzlich gedreht? Augenzwinkern

Augenzwinkern

Klar ist, dass so der Beweis nicht funktioniert. Deine Professorin hat die Anmerkung "knifflig" nicht umsonst angebracht. Big Laugh

Big Laugh

25.10.2012, 20:15

Sasu132

Auf diesen Beitrag antworten »

oh nein

unglücklich

dacht ich mir's doch....das ging irgendwie zu einfach.

aber davor ist alles richtig?
wie gehe ich denn dann weiter vor bzw. wie führe ich die induktion zuende?

25.10.2012, 20:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Sasu132
wie gehe ich denn dann weiter vor bzw. wie führe ich die induktion zuende?

Gar nicht - ab hier

Zitat:

Original von Sasu132
$\begin{eqnarray*} 4*\sqrt{2n} \begin{pmatrix} 2n \\ n \end{pmatrix} \geq \sqrt{2n+2} * \frac{(2n+2)!}{(n+1)! (n+1)!} \end{eqnarray*}$

sind all deine Ungleichungen falsch, das ist auch nicht reparierbar.

Wie ich oben schon sagte, beweise lieber eine andere Behauptung.

25.10.2012, 20:28

Sasu132

Auf diesen Beitrag antworten »

ok werde ich machen smile

smile

verrätst du mir dann warum ich +1 noch unter die wurzel packen soll?

25.10.2012, 20:39

HAL 9000

Auf diesen Beitrag antworten »

Anscheinend hast du meinen Beitrag von gestern 18:52 vollständig ignoriert, denn die Erklärung dafür hab ich oben auch schon geliefert, und zwar durch die Anbringung des Links, aus dem ich jetzt mal zitiere:

Zitat:

Original von AD
Eine zweiter Tipp: Manchmal lohnt es sich, eine schärfere Aussage als die geforderte zu beweisen. Im ersten Moment erscheint das widersinnig, aber auf den zweiten Blick nicht mehr: Mit einer schärferen Aussage kann man ja im Induktionsschritt auch mehr voraussetzen!

29.10.2012, 17:05

Sasu132

Auf diesen Beitrag antworten »

bei meiner lösung weiter oben, wechselt das relationszeichen nicht, wenn man quadriert???

ich bekomm das mit deinem vorschlag irgendwie nicht hin :'(
ich meine jetzt statt Wurzel(2n) mit Wurzel(2n+1) zu rechnen.

wäre sehr lieb, wenn du mir den richtigen Lösungsweg zeigen könntest. Am Anfang dürfte das doch quasi das selbe sein oder???

unglücklich

unglücklich

29.10.2012, 17:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Sasu132
bei meiner lösung weiter oben, wechselt das relationszeichen nicht, wenn man quadriert???

Wenn auf beiden Seiten einer Ungleichung eine nichtnegative Zahl steht, warum soll dann das Relationszeichen beim Quadrieren wechseln??? Du hast schon merkwürdige Ideen bzw. Regeln im Kopf. unglücklich

unglücklich

29.10.2012, 17:40

Sasu132

Auf diesen Beitrag antworten »

mmmh dann bin ich total ratlos unglücklich

unglücklich

kannst du mir da bitte helfen....wäre sehr nett von dir!

ist ja nicht so, als hätte ich nicht schon seeehr viele stunden an dieser einen aufgabe gesessen unglücklich

unglücklich

unglücklich

29.10.2012, 18:04

HAL 9000

Auf diesen Beitrag antworten »

Ich versteh jetzt nicht so richtig, wo noch die Schwierigkeiten liegen: Im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ führen wir zunächst den Binomialkoeffizienten $\begin{eqnarray*} \binom{2(n+1)}{n+1} = \binom{2n+2}{n+1} \end{eqnarray*}$ durch Herausziehen der entsprechenden Faktoren auf $\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ zurück

$\begin{eqnarray*} \sqrt{2n+3} \binom{2n+2}{n+1} = \sqrt{2n+3} \frac{(2n+2)(2n+1)}{(n+1)^2} \binom{2n}{n} = \sqrt{2n+3} \frac{2(2n+1)}{n+1} \binom{2n}{n} \end{eqnarray*}$ .

Nun können wir mit dem gemäß Induktionsvoraussetzung geltenden $\begin{eqnarray*} \binom{2n}{n} \leq \frac{1}{\sqrt{2n+1}}\cdot 4^n \end{eqnarray*}$ dies nach oben abschätzen

$\begin{eqnarray*} \ldots \leq \sqrt{2n+3} \frac{2(2n+1)}{n+1} \cdot \frac{1}{\sqrt{2n+1}}\cdot 4^n = \frac{2\sqrt{(2n+1)(2n+3)}}{n+1}\cdot 4^n \end{eqnarray*}$

Wenn es nun gelingt, diesen Ausdruck rechts nach oben durch die rechte Seite $\begin{eqnarray*} 4^{n+1} \end{eqnarray*}$ der Induktionsbehauptung abzuschätzen, dann ist man fertig mit dem Induktionsschritt. Was ist am Beweis von

$\begin{eqnarray*} \frac{2\sqrt{(2n+1)(2n+3)}}{n+1} \cdot 4^n \leq 4^{n+1} \end{eqnarray*}$

denn nun noch so verdammt schwer? verwirrt

verwirrt

29.10.2012, 21:16

Sasu132

Auf diesen Beitrag antworten »

wenn man sowas noch nie hatte ist das schwer, glaube mir Augenzwinkern

Augenzwinkern

weil du einfach nicht weißt wie du
ansetzen musst.

also den ersten teil habe ich verstanden smile

smile

und was mach ich jetzt mit der ungleichung, die du unten hingeschrieben hast?
die ist ja noch nicht grade einfach (du meintest zu beginn man könnte das mit wurzel(2n+1) sehr viel einfacher machen)

einen schönen abend Augenzwinkern

Augenzwinkern

29.10.2012, 21:25

Sasu132

Auf diesen Beitrag antworten »

ich könnte doch statt $\begin{eqnarray*} 4^{n+1} \end{eqnarray*}$ auch $\begin{eqnarray*} 4^{n} * 4 \end{eqnarray*}$ schreiben oder?
dann könnte ich das $\begin{eqnarray*} 4^{n} \end{eqnarray*}$ auf beiden seiten wegkürzen...

29.10.2012, 21:44

chris95

Auf diesen Beitrag antworten »

Ja, du musst nur noch zeigen, dass

$\begin{eqnarray*} 2\frac{\sqrt{(2n+1)(2n+3)}}{n+1} \le 4 \end{eqnarray*}$

ist.

Da musste nur noch quadrieren, und wissen dass 0<1 ist.

Denke aber eine gute Argumentation wenn du quadrierst und Wurzel ziehst.

29.10.2012, 22:07

Sasu132

Auf diesen Beitrag antworten »

also wenn ich das quadriere und auflöse kommt da $\begin{eqnarray*} \frac{16n^{2} + 24n + 12 }{n^{2} + 2n + 1} \leq 16 \end{eqnarray*}$ raus. ist das richtig?

29.10.2012, 22:15

Sasu132

Auf diesen Beitrag antworten »

wenn ich das vorher kürze komme ich auf $\begin{eqnarray*} \frac{4n^{2} + 8n + 3 }{n^{2} + 2n + 1} \leq 4 \end{eqnarray*}$

29.10.2012, 23:05

chris95

Auf diesen Beitrag antworten »

Jetzt bringste den Nenner noch auf die andere Seite und dann stehts ja schon fast da.

30.10.2012, 06:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Sasu132
wenn man sowas noch nie hatte ist das schwer, glaube mir Augenzwinkern

Augenzwinkern

weil du einfach nicht weißt wie du ansetzen musst.

Unsinn, du hattest es doch oben mit $\begin{eqnarray*} \sqrt{2n} \end{eqnarray*}$ versucht und an sich die richtigen Umformungsschritte gemacht - nur mit dem Pech, dass die letztlich erreichte Ungleichung in der falschen Richtung galt. Es konnte also mit $\begin{eqnarray*} \sqrt{2n} \end{eqnarray*}$ prinzipiell nicht gehen.

Dasselbe aber nochmal mit $\begin{eqnarray*} \sqrt{2n+1} \end{eqnarray*}$ durchgezogen wärest du zum Ziel gekommen, aber da hat dich ja plötzlich eine unerklärliche Lähmung befallen. Es ist also NICHT der fehlende Ansatz, der war nämlich klar da, sondern seltsamerweise Resignation deinerseits.

30.10.2012, 09:06

Sasu132

Auf diesen Beitrag antworten »

ok, dann sieht das ganze also wie folgt aus:

$\begin{eqnarray*} \sqrt{2n + 1} * \begin{pmatrix} 2n \\ n \end{pmatrix} \leq 4^{n} \end{eqnarray*}$

n --> n+1

$\begin{eqnarray*} \sqrt{2n + 3} * \begin{pmatrix} 2n + 2 \\ n + 1 \end{pmatrix} \leq 4^{n + 1} \end{eqnarray*}$

$\begin{eqnarray*} \sqrt{2n + 3} * \frac{(2n + 2)(2n + 1)}{(n + 1)^{2} } * \begin{pmatrix} 2n \\ n \end{pmatrix} \leq 4^{n + 1} \end{eqnarray*}$

Nach Induktionsvoraussetzung gilt $\begin{eqnarray*} \begin{pmatrix} 2n \\ n \end{pmatrix} \leq \frac{1}{\sqrt{2n + 1} } * 4^{n} \end{eqnarray*}$

$\begin{eqnarray*} \sqrt{2n + 3} * \frac{2(2n + 1)}{n+1} * \frac{1}{\sqrt{2n + 1} } * 4^{n} \leq 4^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \frac{2 * \sqrt{(2n + 1)(2n + 3)} }{n + 1} * 4^{n} \leq 4^{n+1} \end{eqnarray*}$

$\begin{eqnarray*} \frac{4n^{2} + 8n + 3 }{n^{2} + 2n + 1 } \leq 4 \end{eqnarray*}$

$\begin{eqnarray*} 4n^{2} + 8n + 3 \leq 4n^{2} + 8n + 4 \end{eqnarray*}$

$\begin{eqnarray*} 0\leq 1 \end{eqnarray*}$

passt das so??? smile

smile

viele grüße

30.10.2012, 13:11

HAL 9000

Auf diesen Beitrag antworten »

Ja, passt. Freude

Freude

Wobei ich mir an der Stelle

Zitat:

Original von Sasu132
Nach Induktionsvoraussetzung gilt $\begin{eqnarray*} \begin{pmatrix} 2n \\ n \end{pmatrix} \leq \frac{1}{\sqrt{2n + 1} } * 4^{n} \end{eqnarray*}$

$\begin{eqnarray*} \sqrt{2n + 3} * \frac{2(2n + 1)}{n+1} * \frac{1}{\sqrt{2n + 1} } * 4^{n} \leq 4^{n+1} \end{eqnarray*}$

noch ein paar Worte derart gewünscht hätte: "Nach Einsetzen der Induktionsvoraussetzung benötigt man noch die Gültigkeit der Ungleichung ... die ich jetzt im folgenden äquivalent umforme".

Ansonsten hängt nämlich ein wenig in der Luft, wie das dann im Beweis einzuordnen ist, was du da im folgenden tust.

30.10.2012, 16:10

Sasu132

Auf diesen Beitrag antworten »

also müsste ich noch die gültigkeit dieser ungleichung beweisen??? und wie mache ich das??? smile

smile

30.10.2012, 16:30

HAL 9000

Auf diesen Beitrag antworten »

Aber das hast du doch gemacht, indem du das äquivalent bis zu einer wahren Aussage umgeformt hast! Ich sehe, du weißt die einzelnen Bestandteile gar nicht im Gesamtkonzept des Induktionsschrittes einzuordnen. Ich empfehle dir dringend, dies alles nochmal in Hinblick auf die Beweislogik zu überdenken.

Deswegen bevorzuge ich ja auch die Darstellung, wie ich sie oben gezeigt habe, die ist logisch klar nach dem Schema, wie man sehr oft Ungleichungen per Induktion beweist:

$\begin{eqnarray*} \mbox{Linke Seite der Induktionsbehauptung} &=& f\left( \mbox{Linke Seite der Induktionsvoraussetzung} \right)\\ &{\color{red}\leq}& f\left( \mbox{Rechte Seite der Induktionsvoraussetzung} \right) \\ &{\color{blue}\leq}& \mbox{Rechte Seite der Induktionsbehauptung} \end{eqnarray*}$

Dabei wird bei $\begin{eqnarray*} {\color{red}\leq} \end{eqnarray*}$ die Induktionsvoraussetzung eingesetzt (und $\begin{eqnarray*} f \end{eqnarray*}$ ist irgendeine monoton wachsende Funktion, in unserem Fall einfach linear mit positivem Anstieg), während man bei $\begin{eqnarray*} {\color{blue}\leq} \end{eqnarray*}$ weitere Abschätzungen einsetzt - so zumindest der verallgemeinerte "Schlachtplan".

30.10.2012, 17:44

chris95

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Deswegen bevorzuge ich ja auch die Darstellung, wie ich sie oben gezeigt habe, die ist logisch klar nach dem Schema, wie man sehr oft Ungleichungen per Induktion beweist:

$\begin{eqnarray*} \mbox{Linke Seite der Induktionsbehauptung} &=& f\left( \mbox{Linke Seite der Induktionsvoraussetzung} \right)\\ &{\color{red}\leq}& f\left( \mbox{Rechte Seite der Induktionsvoraussetzung} \right) \\ &{\color{blue}\leq}& \mbox{Rechte Seite der Induktionsbehauptung} \end{eqnarray*}$

Diese Methode ist natuerliche die feinere, da hierbei die Beweisrichtung klar ist. Da muss ich dir zustimmen. Jedoch ist es oft nicht so einfach einen Beweis zu fuehren und oft ist es einfacher, v.a. auch einleuchtender eben diese Aqeuivalenzumformungen zu machen. Dabei geht aber wie auch bei Sasu132 der Gedanke an die Beweisrichtung verloren.

30.10.2012, 17:46

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von chris95
Jedoch ist es oft nicht so einfach einen Beweis zu fuehren und oft ist es einfacher, v.a. auch einleuchtender eben diese Aqeuivalenzumformungen zu machen.

Ich hab ja auch nichts dagegen - aber dann muss man auch erklären, was man da tut, und wie es sich in den Beweiskontext einordnet. Ansonsten steht schnell mal inhaltlich $\begin{eqnarray*} \leq \end{eqnarray*}$ und $\begin{eqnarray*} \geq \end{eqnarray*}$ in derselben Ungleichungskette da, was die Sache dann völlig entwertet (siehe erster Versuch).

30.10.2012, 18:37

chris95

Auf diesen Beitrag antworten »

Jop, da hast du vollkommen recht. smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »