Fibos: Identität von d'Ocagne < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es seien [mm] $f_{n}$ [/mm] die Fibonacci-Zahlen mit [mm] $f_{0} [/mm] = 0, [mm] f_{1} [/mm] = 1, [mm] f_{2} [/mm] = 1$ und [mm] $f_{n+1} [/mm] = [mm] f_{n} [/mm] + [mm] f_{n-1}$.
[/mm]
[Dateianhang nicht öffentlich] |
Hallo!
Natürlich liegt, dachte ich mir, der Gedanke der Induktion nahe. Leider funktioniert das nicht auf Anhieb, deswegen habe ich mir noch ein paar Gedanken gemacht:
Die rechte Seite der Formel lässt sich ja praktisch "immer weiter" nach unten kürzen:
[mm] $f_{m}*f_{n+1} [/mm] - [mm] f_{n}*f_{m+1}$
[/mm]
$= [mm] f_{m}*(f_{n} [/mm] + [mm] f_{n-1}) [/mm] - [mm] f_{n}*(f_{m} [/mm] + [mm] f_{m-1})$
[/mm]
$= [mm] f_{m}*f_{n-1} [/mm] - [mm] f_{n}*f_{m-1}$
[/mm]
und dann
$= [mm] (f_{m-1} [/mm] + [mm] f_{m-2})*f_{n-1} [/mm] - [mm] (f_{n-1} [/mm] + [mm] f_{n-2})*f_{m-1}$
[/mm]
$= [mm] f_{m-2}*f_{n-1} [/mm] - [mm] f_{n-2}*f_{m-1}$
[/mm]
D.h. man kann die rechte Seite immer weiter herunterbrechen und auf die Form
$= [mm] f_{m-2*k}*f_{n+1 - 2*k} [/mm] - [mm] f_{n-2*k}*f_{m+1 - 2*k}$
[/mm]
mit [mm] $k\in \IN$. [/mm] (Das müsste man ja wahrscheinlich noch mit Induktion zeigen, fände ich aber wegen den vielen Variablen nicht so elegant...)
Betrachtet man nun den Fall $2*k = n$, (d.h. insbesondere n gerade), erhält als gesamte Formel
[mm] f_{m-n} [/mm] = [mm] f_{m-n}*f_{1} [/mm] - [mm] f_{0}*f_{m+1-n}
[/mm]
w.A., weil der rechte "Summand" 0 ist und [mm] $f_{1} [/mm] = 1$. Andererseits erhält man für $2*k-1 = n$, d.h. n ungerade die Gleichung
[mm] -f_{m-n} [/mm] = [mm] f_{m-n-1}*f_{0} [/mm] - [mm] f_{-1}*f_{m-n}
[/mm]
Das funktioniert irgendwie noch nicht so ganz...
Gibt es einen besseren Weg, die Gleichung zu zeigen? Hat jemand einen Ansatz für mich?
Danke für Eure Hilfe,
Stefan.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:22 Do 20.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:10 Do 20.11.2008 | | Autor: | reverend |
Sorry, dass ich erst jetzt antworte. Ich sah die Frage erst, als der Eintrag "Fälligkeit abgelaufen" kam. Da konnte ich aber gerade nicht...
Dein Weg ist doch klasse. Da brauchst Du m.E. auch keine Induktion.
Das Ende für ungerades n ist in der Tat unschön. Zwar könntest Du aus der Rekursionsformel [mm] f_{i+1}=f_i+f_{i-1} [/mm] ein fiktives [mm] f_{-1}=f_1-f_0=1 [/mm] errechnen, womit Du ja unmittelbar fertig wärst. Nur schön ist es nicht, mit dem negativen Index und der Erweiterung der Fibonaccifolge nach vorn. Zuviel Definitionsänderungsaufwandskollateralschaden...
Du kannst aber auch sauber enden. Einen Schritt vor Deinem letzten bist Du ja hier:
[mm] -f_{m-n}=f_{m-n+1}f_2-f_1f_{m-n+2}
[/mm]
Das lässt sich doch ganz gut umformen:
[mm] ...=(f_{m-n+1}+f_{m-n-1})(f_0+f_1)-f_1f_{m-n+2}= [/mm] einsetzen: [mm] f_0=0, f_1=1
[/mm]
[mm] =f_{m-n+1}+f_{m-n-1}-f_{m-n+2}=f_{m-n+1}+f_{m-n-1}-(f_{m-n+1}+f_{m-n})=f_{m-n-1}-f_{m-n+1}=
[/mm]
[mm] =f_{m-n-1}-(f_{m-n}+f_{m-n-1})=\blue{-f_{m-n}}
[/mm]
Das ist nicht so elegant wie bei den geraden Zahlen.
Darum ist doch anzuraten, auch das Wissen um den Wert von [mm] f_2 [/mm] mit einzusetzen: [mm] f_2=f_1=1
[/mm]
Dann bist Du schneller. Beginn der Rechnung an gleicher Stelle wie oben:
[mm] -f_{m-n}=f_{m-n+1}f_2-f_1f_{m-n+2}=f_{m-n+1}-f_{m-n+2}=f_{m-n+1}-(f_{m-n+1}+f_{m-n})=\blue{-f_{m-n}}
[/mm]
|
|
|
| |
|
Hallo reverend,
danke für deine Antwort! Nachdem ich gemerkt hatte dass das etwas unsauber war mit den geraden Zahlen, habe ich es noch etwas anders geschrieben:
[Dateianhang nicht öffentlich]
Ist das okay so?
Stefan.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:53 Do 20.11.2008 | | Autor: | reverend |
...hat wahrscheinlich irgendwas beim Hochladen nicht geklappt.
|
|
|
| |
|
Hallo!
Genau, ich hatte das Bild noch nicht mal hochgeladen 
Stefan.
|
|
|
| |
|
Das ist nicht nur ok, sondern sehr schön.
Wofür brauchst Du das in solcher Reinschrift? Schreibst Du gerade an einem Lehrbuch? 
|
|
|
| |
|
Hallo!
Nein, das war für eine Hausaufgabe
Stefan.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:06 Di 19.05.2009 | | Autor: | abakus |
> Hallo!
>
> Nein, das war für eine Hausaufgabe
>
> Stefan.
Hallo Steppenhahn,
wenn die Wahl deiner Hilfsmittel nicht eingeschränkt ist, könntest du auch mit der expliziten Darstellung der Fibo-Folge arbeiten.
Gruß Abakus
|
|
|
| |
|
> Hallo Steppenhahn,
> wenn die Wahl deiner Hilfsmittel nicht eingeschränkt ist,
> könntest du auch mit der expliziten Darstellung der
> Fibo-Folge arbeiten.
> Gruß Abakus
>
Hallo Abakus,
könnte es sein, daß sich Deine Mitteilung in Wirklichkeit auf einen andern Beitrag in dieser Diskussion bezieht ?
Aber ob das hier mit der Formel von Binnet so viel einfacher ist ...
Gruß
zahlenspieler
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 So 24.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hallo Stefan,
> Es seien [mm]f_{n}[/mm] die Fibonacci-Zahlen mit [mm]f_{0} = 0, f_{1} = 1, f_{2} = 1[/mm]
> und [mm]f_{n+1} = f_{n} + f_{n-1}[/mm].
>
> [Dateianhang nicht öffentlich]
Es sei [mm]D:=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}[/mm].
Dann gilt für alle [mm] n \in \IN[/mm]:
[mm]D^n=\begin{pmatrix} f_{n+1} & f_n\\ f_n & f_{n-1} \end{pmatrix} [/mm].
Beweis: Es ist [mm] \begin{pmatrix} f_2 & f_1 \\ f_1 & f_0 \end{pmatrix} =\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} =D^1[/mm].
Annahme: Für [mm]n \in \IN[/mm] gelte [mm]D^n=\begin{pmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{pmatrix} [/mm]. Durch Multiplikation mit [mm]D[/mm] erhält man:
[mm]\begin{matrix} D^{n+1} &= \begin{pmatrix} f_{n+1} +f_n & f_n +f_{n-1} \\ f_n+1} & f_n \end{pmatrix} \\ &=
\begin{pmatrix} f_{n+2} & f_{n+1} \\ f_{n+1} & f_n \end{pmatrix} \end{matrix}[/mm].
[mm]\qedsymbol[/mm]
Behauptung: Für [mm]n
[mm]f_m*f_{n+1} -f_{m+1}*f_n =(-1)^n*f_{m-n}[/mm].
Beweis. Da [mm]\det{D}=-1[/mm], erhält man für [mm]n \in \IN[/mm]:
[mm] D^{-n} =(D^n)^{-1} =(-1)^n \cdot \begin{pmatrix} f_{n-1} & -f_n \\ -f_n & f_{n+1}\end{pmatrix}[/mm]. Durch Vergleich an Position (2,1) der Matrizen [mm] D^{-n} \cdot D^m[/mm] und [mm] D^{m-n[/mm]:
[mm] f_{n-m}=(-1)^n*(-f_n*f_{m+1} +f_{n+1}*f_m)[/mm], und durch Multiplizieren mit [mm](-1)^n[/mm] die Behauptung.
[mm]\qedsymbol[/mm]
Gruß
zahlenspieler
|
|
|
|
