Fibonacci-Beweis < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:02 Mo 11.02.2013 | | Autor: | Diophant |
| Aufgabe | Sei durch [mm] F_0=0, F_1=F_2=1 [/mm] sowie [mm] F_{n+2}=F_{n+1}+F_n [/mm] die Fibonacci-Folge gegeben.
Man zeige:
[mm]\summe_{i=0}^{n}\vektor{n \\
i}F_i=F_{2n} [/mm] |
Hallo zusammen,
an dieser Aufgabe tue ich mich schwer. Als Hinweis steht noch dabei, dass die Binet'sche Darstellung verwendet werden soll.
Meine Frage wäre zunächst einmal einfach die folgende: ich versuche das jetzt seit Tagen direkt zu zeigen. Kennt vielleicht jemand diese Aufgabe und kann mir sagen, ob ich es vielleicht besser mit vollständiger Induktion versuchen sollte als direkt?
Ich würde die Aufgabe dann gerne hier diskutieren, aber zunächst möchte ich gerne wissen, in welche Richtung das hier geht, also direkter Beweis durch Nachrechnen (wobei sich für mich bis jetzt unüberwindbare Summen mit Binomialkoeffizienten multipliziert mit ungeraden Potenzen von [mm] \wurzel{5} [/mm] ergeben) oder aber doch ein Beweis durch vollständige Induktion?
Falls also jemand die Aufgabe kennt oder eine zündende Idee hat: vielen Dank im Voraus für jede Antwort!
Gruß, Diophant
PS: Die Aufgabe stammt aus Walter, Wolfgang: Analysis 1, eines meiner absoluten Lieblingsbücher. 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:52 Mo 11.02.2013 | | Autor: | Helbig |
> Sei durch [mm]F_0=0, F_1=F_2=1[/mm] sowie [mm]F_{n+2}=F_{n+1}+F_n[/mm] die
> Fibonacci-Folge gegeben.
>
> Man zeige:
>
> [mm]\summe_{i=0}^{n}\vektor{n \\
i}F_i=F_{2n}[/mm]
>
>
>
> Hallo zusammen,
>
> an dieser Aufgabe tue ich mich schwer. Als Hinweis steht
> noch dabei, dass die Binet'sche Darstellung verwendet
> werden soll.
>
> Meine Frage wäre zunächst einmal einfach die folgende:
> ich versuche das jetzt seit Tagen direkt zu zeigen. Kennt
> vielleicht jemand diese Aufgabe und kann mir sagen, ob ich
> es vielleicht besser mit vollständiger Induktion versuchen
> sollte als direkt?
>
> Ich würde die Aufgabe dann gerne hier diskutieren, aber
> zunächst möchte ich gerne wissen, in welche Richtung das
> hier geht, also direkter Beweis durch Nachrechnen (wobei
> sich für mich bis jetzt unüberwindbare Summen mit
> Binomialkoeffizienten multipliziert mit ungeraden Potenzen
> von [mm]\wurzel{5}[/mm] ergeben) oder aber doch ein Beweis durch
> vollständige Induktion?
Hallo Diophant,
nach Binet ist
[mm] $F_n={\lambda^n - \mu^n \over \lambda -\mu}\,,$
[/mm]
wobei [mm] $\lambda$ [/mm] und [mm] \mu$ [/mm] die beiden Nullstellen von [mm] $x^2-x-1$ [/mm] sind. Für jede dieser Nullstellen x ist
[mm] $\sum_{i=0}^n{n\choose i} x^i [/mm] = [mm] (x+1)^n [/mm] = [mm] \left(x^2\right)^n [/mm] = [mm] x^{2n}\,.$
[/mm]
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:01 Mo 11.02.2013 | | Autor: | Diophant |
Hallo Wolfgang,
> nach Binet ist
>
> [mm]F_n={\lambda^n - \mu^n \over \lambda -\mu}\,,[/mm]
>
> wobei [mm]\lambda[/mm][/mm] und [mm]\mu$[/mm] die beiden Nullstellen von
> [mm]x^2-x-1[/mm][/mm] sind.
Ok, das war das entscheidende Detail, welches ich versäumt habe, in meine Überlegungen mit einzubeziehen.
> Für jede dieser Nullstellen x ist
>
> [mm]\sum_{i=0}^n{n\choose i} x^i = (x+1)^n = \left(x^2\right)^n = x^{2n}\,.[/mm]
>
Man muss kurz über die zweite Gleichheit nachdenken, aber wirklich nur kurz. Damit hast du mir netterweise die komplette Aufgabe gelöst, was eine weitere Diskussion erübrigt.
Ansonsten: mal wieder eine äußerst elegenate Lösung von dir zu einer Analysis-Aufgabe. Aber das ist bei diesen Walter-Aufgaben für mein Gefühl immer mal wieder der tiefere Sinn: mehrere angesprochene Sachverhalte durch gedankliches Herumspielen zu verbinden, so dass eine zunächst schwierig erscheinende Aufgabenstellung zum Einzeiler wird, so wie hier.
Vielen Dank!
Grüße&schönen Abend, Johannes aka Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:54 Mo 11.02.2013 | | Autor: | kaju35 |
Hallo Diophant,
Du hast geschrieben, dass sich eine weitere Diskussion erübrigt.
Ich will Dir auch nicht auf die Nerven gehen oder so. Aber
ich habe einen alternativen Ansatz, den Du Dir, wenn Du magst
mal durchlesen kannst!
Ich habe mal ganz naiv angefangen mit der Identität [mm] $F_{2n}=F_{2n}$ [/mm]
Das ist
[mm] $=F_{2n}$
[/mm]
[mm] $=F_{2n-1}+F_{2n-2}$
[/mm]
[mm] $=F_{2n-2}+F_{2n-3}+F_{2n-3}+F_{2n-4}=F_{2n-2}+2\cdot F_{2n-3}+F_{2n-4}$
[/mm]
[mm] $=F_{2n-3}+F_{2n-4}+2\cdot (F_{2n-4}+F_{2n-5})+F_{2n-5}+F_{2n-6}
[/mm]
[mm] $=F_{2n-3}+3\cdot F_{2n-4}+3\cdot F_{2n-5}+F_{2n-6}
[/mm]
Das ergibt allgemein die Formel
[mm] $F_{2n}=\sum_{j=0}^k\binom{k}{j}F_{2n-k-j}$
[/mm]
Das heisst, der Ko-Effizient von [mm] $F_{2n-k-j}$ [/mm] ist [mm] $\binom{k}{j}$
[/mm]
Gehen wir nun eine Zeile im Pascalschen Dreieck nach unten :
Da ist der Ko-Effizient von [mm] $F_{2n-(k+1)-j}$ [/mm] gegeben durch
[mm] $\binom{k}{j-1}+\binom{k}{j}=\binom{k+1}{j}$
[/mm]
Die Formel für die Summe lautet dort :
[mm] $F_{2n}=\sum_{j=0}^{k+1}\binom{k+1}{j}F_{2n-(k+1)-j}$
[/mm]
Und im Endeffekt kommen wir dann per Induktion zu
[mm] $F_{2n}=\sum_{j=0}^n\binom{n}{j}F_{n-j}$
[/mm]
Gruß
Kai
|
|
|
|
