Vollständige Induktion Rekursive Folge

Question

Ich möchte zeigen, dass eine rekursive Folge nach oben beschränkt ist.

a_n+1 = a_n(2-a_n); a₁= 1/2

Ich habe durch Einsetzen die Vermutung das gilt a_n≤1.

Darf ich beim Induktionsschritt wie folgt vorgehen

1·(2-1) = 1 ≤ 1

oder lieber

 1 ≤ 2a_n - a_n²

0 ≤ 2a_n -a_n² -1

0 ≤ -(a_n -1)²   

Comments

Du fragst:

$$a_{n+1}=1$$

Das ist doch offensichtlich falsch??

Überlege, wie Du das richtig formulieren kannst.

---

an+1 = an(2-an) a1= 1/2

Wenn Du damit meinst

a_n+1 = a_n(2 - a_n)   ;   a₁ = 1/2

dann solltest Du es auch so schreiben.

Answer 1

Als Beweis ließ folgende Umformungen rückwärts von unten nach oben:

$$a_{n+1} \le 1 \newline a_n \cdot (2 - a_n) \le 1 \newline 2 \cdot a_n - {a_n}^2 \le 1 \newline {a_n}^2 - 2 \cdot a_n \ge -1 \newline {a_n}^2 - 2 \cdot a_n + 1 \ge 0 \newline (a_n - 1)^2 \ge 0$$

Comments

Das ist doch nun wirklich eine alberner Abschrieb meiner Antwort.

---

Quatsch. Er nutzt \(a_n \) statt \(x \). Damit enthält seine Antwort mehr als genug Eigenständigkeit. ;)

---

Nein, das ist nicht überflüssig und nicht albern.

Wie soll ein verzweifelter Fragesteller darauf kommen, den anscheinend vom Himmel gefallenen Ansatz \(0 \leq (x-1)^2\) zu verwenden, welcher dann sein Problem löst?

Was MC gemacht hat ist die Beweisfindung. Man formt die Behauptung so lange um, bis man auf etwas stößt von dem man weiß, dass es stimmt. DANN kann man diesen Weg für den eigentlichen Beweis umkehren.

---

1. Ich bleibe dabei: Eine Person, die sich lernhaft mit der Analyse rekursiv definierter Folgen beschäftigt, ist in der Lage, einen einfachen Beweis rückwärts zu lesen, ohne dass ihr ein rückwärtiger Abschrieb an die Hand gegeben werden muss.

2. Die eigenen Überlegungen des FS zeigen, dass eine einfache zusammenfassende Antwort angemessen ist.

3. In seinen meisten Beiträgen erklärt MC nichts. Deine Behauptung, er wolle uns hier bei diesem nicht überkomplexen Sachverhalt die Beweisfindung erläutern, stimmt mich heiter.

Answer 2

Deine letzte Ungleichung gilt (allgemein) genau anders herum. Also: Es gilt für alle \(x \in \R\):

$$0 \leq (x-1)^2=x^2-2x+1 \Rightarrow 2x-x^2\leq 1$$

Daher gilt für alle \(n \in \N\):

$$a_{n+1}=a_n(2-a_n) \leq 1$$

Comments

Du würdest gerne zeigen, daß alle a_n beschränkt sind. Die Idee der Vollständigen Induktion ist nicht schlecht. Beim Schluß hast Du dann zu zeigen, daß

a_n+1 = a_n (2-a_n)

kleiner 1 ist. Den ersten Faktor a_n rechts könntest Du nach der Ind. Annahme durch 1 nach oben abschätzen, leider aber nicht die Klammer wegen des Minus-Zeichen. So geht es also erst mal nicht weiter.

Also muß man etwas anderes versuchen was uns zu dem Ansatz von Mathhilf bringt, den Ausdruck in ein Quadrat umzuformen (Idee: quadratische Ergänzung) da man weiß, daß Quadrate nie negativ werden.

Damit ist dann auch keine Induktion mehr erforderlich.