Folgen (Fibonacci)

07.10.2009, 17:03

mützenlisa

Folgen (Fibonacci)

Hallo zusammen!

Aufgabenstellung:
die Fibonacci-Zahlen $\begin{eqnarray*} a_n \end{eqnarray*}$ , mit $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ , sind rekursiv definiert durch

$\begin{eqnarray*} a_0 = 1, a_1 = 1, a_n+_1 = a_n-_1 + a_n, n \geq 1 \end{eqnarray*}$

Zeige, dass für alle $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ gilt:

$\begin{eqnarray*} n \leq a_n \leq 2^{n} \end{eqnarray*}$

ich habe versucht, die Aufgabe mittels Induktion zu lösen.. drehe mich aber immer wieder im Kreis.
könnte mir jemand einen Anstoss geben, mit welchem Verfahren die Aufgabe zu bewältigen wäre?

vielen lieben Dank!

07.10.2009, 17:07

kiste

Auf diesen Beitrag antworten »

Ja, Induktion geht doch hier mehr als einfach durch.
Präsentiere einmal deine Versuche

07.10.2009, 17:10

mützenlisa

Auf diesen Beitrag antworten »

$\begin{eqnarray*} n \leq a_n-_1 \leq 2^{n} \Rightarrow n+1 \leq a_n + a_n+_1 \leq 2 \cdot 2^{n} \end{eqnarray*}$

..und dann müsste ich doch $\begin{eqnarray*} a_n + a_n+_1 \end{eqnarray*}$ so umformen, dass wieder $\begin{eqnarray*} a_n-_1 \end{eqnarray*}$ vorkommt, oder nicht?

07.10.2009, 17:15

kiste

Auf diesen Beitrag antworten »

Ah das hat gefehlt. Wir machen hier nicht die normale Induktion wo wir n-1 auf n betrachten, sondern wir machen hier einen Spezialfall der noetherschen Induktion(hört sich jetzt kompliziert an, ist es aber nicht).
Speziell heißt das:
Wir können sowohl für $\begin{eqnarray*} a_{n-1} \end{eqnarray*}$ als auch für $\begin{eqnarray*} a_n \end{eqnarray*}$ die Induktionsvorraussetzung annehmen und dann den Schluss für n+1 zu machen.

Einfacher zu notieren wird es sicherlich wenn du seperat $\begin{eqnarray*} n \leq a_n \end{eqnarray*}$ und $\begin{eqnarray*} a_n \leq 2^n \end{eqnarray*}$ zeigst.

07.10.2009, 17:20

mützenlisa

Auf diesen Beitrag antworten »

das ging mir jetzt ein wenig zu schnell.. sorry.. Hammer

also was du in der letzten Zeile notiert hast, die "Aufteilung" .. erscheint mir logisch. smile

aber wie die Induktion durchgeführt werden muss, mh.. wahrscheinlich ist der Name dieser "speziellen Induktion" ein wenig verwirrend.. und ich bin schon ein wenig durcheinander, da ich seit morgens hinter der ach so wundervollen Mathe sitz.. hehe

sorry!
aber kannst du mir das schnell ansatzweise erläutern? wäre lieb!

07.10.2009, 17:27

kiste

Auf diesen Beitrag antworten »

Grob heißt das jetzt:
-Induktionsanfang für a_0 und a_1
-Im Induktionsschritt anfangen mit
$\begin{eqnarray*} a_{n+1} = a_n + a_{n-1} \end{eqnarray*}$ und dann den Term jeweils nach unten und nach oben laut Induktionsvorraussetzung abschätzen!

07.10.2009, 17:30

mützenlisa

Auf diesen Beitrag antworten »

ah okay - jetzt ist klar!
vielen lieben dank!

07.10.2009, 17:38

kiste

Auf diesen Beitrag antworten »

Du kannst deine Lösung ja dann präsentieren smile

07.10.2009, 17:48

mahtli

Auf diesen Beitrag antworten »

wäre sehr lieb, denn ich habe dasselbe problem mit derselben aufgabe und schnalle trotzdem nicht wie der induktionsschritt beginnen soll.

muss man die erste ungleichung setzen und dann dort für \left[a\right]_{n+1} die rekursive definition einsetzen?

07.10.2009, 17:49

mahtli

Auf diesen Beitrag antworten »

sorry ich hab den formeleditor noch nicht im griff :P

ich meine a n+1 mit der unlesbaren formel

07.10.2009, 17:53

mützenlisa

Auf diesen Beitrag antworten »

ah - jetzt war ich glaubs ein wenig vorlaut .. geschockt

ich kriege dann im Induktionsschritt

$\begin{eqnarray*} n+1 \leq a_n + a_n-_1 \end{eqnarray*}$

sowie

$\begin{eqnarray*} a_n \leq 2\cdot 2^{n} \end{eqnarray*}$

das führt mich doch nicht zum eigentlichen Beweis, dass die vorgegebenen Beziehungen gültig sind?

07.10.2009, 21:13

kiste

Auf diesen Beitrag antworten »

Nein, du "beweist" falsch rum. Du sollst nicht mit der zu beweisenden Aussage anfangen.

Machen wir nur mal die Abschätzung nach oben:
$\begin{eqnarray*} a_{n+1} = a_n + a_{n-1} \leq \text{hier kommt die Abschaetzung nach Induktion von } a_n \text{ hin} + \text{hier kommt die Abschaetzung nach Induktion von } a_{n-1} \text{ hin} \end{eqnarray*}$

08.10.2009, 09:39

O. Becker

Auf diesen Beitrag antworten »

RE: Folgen (Fibonacci)

Zitat:

Original von mützenlisa
Hallo zusammen!

Aufgabenstellung:
die Fibonacci-Zahlen $\begin{eqnarray*} a_n \end{eqnarray*}$ , mit $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ , sind rekursiv definiert durch

$\begin{eqnarray*} a_0 = 1, a_1 = 1, a_n+_1 = a_n-_1 + a_n, n \geq 1 \end{eqnarray*}$

Zeige, dass für alle $\begin{eqnarray*} n \in \mathbb N_0 \end{eqnarray*}$ gilt:

$\begin{eqnarray*} n \leq a_n \leq 2^{n} \end{eqnarray*}$

ich habe versucht, die Aufgabe mittels Induktion zu lösen.. drehe mich aber immer wieder im Kreis.
könnte mir jemand einen Anstoss geben, mit welchem Verfahren die Aufgabe zu bewältigen wäre?

vielen lieben Dank!

Recht einfach geht's auch wenn Du zunächst zeigst, dass die Folge monoton wächst. Dann gilt:

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

$\begin{eqnarray*} a_n\geq 1 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$

womit sich die Induktionsbeweise für die zu zeigenden Schranken in einer Zeile abhandeln lassen.

Neue Frage »

Antworten »

Folgen (Fibonacci)

Verwandte Themen