Induktion reelle Folge, rekursiv definiert

12.06.2020, 20:06

KonverDiv

Auf diesen Beitrag antworten »

Induktion reelle Folge, rekursiv definiert

Eine reelle Folge ist rekursiv definiert durch:
$\begin{eqnarray*} a_1 = 0 \end{eqnarray*}$
$\begin{eqnarray*} a_{n+1} = 1-\frac{1}{2+a_n} \end{eqnarray*}$
Durch vollständige Induktion ist nun $\begin{eqnarray*} 0 \leq a_n \leq a_{n+1} \end{eqnarray*}$ zu zeigen.

Mein Ansatz:

Induktionsanfang:
$\begin{eqnarray*} n = 1 \end{eqnarray*}$
$\begin{eqnarray*} a_1 = 0, a_2 = 1 - \frac{1}{2+a_1} = 1 - \frac{1}{2+0} = \frac{1}{2} \end{eqnarray*}$

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

Induktionsvoraussetzung:
Die Behauptung gelte für ein beliebiges $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$

Induktionsschritt: $\begin{eqnarray*} n+1 \end{eqnarray*}$
$\begin{eqnarray*} 0 \leq a_{n+1} \leq a_{n+2} \end{eqnarray*}$
$\begin{eqnarray*} a_{n+2} \geq a_{n+1} \geq 0 \end{eqnarray*}$
$\begin{eqnarray*} a_{n+2} = 1 - \frac{1}{2+a_{n+1}} \geq \underbrace{1-\frac{1}{2+a_n}}_{a_{n+1}} \geq 0 \end{eqnarray*}$

Beim Induktionschritt bin ich mir nicht sicher, ob das so reicht. Vielleicht müsste man das Wissen aus dem Induktionsanfang noch irgendwie berücksichtigen. Beim letzten Teil würde ich vllt noch etwas in der Art von: $\begin{eqnarray*} 1- \frac{1}{2} = \frac{1}{2} \geq 0 \end{eqnarray*}$ einbauen (hier fehlt mir aber die Intuition/Begründung ob das so geht, nur weil es in der IA so gemacht wurde...)

Mich würden eure Verbesserungen hinsichtlich des Beweises interessieren! smile

smile

Danke

smile

13.06.2020, 16:28

HAL 9000

Auf diesen Beitrag antworten »

Bei deinem Induktionsschritt geht es mir wie so oft, wenn ich derart reine "Formelansammlungen" lese:

Formt er nun gerade nur die Induktionsbehauptung $\begin{eqnarray*} a_{n+2}\geq a_{n+1} \end{eqnarray*}$ äquivalent um, oder soll das wirklich schon der Beweis mit Hilfe der Induktionsvoraussetzung $\begin{eqnarray*} a_{n+1}\geq a_n \end{eqnarray*}$ sein? Kommt mangels Erläuterung nicht sehr deutlich rüber.

13.06.2020, 18:23

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Kommt mangels Erläuterung nicht sehr deutlich rüber.

Vielen ist das nicht klar, daß Mathematik erst entsteht, wenn Formeln durch Text miteinander in Verbindung gebracht werden.

Übrigens interessant: Mit der Fibonacci-Folge $\begin{align*} \left( f_0,f_1,f_2,f_3,\ldots \right) = \left(0,1,1,2,\ldots \right) \end{align*}$ gilt

$\begin{align*} a_n = \frac{f_{2n-2}}{f_{2n-1}} \end{align*}$

(per unvollständiger Induktion)

13.06.2020, 18:29

KonverDiv

Auf diesen Beitrag antworten »

Ok, was ich gemacht habe ist Folgendes ich habe in den Ausdruck $\begin{eqnarray*} 0 \leq a_n \leq a_{n+1}, n \end{eqnarray*}$ ersetzt mit $\begin{eqnarray*} n+1 \end{eqnarray*}$ und dann umgestellt.

13.06.2020, 18:41

HAL 9000

Auf diesen Beitrag antworten »

Ok, also ersteres von meiner Vermutung: Du hast die Iterationsgleichung in die Induktionsbehauptung eingesetzt und bist damit bei

$\begin{eqnarray*} 1 - \frac{1}{2+a_{n+1}} \geq 1-\frac{1}{2+a_n} \end{eqnarray*}$

angelangt. Eine solche Umformung (bzw. bisher ist es ja sogar nur Einsetzen) ist doch aber kein Beweis, dass diese Ungleichung auch tatsächlich gilt! Was also ist dein Plan? verwirrt

verwirrt

13.06.2020, 19:20

KonverDiv

Auf diesen Beitrag antworten »

Richtig, ich müsste irgendwie die Induktionsvoraussetzung noch mit einbringen, da fehlt mir aber die Idee, wie dies geschehen könnte.

Anzeige

14.06.2020, 10:44

klarsoweit

Auf diesen Beitrag antworten »

Wie immer hilft das Sortieren von "was ist gegeben?" und "was ist zu zeigen?" In diesem Fall haben wir im Induktionsschritt:

Gegeben: $\begin{eqnarray*} a_n \leq a_{n+1} \end{eqnarray*}$

Zu zeigen: $\begin{eqnarray*} a_{n+1} \leq a_{n+2} \end{eqnarray*}$

