Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Lemma von Bezout Fibonacci Reihe

Lemma von Bezout Fibonacci Reihe

Universität / Fachhochschule

Tags: Bezout, Euklidischer Algorithmus, Fibonacci Folge

anonymous

03:18 Uhr, 13.11.2023

Bestimmen Sie ganze Zahlen

x, y,

sodass gilt

x

· Fn

+ y

· Fn+1

= 1

für alle natürliche Zahlen

n

gilt.
Bei

F

handelt es sich um die Fibonacci Folge,

n

gibt an welcher Stelle man sich befindet. Durch das Lemma von Bezout ist klar ,das ggt(Fn,fn+1)=1.Das lässt sich auch leicht durch den Euklidischen Algorithmus zeigen. Mein Problem liegt nun dabei ,dass ich beim rückwärtseinsetzen nur die ganzen Zahlen

x

und

y

vom jeweiligen

n

bekomme. Ein richtiges Schema von

x

und

y

erkenn ich beim durchgehen der eingesetzen n´s auch nicht.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

michaL aktiv_icon

07:28 Uhr, 13.11.2023

Hallo,

nun, die Gleichung

1 = x_{n} \cdot F_{n + 1} + y_{n} \cdot F_{n}

ist per

F_{n + 1} = F_{n} + F_{n - 1}

zurückzuführen auf

1 = x_{n} (F_{n} + F_{n - 1}) + y_{n} \cdot F_{n} = (x_{n} + y_{n}) F_{n} + x_{n} F_{n - 1}

, d.h. es gelten

x_{n - 1} = x_{n} + y_{n}

und

y_{n - 1} = x_{n}

.

Das würde ich eben umdrehen zu

x_{n} = y_{n - 1}

und

y_{n} = x_{n - 1} - x_{n} = x_{n - 1} - y_{n - 1}

Diese beiden Gleichungen sind per Induktion zu beweisen. (Vorwärts, nicht rückwärts, wie bei mir oben.)

Ich weiß weder, bei welchem Index, noch mit welchen Zahlen bei euch die Fibonaccizahlen definiert worden sind.
Ich gehe vielleicht mal von

F_{1} := F_{2} := 1

und

F_{n + 1} = F_{n} + F_{n - 1}

aus.
Dann könnte man

1 = 1 \cdot F_{2} + 0 \cdot F_{1}

und damit

x_{0} = 1

y_{0} := 0

nehmen.

Gemäß Rekursion müsste gelten:

x_{1} := y_{0} = 0

y_{1} := x_{0} - y_{0} = 1 - 0 = 1

Und siehe da: Es gilt:

1 = x_{1} F_{2} + y_{1} F_{1} = 0 \cdot 2 + 1 \cdot 1

Noch eine weitere Iteration:

x_{2} := y_{1} = 1

y_{2} := x_{1} - y_{1} = 0 - 1 = - 1

1 \cdot F_{3} + (- 1) \cdot F_{2} = 1 \cdot 3 - 1 \cdot 2 = 1

Mfg Michael

story aktiv_icon

08:46 Uhr, 13.11.2023

Eine sehr schöne Lösung! Nur glaube ich (kann mich natürlich täuschen), dass am Anfang

x

und

y

vertauscht wurden und dass die Indizes jeweils um

1

zu niedrig gewählt worden sind. Den vorigen Kommentar weitgehend kopierend, würde ich sagen:

Aus

1 = x_{n} \cdot F_{n} + y_{n} \cdot F_{n + 1}

, darstellbar auch als

1 = x_{n} \cdot F_{n} + y_{n} \cdot (F_{n - 1} + F_{n}) = y_{n} \cdot F_{n - 1} + (x_{n} + y_{n}) \cdot F_{n}

folgt

y_{n} = x_{n - 1}

sowie

x_{n} + y_{n} = y_{n - 1} \overset{}{\Leftrightarrow} x_{n} = y_{n - 1} - y_{n} = y_{n - 1} - x_{n - 1}

.

Wenn wir

F_{1} := F_{2} := 1

sowie

F_{n + 1} = F_{n - 1} + F_{n}

