Beschränktheit mittels vollst. Induktion beweisen

31.10.2011, 22:18

Mikadobrain

Beschränktheit mittels vollst. Induktion beweisen

Hallo zusammen,
ich stehe wieder mal vor Problemen.
Ich möchte zeigen, dass
$\begin{eqnarray*} \frac{n\cdot 2^{n} }{3^{n}} \end{eqnarray*}$
beschränkt ist.
Den Beweis für die Existenz einer oberen Schranke habe ich mir so gedacht:

$\begin{eqnarray*} a_{1}= \frac{2}{3}, a_{2}=\frac{8}{9}, a_{3}=\frac{4}{3}, a_{4}= \frac{64}{81} \end{eqnarray*}$

Induktionsanfang: $\begin{eqnarray*} a_{4} < a_{3} \end{eqnarray*}$

Induktionsannahme: $\begin{eqnarray*} a_{n} < a_{n-1} \end{eqnarray*}$

Induktionsschluss: $\begin{eqnarray*} n -> n+1 \end{eqnarray*}$

$\begin{eqnarray*} a_{n+1} = (n+1)\frac{2^{n+1} }{3^{n+1}} < a_{n} = (n)\frac{2^{n} }{3^{n}} <=> (n+1)\frac{2^{n}\cdot 2 }{3^{n}\cdot 3} < (n)\frac{2^{n-1} \cdot 2}{3^{n-1}\cdot 3} <=> (n+1)\frac{2^{n}}{3^{n}} < (n)\frac{2^{n-1}}{3^{n-1}} \Rightarrow ((n+1)-1)\frac{2^{n}}{3^{n}} < ((n)-1)\frac{2^{n-1} }{3^{n-1}} \square \end{eqnarray*}$

Gesetzt den Fall alles davor sei überhaupt richtig: Ist die Folgerung in der letzten Zeile zulässig? Kann man das einfach so dreist da reinschieben, das -1?

Der Beweis für die untere Schranke läuft genau nach dem gleichen Schema, allerdings mit der Annahme $\begin{eqnarray*} a_{n} > 0 \end{eqnarray*}$

Ist das korrekt soweit?

Lg,
Micha

01.11.2011, 08:50

klarsoweit

Auf diesen Beitrag antworten »

RE: Beschränktheit mittels vollst. Induktion beweisen

Zitat:

Original von Mikadobrain
Ist die Folgerung in der letzten Zeile zulässig? Kann man das einfach so dreist da reinschieben, das -1?

Ohne eine schlüssige Begründung geht das natürlich nicht. Und selbst wenn das stimmen würde, hast du jetzt gezeigt, daß aus $\begin{eqnarray*} a_{n+1} < a_{n} \end{eqnarray*}$
die Ungleichung $\begin{eqnarray*} a_{n} < a_{n-1} \end{eqnarray*}$ folgt. Das ist aber die falsche Richtung. Du mußt zeigen, daß aus $\begin{eqnarray*} a_{n} < a_{n-1} \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} a_{n+1} < a_{n} \end{eqnarray*}$ folgt.

Am besten fängst du mit der linken Seite $\begin{eqnarray*} a_{n+1} \end{eqnarray*}$ an und folgerst mit geeigneten Umformungen, daß dies kleiner als a_n ist.

Im übrigen hast du a_3 falsch ausgerechnet.

01.11.2011, 11:34

Mikadobrain

Auf diesen Beitrag antworten »

Zweiter Versuch:

Annahme:
$\begin{eqnarray*} (n)\frac{2^{n}}{3^{n}} < (n-1)\frac{2^{n-1} }{3^{n-1}} \end{eqnarray*}$
äquivalent zu
$\begin{eqnarray*} \frac{n}{n-1}\cdot\frac{2^{n}}{3^{n}} < \frac{2^{n-1} }{3^{n-1}} \end{eqnarray*}$

Dann nehme ich als Schluss:
$\begin{eqnarray*} (n+1)\frac{2^{n+1} }{3^{n+1}} < (n)\frac{2^{n} }{3^{n}} \end{eqnarray*}$
äquivalent zu
$\begin{eqnarray*} \frac{n+1}{n}\cdot\frac{2^{n} }{3^{n}} < \frac{2^{n-1} }{3^{n-1}} \end{eqnarray*}$

Das fühlt sich für mich schonmal grundsätzlich gut an, denn nun unterscheidet sich der Schluss durch die Annahme nur noch im ersten Faktor der linken Seite.

