(Twitter)
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}\).
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
Link
geantwortet
cunni
Punkte: 705
Punkte: 705
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
\( 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
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
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
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