setzen, ergibt es Sinn, die Indizes bei

1

zu starten (

F_{0}

ist ja gar nicht erklärt.) Also etwa

x_{1} = 1

und

y_{1} = 0

. Rekursiv ergibt sich dann

x_{2} = - 1

und

y_{2} = 1

x_{3} = 2

und

y_{3} = - 1

x_{4} = - 3

und

y_{4} = 2

und so weiter - Nachrechnen zeigt, dass all diese

x_{n}, y_{n}

tatsächlich die obige Gleichung erfüllen.

Übrigens wundert mich bei der Aufgabenstellung, dass von ganzen Zahlen

x, y

und nicht von ganzen Zahlen

x_{n}, y_{n}

die Rede ist. Ersteres suggeriert für mich, dass es FESTE ganze Zahlen

x, y

unabhängig von

n

gäbe, was ja aber nicht der Fall ist.

HAL9000

08:50 Uhr, 13.11.2023

Auf diesem Wege fortschreitend kann man dann mit genug gesichtetem Zahlenmaterial die Vermutung

{(- 1)}^{n} = F_{n - 1} F_{n} - F_{n - 2} F_{n + 1}

aufstellen, um diese anschließend seriös über Vollständige Induktion zu beweisen. ;-)

P.S.: Zugegeben, für

n < 2

muss man dazu die Fibonacci-Folge nach unten "verlängern":

F_{- 1} = F_{1} - F_{0} = 1

und

F_{- 2} = F_{0} - F_{- 1} = - 1

story aktiv_icon

09:11 Uhr, 13.11.2023

... oder (die gleiche Idee anders dargestellt) beweisen, dass für alle

n \geq 2

gewählt werden kann:

x_{n} = (- 1)^{n + 1} F_{n}

und

y_{n} = (- 1)^{n} F_{n - 1}

, dass also stets gilt:

1 = (- 1)^{n + 1} F_{n} \cdot F_{n} + (- 1)^{n} F_{n - 1} \cdot F_{n + 1}

.

Induktionsanfang (

n = 2

)
Die Gleichung

1 = - 1 \cdot 1 \cdot 1 + 1 \cdot 1 \cdot 2

ist wahr.

Induktionsschluss

(- 1)^{n + 2} F_{n + 1} \cdot F_{n + 1} + (- 1)^{n + 1} F_{n} \cdot F_{n + 2}

= (- 1)^{n + 2} \cdot F_{n + 1} \cdot (F_{n - 1} + F_{n}) + (- 1)^{n + 1} \cdot F_{n} \cdot (F_{n} + F_{n + 1})

= ((- 1)^{n + 1} F_{n} \cdot F_{n} + (- 1)^{n} F_{n - 1} \cdot F_{n + 1}) + (- 1)^{n + 2} F_{n + 1} \cdot F_{n} + (- 1)^{n + 1} F_{n} \cdot F_{n + 1}

= 1 + 0 = 1

.

Umgangssprachlich ausgedrückt bilden also die Zahlenwerte

x_{n}

und

y_{n}

selbst wieder zwei Fibonacci-Folgen, nur dass die beiden Folgen versetzt sind und die enthaltenen Zahlen stets ihr Vorzeichen wechseln.

HAL9000

09:18 Uhr, 13.11.2023

Ja, geht auch. Ich hatte mich nur für die andere Variante entschieden der betragskleineren Bezout-Koeffizienten wegen. Sieht man am Start nicht gleich (und hat zudem Ärger mit den negativen Indizes), aber wenig später dann schon.

Es ist natürlich klar, dass die Lösung nicht eindeutig ist: Mit

1 = x_{n} F_{n} + y_{n} F_{n + 1}

ist selbstverständlich auch jedes

1 = (x_{n} + z_{n} F_{n + 1}) F_{n} + (y_{n} - z_{n} F_{n}) F_{n + 1}

Lösung, mit beliebig wählbarem ganzzahligen

z_{n}

michaL aktiv_icon

10:44 Uhr, 13.11.2023

Hallo,

> dass am Anfang x und y vertauscht wurden

Hm, Buchstaben sind Schall und Rauch.

