Fibonacci-Potenzreihe [ehemals: "Summe aus Quotient < 2"]

05.11.2005, 21:22	Wurzel3	Auf diesen Beitrag antworten »
Fibonacci-Potenzreihe [ehemals: "Summe aus Quotient < 2"] Hallo! An folgender Aufgabe bin ich gerade am Verzweifeln: Zeige: $\begin{eqnarray} f_k \end{eqnarray}$ ist die k-te Fibonacci-Zahl. $\begin{eqnarray} \sum^n_{k=1} \frac{f_k}{2^k} < 2 \forall n \in N \end{eqnarray}$ Ich habe schon diverses ausprobiert. Nun frage ich euch, was ihr für den vielversprechendsten Ansatz haltet: 1) Vollständige Induktion. Da komme ich nicht weiter, weil da ja eine Ungleichung steht. Außerdem habe ich keine Ahnung, wie ich die Fibonacci-Zahlen da reinbringen soll. 2) Auflösen. Ich habe schon mal den Bruch in der Summe beseitigen können, indem ich auf 2^n erweitert habe. Dann kann man das 2^n aus der Summe herausziehen. Das hilft mir aber auch nicht wirklich, weil ich auch mit einem Produkt in der Summe nicht viel anfangen kann, zumal da dann auchnoch die Fibonaccis drinstehen. 3) Irgendwie anders... Da habe ich auch noch nicht so wirklich eine Idee. Würde vielleicht ein indirekter Beweis klappen? Alles in allem komme ich eigentlich nur deshalb nicht weiter, weil ich die Fibonaccis nicht in geschlossener Form darstellen kann und ich das ja benötigen würde. Da wir in der Vorlesung aber noch nicht bewiesen haben, dass man die geschlossen darstellen kann (das geht irgenwie im Zusammenhang mit einer Gaußklammer, oder?), kann ich das ja nicht verwenden. Vielen Dank für eventuelle Hilfe (wenn sie schnell genug kommt), ich muss das übermorgen abgeben ;-) Christoph
05.11.2005, 22:21	Sciencefreak	Auf diesen Beitrag antworten »
So schlimm ist die expliziete Bildungsvorschrift für die Fibonaccizahlen doch auch wieder nicht. Und sie geht sogar wunderbar leicht herzuleiten. $\begin{eqnarray} f_n=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \end{eqnarray}$ Edit: Habe heute den ganzen Tag in Latex geschrieben, da klappt das mit den $-Zeichen besser als hier
05.11.2005, 23:31	AD	Auf diesen Beitrag antworten »
Warum nicht die Sache so angehen: Sei $\begin{eqnarray} a_n := \sum_{k=1}^n ~ \frac{f_k}{2^k} \end{eqnarray}$ . Dann folgt mit $\begin{eqnarray} f_0=0,f_1=1 \end{eqnarray}$ und $\begin{eqnarray} f_k = f_{k-1}+f_{k-2} \end{eqnarray}$ : $\begin{eqnarray} a_n = \frac{1}{2} + \sum_{k=2}^n ~ \frac{f_{k-1}+f_{k-2}}{2^k} = \frac{1}{2} + \frac{1}{2}\sum_{j=1}^{n-1} ~ \frac{f_j}{2^j} + \frac{1}{4}\sum_{i=0}^{n-2} ~ \frac{f_i}{2^i} = \frac{1}{2} + \frac{a_{n-1}}{2} + \frac{a_{n-2}}{4} \end{eqnarray}$ (Indexverschiebung $\begin{eqnarray} j=k-1 \end{eqnarray}$ und $\begin{eqnarray} i=k-2 \end{eqnarray}$ ). Bis zur geforderten Ungleichung ist es jetzt nur noch ein kleiner Schritt, wenn man an die Monotonie von $\begin{eqnarray} (a_n) \end{eqnarray}$ denkt...
06.11.2005, 13:07	Wurzel3	Auf diesen Beitrag antworten »
Danke Danke! Auf den ersten Blick versteh ich zwar nur Bahnhof, aber ich gucks mir nachher noch mal genauer an... Danke... Christoph
06.11.2005, 20:46	Wurzel3	Auf diesen Beitrag antworten »
Hallo nochmal! (@Arthur Dent) Ich habe deinen Ansatz heute mal durchdacht... komme aber leider nicht wirklich weiter. Folgendes ist mein Problem: Wenn ich dein "Schlusswort" nehme und einfach mal in meine Ungleichung einsetze: $\begin{eqnarray} a_{n-q}+a_{n-2} < 3 \end{eqnarray}$ Das hilft mir aber reichlich wenig, da ich dann ja das gleiche Problem wie vorher habe. Also habe ich probiert, herauszufinden, wie denn die Summe zweier nachfolgender Elemente von $\begin{eqnarray} a_n \end{eqnarray}$ sich vereinfachen lassen. Dabei komme ich dann auf: $\begin{eqnarray} \sum_{k=1}^n \frac{f_k}{2^k} + \sum_{k=1}^{n+1} \frac{f_k}{2^k} = 2 \cdot \sum_{k=1}^n \frac{f_n}{2^k} + \frac{f_{n+1}}{2{n+1}} \end{eqnarray}$ Der zweite Teil der Summe ist auf jedenfall kleiner als 1, da ja jede Fibonacci-Zahl kleiner als die entsprechende 2er-Potenz ist. Klar. Aber so komme ich auch nicht weiter, da ich jetzt ja das gleiche Problem wie am Anfang habe. Dann habe ich folgendes probiert: Ich habe versucht, $\begin{eqnarray} a_n \end{eqnarray}$ und den von dir am Ende vorgeschlagenen Term irgendwie so zu kombinieren, dass es hinkommt. Leider hat das jedoch auch nocht geklappt... Ich bin reichlich ratlos. Kannst du mir noch einen klitzekleinen Tipp geben, wie du das meintest? Danke, Christoph
06.11.2005, 20:59	AD	Auf diesen Beitrag antworten »
$\begin{eqnarray} (a_n) \end{eqnarray}$ ist streng monoton wachsend, da für wachsendes n immer nur positive Summanden zur Summe hinzukommen. Also kann ich meine letzte Gleichung folgendermaßen nach oben abschätzen: $\begin{eqnarray} a_n = \frac{1}{2} + \frac{a_{n-1}}{2} + \frac{a_{n-2}}{4} < \frac{1}{2} + \frac{a_n}{2} + \frac{a_n}{4} = \frac{1}{2} + \frac{3}{4}a_n \end{eqnarray}$ Und wie man $\begin{eqnarray} a_n <\frac{1}{2} + \frac{3}{4}a_n \end{eqnarray}$ nach $\begin{eqnarray} a_n \end{eqnarray}$ umstellt, sollte selbst ein Blinder sehen.
Anzeige

06.11.2005, 23:03	Wurzel3	Auf diesen Beitrag antworten »
Hallo! Danke nochmal für die ausführliche Hilfe. Jetzt habe ich es kapiert... Irgendwie war ich da wohl so vernagelt, dass ich nicht auf die Idee gekommen bin, das Summandenweise zu machen. Christoph

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »