Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Teilerfremdheit aufeinanderfolg. Fibonaccizahlen

Teilerfremdheit aufeinanderfolg. Fibonaccizahlen

Universität / Fachhochschule

Elementare Zahlentheorie

Tags: Elementare Zahlentheorie, Fibonacci Folge, Teilbarkeit

Nicole-B aktiv_icon

16:43 Uhr, 11.05.2009

Folgende Aufgabe soll ich lösen:

Sei

(f_{n}) n

ℕ

die Fibonacci-Folge. Beweisen Sie durch vollständige
Induktion, dass für alle

n

ℕ

die aufeinanderfolgenden Glieder

f_{n}

und

f_{n + 1}

teilerfremd sind.

Mein Problem liegt darin, dass ich das per Induktion beweisen soll. Argumentativ wäre die Aufgabe kein Problem.
Bis jetzt habe ich:
Induktionsanfang: Sei

n = 3 \Rightarrow f_{3} = 2, f_{4} = 3 \Rightarrow

ggT(

f_{3}, f_{4}) = 1

Induktionsvorraussetzung: Es gilt: ggT(

f_{n}, f_{n + 1}) = 1

Induktionsbehauptung: Es gilt: ggT(

f_{n + 1}, f_{n + 2}) = 1

und beim Induktionsbeweis weiß ich nicht wie ich es machen soll. Es gibt ja zwei möglichkeiten das ggT von zwei Zahlen auszurechnen:
1. Primfaktorzerlegung (fällt weg, da ich die Zahlen nicht in die Primfaktoren zerlegen kann, weil es irgendwelche

f_{n}

sein können)
2. Euklidischer Algorithmus (das wäre dann so: ich kann

f_{n + 1}

als

f_{n} + f_{n - 1}

darstellen, weil die Fibonaccizahlen so definiert sind und

f_{n + 2}

als

f_{n + 1} + f_{n}

so beim euklidischen Algorithmus macht führt man so lange die Division mit Rest durch, bis kein Rest mehr bleibt. Aber wie mache ich das?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Sebus aktiv_icon

17:18 Uhr, 11.05.2009

f_{1} = 0, f_{2} = 1;

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

ZZ:

f_{n}

und

f_{n + 1}

sind teilerfremd.
Induktionsanfang:

n = 2

geht auch schon:

g g T (f_{2}, f_{3}) = g g T (1, 2) = 1

.

Induktionsschritt:

n \to n + 1

Klar:

f_{n + 2} = f_{n + 1} + f_{n}

Einsetzen:

g g T (f_{n + 2}, f_{n + 1}) = g g T (f_{n + 1} + f_{n}, f_{n + 1})

Und jetzt behaupte ich:
"Wenn man zwei teilerfremde Zahlen addiert, ist die Summe teilerfremd zu beiden Summanden."
Den Beweis und die Anwendung dieser Aussage überlasse ich als Übungsaufgabe. :-)

Nicole-B aktiv_icon

20:24 Uhr, 11.05.2009

Erstmal danke und dann habe ich noch eine Frage: Kann ich auch einfach so argumentieren, dass ich mit dem euklidischen Algorithmus ja den ggT bestimmen kann und dann

f_{n + 2} = 1 \cdot f (n + 1) + f_{n}

ist (per Definition der Fibonacci Zahlen)
dann

f_{n + 1} = 1 \cdot f_{n} + f_{n - 1}

.
.
.

f_{3} = 1 \cdot f_{2} + f_{1}

f_{2} = f_{1}

(per Def.)

weil so habe ich ja nichts dazu erfunden sondern nur alle Informationen genutzt die ich über die Fibonacci Zahlen habe.

Sebus aktiv_icon

20:29 Uhr, 11.05.2009

Nein, ich fürchte, du kannst mit dem Euklidischen Algorithmus nicht argumentieren. Solange du über die Teilbarkeit der Fibonacci-Folgenglieder noch gar nichts weißt, kannst du nicht einfach behaupten, dass bei der Division

\frac{f_{n + 2}}{f_{n + 1}}

der Rest

f_{n}

bleibt. Das ist zwar korrekt, setzt aber doch bereits voraus, dass

f_{n + 2}

und

f_{n + 1}

teilerfremd sind.

: - (

Nicole-B aktiv_icon

20:36 Uhr, 11.05.2009

tja schade dann gibts halt nicht die volle punktzahl aber danke nochmal. :-)

Nicole-B aktiv_icon

20:44 Uhr, 11.05.2009

Danke dass du dir für meine Frage Zeit genommen hast

Sebus aktiv_icon

21:19 Uhr, 11.05.2009

War mir ein Vergnügen, und man lernt ja auch immer selbst etwas dabei. Wer weiß, vielleicht kommt gleich einer der ganz großen Profis und sagt uns, wie das alles wirklich geht. Ich bin ja auch bloß naiver Zweitsemester...

609358

609074

	Status: nicht eingeloggt	Noch nicht registriert?