Kann ich jetzt behaupten, dass
$\begin{eqnarray*} \frac{n+1}{n} < \frac{n}{n-1} \end{eqnarray*}$
womit gilt
$\begin{eqnarray*} \frac{n+1}{n} \cdot \frac{2^{n} }{3^{n}} < \frac{n}{n-1}\cdot\frac{2^{n}}{3^{n}} < \frac{2^{n-1} }{3^{n-1}} \end{eqnarray*}$
?

01.11.2011, 11:48

Huy

Auf diesen Beitrag antworten »

Du möchtest zeigen, dass die Folge $\begin{eqnarray*} \frac{n 2^n}{3^n} \end{eqnarray*}$ beschränkt ist, in deiner Induktion versuchst du allerdings strikte Monotonie zu zeigen. Mit deinem Induktionsanfang versuchst du insbesondere zu zeigen, dass $\begin{eqnarray*} a_3 > a_k \end{eqnarray*}$ für alle $\begin{eqnarray*} k > 3 \end{eqnarray*}$ ist. Das sind zwei verschiedene Dinge. Warum zeigst du nicht einfach das, was du wirklich zeigen willst?

Induktionsannahme: $\begin{eqnarray*} \forall n \in \mathbb{N}: a_n < 1 \end{eqnarray*}$
Induktionsanfang: $\begin{eqnarray*} a_1 = 2/3 < 1 \end{eqnarray*}$

Induktionsschritt: ?

MfG

01.11.2011, 11:50

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Mikadobrain
Kann ich jetzt behaupten, dass
$\begin{eqnarray*} \frac{n+1}{n} < \frac{n}{n-1} \end{eqnarray*}$

Das kann man nicht nur behaupten, sondern auch beweisen. Augenzwinkern

Im Prinzip ist der Beweis ok, es geht aber auch direkter:

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

Eine vollständige Induktion ist somit gar nicht erforderlich. Augenzwinkern

01.11.2011, 12:09

Mikadobrain

Auf diesen Beitrag antworten »

@Huy:
Streng monoton fallend muss doch beschränkt nach oben sein, oder?
Im übrigen würde ich gern direkt zeigen was ich zeigen möchte, nur am Können mangelt es Augenzwinkern

@klarsoweit:
Äh, ja. So ist das bisher immer wenn ich nach langem Überlegen den Prof. vorrechnen sehe: Ich wundere mich, warum ich mir soviel Mühe gemacht habe wenn es doch so eindeutig einfach ist : /

Danke euch beiden.
Wird nicht die letzte Frage gewesen sein...

Lg Micha

01.11.2011, 13:01

Mikadobrain

Auf diesen Beitrag antworten »

Hm, etwas ist mir nicht ganz klar, vielleicht steh ich nur extrem auf dem Schlauch. Warum ist

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

Wie kommt man darauf?
Ich seh das ja intuitiv ein, zumindest für n>2, aber genügt das in einem Beweis?

01.11.2011, 15:58

klarsoweit

Auf diesen Beitrag antworten »

Ja, wenn du die fallende Monotonie für n >= 3 zeigen willst.

01.11.2011, 16:46

Mikadobrain

Auf diesen Beitrag antworten »

Gut.

Die untere Schranke 0 sieht derzeit so aus:

$\begin{eqnarray*} a_{n+1} = (n+1)\frac{2^{n+1}}{3^{n+1}} = (n+1)(\frac{2}{3})^{n+1} > 0 \end{eqnarray*}$
weil
$\begin{eqnarray*} (n+1)_{n\in \mathbb N } >0 \end{eqnarray*}$
und
$\begin{eqnarray*} ((\frac{2}{3})^{n+1})_{n\in \mathbb N} > 0 \end{eqnarray*}$

Korrekt? Oder wieder fehlerhaft?

01.11.2011, 17:37

klarsoweit

Auf diesen Beitrag antworten »

Soweit ja, aber für einen direkten Beweis reicht es aus, wenn du a_n betrachtest.

01.11.2011, 18:13

Mikadobrain

Auf diesen Beitrag antworten »

Oh, schön

Unser Prof sagt immer man könne in der Analysis ruhig verschwenderisch sein, also was solls... n oder n+1....

Vielen Dank!

Neue Frage »

Antworten »

Beschränktheit mittels vollst. Induktion beweisen

Verwandte Themen