14.06.2020, 10:50

KonverDiv

Auf diesen Beitrag antworten »

Guten Morgen klarsoweit,

könnte ich dann nicht meine Rechnung aus meinem ersten Beitrag so stehen lassen und sagen, dass diese unter der Induktionsvoraussetzung gilt?

14.06.2020, 11:01

klarsoweit

Auf diesen Beitrag antworten »

Deine Rechnung im Induktionsschritt ist prinzipiell ok. Ein Hinweis, warum die Ungleichung gilt, hilft dem Leser beim Nachvollziehen der Schritte Nicht die Formeln sind das Wichtigste, sondern die Kommentare.

Ich würde auch empfehlen, einen separaten Beweis für a_n >= 0 zu machen.

14.06.2020, 11:14

KonverDiv

Auf diesen Beitrag antworten »

Danke für deine Antwort,

Meinen oberen Beitrag hätte ich vielleicht noch in diese Richtung erweitert, da ich so die Induktionsvoraussetzung noch aufgreife (hoffentlich auch richtig smile

smile

)
$\begin{eqnarray*} a_{n+2} = 1 - \frac{1}{2+a_{n+1}} \geq \underbrace{1-\frac{1}{2+a_n}}_{a_{n+1}} \overbrace{\geq}^{\text{nach IV}} \underbrace{1 - \frac{1}{2+a_1} = 1 - \frac{1}{2+0} = \frac{1}{2}}_{a_2} \geq \underbrace{0}_{a_1} \geq 0 \end{eqnarray*}$

Du sagtest du würdest noch einen Beweis für $\begin{eqnarray*} a_n\geq 0 \end{eqnarray*}$ zu machen. Ich habe hier gerade keine Idee, wie man diese anstellen könnte, kannst du mir weiterhelfen?

14.06.2020, 11:34

klarsoweit

Auf diesen Beitrag antworten »

Eher so:

$\begin{eqnarray*} a_{n+2} = 1 - \frac{1}{2+a_{n+1}} \overbrace{\geq}^{\text{nach IV}} 1 - \frac{1}{2+a_n} = a_{n+1} \end{eqnarray*}$

Für $\begin{eqnarray*} a_n\geq 0 \end{eqnarray*}$ machst du auch wieder Induktionsanfang und Induktionsschritt.

14.06.2020, 11:49

KonverDiv

Auf diesen Beitrag antworten »

Ok, das würde ich dann in etwa so machen:

Behauptung: $\begin{eqnarray*} a_n \geq 0 \end{eqnarray*}$
IA: $\begin{eqnarray*} n = 0,\quad a_0 = 0 \geq 0 \end{eqnarray*}$
IV: Behauptung gelte für $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$
IS: $\begin{eqnarray*} n+1 \end{eqnarray*}$
$\begin{eqnarray*} a_{n+1} \geq 0 \end{eqnarray*}$
$\begin{eqnarray*} 1 - 1/(2+a_n) \geq 0 \end{eqnarray*}$ (müsste dann ja nach der IV auch gelten, oder bedarf es hier einer Grenzwertbetrachtung?)

14.06.2020, 12:11

klarsoweit

Auf diesen Beitrag antworten »

Ich würde es vielleicht etwas deutlicher rausstellen.

Mit IV gilt: $\begin{eqnarray*} \frac{1}{2+a_n} \leq \frac 1 2 \end{eqnarray*}$ . Das kannst du dann im Induktionsschritt verwenden.

14.06.2020, 12:15

KonverDiv

Auf diesen Beitrag antworten »

Wobei noch eine Anmerkung, wie kommst du auf $\begin{eqnarray*} \frac{1}{2+a_n} \leq \frac 1 2 \end{eqnarray*}$

Ich nehme an du hast:

$\begin{eqnarray*} 1 - \frac{1}{2+a_n} = a_{n+1} \geq \frac 1 2 \end{eqnarray*}$

$\begin{eqnarray*} - \frac{1}{2+a_n} = a_{n+1} \geq -\frac 1 2 \end{eqnarray*}$

$\begin{eqnarray*} \frac{1}{2+a_n} = a_{n+1} \leq \frac 1 2 \end{eqnarray*}$

angewendet (aus dem oberen Teil, oder?)

14.06.2020, 12:57

HAL 9000

Auf diesen Beitrag antworten »

Alternativ kann man auch alles auf einen Bruchstrich bringen: Der Darstellung $\begin{eqnarray*} a_{n+1} = \frac{1+a_n}{2+a_n} \end{eqnarray*}$ sieht man unmittelbar an, dass aus $\begin{eqnarray*} a_n\geq 0 \end{eqnarray*}$ auch $\begin{eqnarray*} a_{n+1}\geq 0 \end{eqnarray*}$ folgt.

14.06.2020, 13:03

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von KonverDiv
Wobei noch eine Anmerkung, wie kommst du auf $\begin{eqnarray*} \frac{1}{2+a_n} \leq \frac 1 2 \end{eqnarray*}$

Wie ich schon sagte, folgt das direkt aus der IV. Etwa so:
$\begin{eqnarray*} a_n \geq 0 \Rightarrow 2+ a_n \geq 2 \end{eqnarray*}$

Kehrwert bilden und fertig. smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »