Monotonie Fibonacci-Folge, Ungleichung, Landau-Symbole

Aufrufe: 277     Aktiv: 06.05.2021 um 20:39

0
Ich möchte zeigen, dass die Fibonacci-Folge mit \( a_0:=1, a_1 := 1, a_n:=a_{n-1}+a_{n-2}, n>1\) monoton wachsend ist und dass für alle \( n\geq 2\) die Ungleichung \(2^{\frac{2}{n}}\leq a_n\leq2^n \) gilt.

Dass die Folge monoton wachsend ist, hab ich mit vollst. Induktion gezeigt, was ziemlich trivial war, was mich ehrlich gesagt auch ein bisschen skeptisch macht:
Ind.anfang: \( n = 0 \quad \to a_1=1 \geq 1 = a_0  \)
Ind.vss: \( \exists n\in \mathbb{N}: a_{n+1} \geq a_n \)
Ind.schritt: \( a_{n+2} = a_n + a_{n+1} \geq a_{n+1} \) 


Wie ich jedoch diese Ungleichung zeigen soll, ist mir ein Rätsel. Wir behandeln gerade Asymptotik/ Landau-Symbole und ich soll darauf Bezug nehmen. Ich habe da allerdings keinen Schimmer, wie ich das angehen soll. Hat mir jemand einen Tipp?
Diese Frage melden
gefragt

Student, Punkte: 193

 

TU Darmstadt Mathe 2 für Informatiker?   ─   koch 06.05.2021 um 20:39

Kommentar schreiben

1 Antwort
1
1.) Deine erste Induktion funktioniert so nicht. Wie hast du überhaupt deine Induktionsannahme verwendet? Wenn du deine Induktionsannahme verwendest, dann kommt daraus \( a_{n+2} = a_n + a_{n+1} \leq 2\cdot a_{n+1} \). Nur das hilft dir nicht weiter.

Ich würde das ganz stumpf machen. Nach der Ungleichung, die du sowieso zeigen musst, sind alle Fibunaccizahlen positiv, denn \( a_n \geq 2^\frac{2}{n} >0 \) (\(a_0\) und \(a_1\) sind natürlich auch positiv). Dann gilt aber auch \( a_n = a_{n-1} + \underbrace{a_{n-2}}_{>0} > a_{n-1} \) für alle \( n\geq 2\). Bleibt nurnoch ein Wort zu \(a_0\) und \(a_1\) und schon kann man sich die Induktion sparen.

2.) Die Ungleichungen \( 2^\frac{2}{n} \leq a_n\) und \(a_n \leq 2^n\) machst du am besten getrennt voneinander. Die Letztere \(a_n \leq 2^n\) ist erheblich einfacher. Mit der soltest du anfangen. Verwende für beide Induktion über \(n\). Beachte außerdem, dass du hier den Induktinsstart für 2 Werte machen musst! Nämlich für \(a_0\) und \(a_1\).
Das liegt daran, dass du auch die Induktionsannahme für die 2 letzten Werte benutzen musst \(a_{n-1}\) und \(a_{n-2}\).
Diese Antwort melden
geantwortet

Punkte: 270
 

Perfekt, das versuche ich nachher gleich mal.   ─   akimboslice 30.04.2021 um 07:08

Für das monotone Wachstum habe ich geschrieben: \( a_n \) ist monoton wachsend, denn von n=2 an werden ausschließlich positive Zahlen addiert. Somit gilt sofort:
\( a_{n+1}-a_n = a_n + a_{n-1} - a_n = a_{n-1} \geq 0 \)

Ich hab die \(a_n \leq 2^n \) gezeigt wie hier von adriano erklärt: https://math.stackexchange.com/questions/894743/proof-by-induction-nth-fibonacci-number-is-at-most-2n

Die zweite Ungleichung jedoch schaffe ich nicht. Das n/2 in der Potenz macht mir zu schaffen. Ich muss im Ind.schritt am Ende ja auf \( a_{n+1} \geq 2^{\frac{1}{2} \cdot (n+1)} \) kommen und damit bin ich überfordert.
  ─   akimboslice 30.04.2021 um 18:07

Wenn da \( \frac{n}{2} \) im Exponenten steht, habe ich gestern etwas vollkommen falsches bewiesen. In der Aufgabenstellung deiner Frage steht eindeutig \( \frac{2}{n} \).
Hier ist der Induktionsschritt. Beachte, dass du hier definitiv 2 Induktionsstarts machen musst, weil du die Ungleichung für \(a_{n-2}\) brauchst.
\[ a_n \overset{\text{Def. } a_n}{=} a_{n-1}+a_{n-2} \overset{\text{Monotonie}}{\leq} 2 \cdot a_{n-2}\overset{\text{IA}}{\leq} 2\cdot2^{\frac{n-2}{2}} = 2^{\frac{n}{2}} \]
  ─   cunni 30.04.2021 um 20:24

Jap, das geht auf meine Kappe. Es muss \( 2^{\frac{n}{2}} \) heißen. Danke für den Induktionsschritt. Damit hab ich's ja eigentlich. Darauf wär ich nicht gekommen. Ich schreibe nachher den Ind.start auf. Das ist der erste Ind.beweis, den ich mit 2 Werten mache.   ─   akimboslice 01.05.2021 um 08:17

Mich verwirrt das, dass du beim Induktionsschritt \( a_n \) nimmst und nicht \( a_{n+1} \).
Ich würde dann schreiben:
Ind.anfang:
\( n = 2 \to 2^1=2\leq 2 = a_2 \\
n=3\to 2^{\frac{3}{2}} \approx 2,82 \leq 3 = a_3 \)
Ind.vss: es gibt eine natürliche Zahl \( n \geq 2 \) mit \( 2^{\frac{n}{2}} \leq a_n \)

Und dann deinen Ind.schritt.

Das stimmt doch so aber nicht, oder?
  ─   akimboslice 01.05.2021 um 10:17

"Mich verwirrt das, dass du beim Induktionsschritt \(a_n\) nimmst und nicht \(a_{n+1}\)."
Ob man die Annahme für \(a_n\) aufstellt und für \(a_{n+1}\) beweist oder für \(a_{n-1}\) annimmt und für \(a_{n}\) beweist ist doch egal. Du kannst das gerne umschreiben.

"Ind.vss: es gibt eine natürliche Zahl \(n\geq 2\) mit \(2^\frac{n}{2}\leq a_n\)"
Wenn du dir meinen Induktionsschritt genau siehst, verwende ich die Eigenschaft vor allem für \(a_{n-2}\). Also das VORLETZTE Element. Selbst wenn ich jetzt davon ausgehe, dass du meinen Schritt umschreiben willst für \(a_{n+1}\leq 2^{\frac{n+1}{2}}\), reicht es nicht die Induktionsannahme nur für \(a_n\) zu haben. Du brauchst sie auch für \( a_{n-1} \).
Genau deswegen hast du ja auch einen doppelten Induktionsanfang gemacht. Jetzt kannst du nämlich in der Induktionsannahme sagen \(\exists n\in \mathbb{N}_{\geq3}: 2^\frac{n}{2} \leq a_n \wedge 2^\frac{n-1}{2} \leq a_{n-1} \).
  ─   cunni 01.05.2021 um 13:31

Habs jetzt endlich hinbekommen. Danke für die geduldige Hilfe.   ─   akimboslice 01.05.2021 um 17:29

Kommentar schreiben