Fibonacci-Zahlen |
| 30.06.2004, 17:28 | Gast | Auf diesen Beitrag antworten » |
| Fibonacci-Zahlen Weiß zwar nicht, ob ich hier im richtigen Themengebiet bin, aber vielleicht kann mir ja trotzdem jemand helfen. Soll nämlich folgendes beweisen und hab keine Ahnung, wie ich da am besten ran gehe: Zeige, dass die Fibonacci-Zahl f_n modulo f_n+1 invertierbar ist und gib die Inverse an. Wäre super lieb, wenn mir jemand helfen könnte! DANKE MfG Katrin |
||
| 30.06.2004, 18:54 | SirJective | Auf diesen Beitrag antworten » |
Welches Kriterium für die Invertierbarkeit einer Zahl a modulo einer Zahl m kennst du denn schon? Ein Kriterium ist, dass a und m teilerfremd sind. Kennst du dieses? Wenn ja, dann musst du nachweisen, dass f_n und f_(n+1) teilerfremd sind. |
||
| 01.07.2004, 17:25 | Gast | Auf diesen Beitrag antworten » |
@ SirJective Ja, dieses Kriterium kann als bekannt vorausgesetzt werden, nur was bringt es mir, wenn ich zeige, dass f_n und f_(n+1) teilerfremd sind?? Versteh ich net so ganz 
Kannst du das vielleicht noch etwas genauer aufschlüsseln?? Wäre super lieb! MfG Katrin |
||
| 01.07.2004, 18:01 | Irrlicht | Auf diesen Beitrag antworten » |
Sei p ein gemeinsamer Teiler von f_n und f_{n-1}. Wegen f_{n-2} = f_{n} - f _{n-1} ist p dann auch ein Teiler von f_{n-2}. und so weiter... Man erhält, dass p ein Teiler von f_1 = 1 sein muss. Damit ist bewiesen, dass f_n und f_{n-1} teilerfremd sind. Du könntest das auch sehen, indem du dir klarmachst, dass die Zeilen f_{n} = f_{n-1} + f_{n-2} f_{n-1} = f_{n-2} + f_{n-3} f_{n-2} = f_{n-3} + f_{n-4} . . . f_{2} = f_{1} + f_{0} = 1 + 0 bei der Anwendung des euklidischen Algorithmus von f_n und f_{n-1} entstehen. Die Inverse bekommt man nun, indem man den erweiterten euklidischen Algorithmus auf f_n und f_{n-1} anwendet. Der liefert dir eine Darstellung der 1 in der Form a*f_n + b*f_{n-1} = 1. Diese Darstellung musst du dann noch mit vollständiger Induktion beweisen. Das Inverse von f_{n-1} modulo f_{n} ist dann b. |
||
| 01.07.2004, 18:39 | Benutzer | Auf diesen Beitrag antworten » |
| Noch 'ne Skizze.... Huhu, am elementarsten ist wohl einfach vollständige Induktion unter Ausnutzung der relevanten Definitionen, also ein Vorgehen nach dem Motto: 1. Der Fall n=1 bleibt dem Korrektor überlassen. 2. Der Fall n->n+1 bleibt auc... äh, Sei f_(n-1) invertierbar modulo f_n. Dann gibt es a,b aus Z mit a*f_n + b*f_(n-1) = 1. Weil nun f_(n-1) = f_(n+1) - f_n ist, folgt daraus.............. und also q.e.d. 
.Mfg, ein Freund elementarer Beweise P.S.: Die Anzahl der lückenfüllenden Punkte da oben ist nicht identisch mit der Länge des ausgelassenen Beweisschrittes gemessen in Buchstaben. |
||
| 02.07.2004, 15:15 | blackdrake | Auf diesen Beitrag antworten » |
Hallo. Ich habe mir die Fib-Funktion vor Kurzem selbst beigebracht. Ich habe folgendes in meiner Formelsammlung: fib(n) = fib(n-1) + fib(n-2) fib(1) = fib(0) = 1 Zitat von Irrlicht: f_{2} = f_{1} + f_{0} = 1 + 0 Ich würde sagen: fib(2) = fib(1) + fib(0) = 1 + 1 = 2 |
||
| Anzeige | ||
|
|
||
| 02.07.2004, 16:28 | Irrlicht | Auf diesen Beitrag antworten » |
Och, blackdrake! Jetzt dreh hier nur keinen Strick draus, dass ich die Elemente anders nummeriere.
Ich fange mit f_0 = 0 und f_1 = 1 an und du mit f_0 = f_1 = 1.Gruss, langsam verwirrtes Irrlicht EDIT: Sorry, vielleicht meintest du mich auch nicht persönlich - es ist eigentlich völlig egal, mit welchen Startwerten du anfängst. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