> und dass die Indizes jeweils um 1 zu niedrig gewählt worden sind.

Da würde ich sagen, dass es Geschmackssache ist. Ich hatte vorhin nicht so viel Zeit. Es mag schon sein, dass die Zuordnung des Index zur größeren der der beiden Fibonaccizahlen sinnvoller ist. Das habe ich aber nicht geprüft.

Die Gleichung
>

(- 1)^{n} = F_{n - 1} F_{n} - F_{n - 2} F_{n + 1}

ähnelt der Cassini-Identität:

(- 1)^{n} = F_{n - 1} F_{n + 1} - F_{n}^{2}

Beide sind offenbar in einander umrechenbar. (Musste ich mich aber eben von überzeugen.)
Sie stand noch vor nicht allzu langer bei wikipedia. Nun ist sie nicht mehr zu finden (hatte vorhin danach gesucht, weil mir auch der Name nicht mehr einfiel).
Bei Bianca Högel

^{[1]}

(sehr fleißig im Kopieren von wikipedia-Artikeln mit mathematischem Bezug) ist sie noch zu finden.

Mfg Michael

[1] www.biancahoegel.de/mathe/folge/fibonacci_folge.html (gesichtet: 13.11.23, ~ 10:00 Uhr)

PS: Wenn das Lemma von Bézout zur Verfügung steht, reicht auch die leicht nachzuweisende Gleicheit

ggT (F_{n + 1}, F_{n}) = ggT (F_{n}, F_{n - 1})

, die (indutkiv) auf 1 führt.

HAL9000

11:04 Uhr, 13.11.2023

Kenne diese ganzen Spezialbezeichnungen nicht, aber offenbar ist dann die von mir angegebene Identität (mit den minimalen Bezout-Koeffizienten) die Identität von d’Ocagne angewandt auf

m = n - 2

unter Berücksichtigung von

F_{- 2} = - 1

.

Überhaupt kann man via

F_{n} = F_{n + 2} - F_{n + 1}

ja auch die Fibonacci-Folge auf negative Indizes ausdehnen und bekommt schnell den Zusammenhang

F_{- n} = {(- 1)}^{n - 1} \cdot F_{n}

für alle

n

. In dem Zusammenhang gilt dann die ebenfalls auf der biancahoegel-Seite angegebene Identität

F_{m + n} = F_{n + 1} F_{m} + F_{n} F_{m - 1}

tatsächlich für alle GANZEN (!) Indizes

m, n

. Da kann man dann rumspielen und etwa

m = - n + 1

einsetzen, oder

m = - n + 2

o.ä. ...

michaL aktiv_icon

11:25 Uhr, 13.11.2023

Hallo,

ich will mich da auch nicht mit fremden Federn schmücken.
Ich kannte den Namen auch nicht. Nicht einmal die Details der Formeln. Nur, dass es in etwa das sein könnte, was man hier brauchen könnte.
Ich habe es dann nicht (mehr) bei wikipedia (oder schnell sonst wo) gefunden und mir etwas eigenes zusammengeschustert.

Mfg Michael

HAL9000

12:24 Uhr, 13.11.2023

So wie story den Induktionsbeweis für die eine Identität genannt hat, liefere ich der Vollständigkeit halber mal noch den für die andere:

Induktionsanfang lass

n = 0

gilt wegen

F_{- 1} \cdot F_{0} - F_{- 2} F_{1} = 1 \cdot 0 - (- 1) \cdot 1 = 1 = {(- 1)}^{0}

.

Im Induktionsschritt

n \to n + 1

rechnet man

F_{n} F_{n + 1} - F_{n - 1} F_{n + 2} = (F_{n - 2} + F_{n - 1}) F_{n + 1} - F_{n - 1} (F_{n} + F_{n + 1})

= F_{n - 2} F_{n + 1} - F_{n - 1} F_{n} = - (F_{n - 1} F_{n} - F_{n - 2} F_{n + 1}) \overset{I V}{=} - {(- 1)}^{n} = {(- 1)}^{n + 1}

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1578392

1578372

	Status: nicht eingeloggt	Noch nicht registriert?