Wie zeige ich, dass aufeinanderfolgende Fibonaccizahlen teilerfremd sind?

Question

Wie zeige ich dass fn und fn+1 für alle n  teilerfremd sind ? Wie Zeige ich das mit induktion ?

Comments

                <p><strong>Vom Duplikat:</strong></p>
                <p>Titel: Beweisen, dass aufeinanderfolgende Glieder der Fibonacci Folge teilerfremd sind.</p>
                <p>Stichworte: rekursiv,induktion,fibonacci</p>
            Ich soll mittels Induktion beweisen, dass aufeinanderfolgende Glieder der Fibonacci Folge teilerfremd sind. Hierzu habe ich folgende Informationen:

Die Fibonacci Folge F : N -> N ist rekursiv wie folgt gegeben:
F(0) = 0
F(1) = 1
F(n + 2) = F(n) + F(n + 1)

Mir ist nicht ganz klar, wie ich da vorzugehen habe.

---

Vielleicht kannst du was mit dem ggT anfangen? Wenn ggT(a,b) = 1, dann sind a und b teilerfremd. Außerdem gibt es zum ggT einige vielleicht nützliche Rechenregeln, siehe Wikipedia.

---

https://de.wikipedia.org/wiki/Fibonacci-Folge

Falls du diese Tabelle begründen kannst, folgt deine Behauptung eigentlich direkt.

---

1, 1, 2, 3, 5, 8, 13, 21, 34 Alle aufeinanderfolgrnden sind gerade und ungerade

---

EDIT:

" dass f und fn+1 für alle n  teilerfremd sind ? "

Fehlt da ein n? 

Ist wohl: https://www.mathelounge.de/66995/beweisen-aufeinanderfolgende-glieder-fibonacci-teilerfremd

---

Ohh Jaa da fehlt ein n aber das ist keine induktion .ich brauch eine induktion

---

Dann schreib einmal die definierenden Formeln hin.

EDIT: Habe nun die Eingangsdiskussion von 2013 hierhin umgeleitet, damit sie wieder aufgenommen werden kann und nicht noch eine alte Frage mehr offen bleibt. 

---

Fn=fn-1+fn-2

F0=0

F1=1

---

Welche Teiler hat denn 0 ? 

1, 1, 2, 3, 5, 8, 13, 21, 34 

Also: 0 und 1 sind teilfremd.

1 und 1 auch,

1 und 2 auch

2 und 3 auch   , ab hier kannst du wohl davon ausgehen, dass die Verankerung gelungen ist.

---

Aber wie zeigt man das denn formal?

---

Jetzt musst du halt warten, ob jemand einen Induktionsschritt hinbringt und deine Frage beantwortet wird.

(Meinst du wirklich Fibonaccizahlen und nicht etwas Fermatzahlen? https://www.mathelounge.de/441203/beweisen-beliebige-verschiedene-fermat-zahlen-teilerfremd  )

Answer 1

Die Fibonacci Folge F : N -> N ist rekursiv wie folgt gegeben:
F(0) = 0
F(1) = 1
F(n + 2) = F(n) + F(n + 1)

Ind.anfang hast du ja.

Sei  n≥1 und die Beh. wahr für alle k≤n, also immer ggT(  F(k) ,F(k-1) ) = 1

Dann gilt F(n+1) = F(n) + F(n-1) .

Sei nun t ein gemeinsamer Teiler von  F(n+1) und  F(n) , dann gilt wegen

 F(n-1) =   F(n+1) -  F(n)

auch  t ist Teiler von F(n-1) , also auch ein gem. Teiler

von  F(n-1) und  F(n) , also nach Ind. vor  t=1.

Comments

Ich stelle auch mal eine Variante zur Diskussion:

Definitionen:
$$ f (1)=1$$ $$f (2)=1$$
$$ f (n+2)=f(n+1)+f(n)$$
$$q_{n}=\frac{f(n+1)}{f(n)}$$
Beginn:
$$q_3= \frac {f(4)}{f(3)}= \frac 32$$
 $$q_3 \notin \mathbb{N}$$
$$q_n=\frac{f(n+1)}{f(n)}$$
$$q_{n+1}=\frac{f(n+2)}{f(n+1)}$$
$$q_{n+1}=\frac{f(n+1)+f(n)}{f(n+1)}$$
$$q_{n+1}=1+ \frac{f(n)}{f(n+1)}$$
Schluß:
Da  $$q({n})\notin \mathbb{N}$$ ist $$q({n+1})\notin \mathbb{N}$$ für  alle $$n \ge 3$$ erfüllt.

---

Wenn \(q(n+1) \not \in \mathbb{N}\) ist, so heißt das doch nicht automatisch, dass \(f(n+2) \perp f(n+1)\) ist - oder?

---

Wenn man eine größere Zahl durch eine kleinere dividiert und das ganzzahlig ohne Rest aufgeht, würde ich vermuten, dass die einen gemeinsamen Teiler haben.

Umgekehrt sollte es keine zwei natürlichen Zahlen mit gemeinsamen Teilern geben, die nach ihrer Division (größere durch die kleinere) einen Quotienten ergeben, der keine natürliche Zahl ist.

Diese Annahme habe ich stillschweigend unbewiesen eingesetzt, ohne diese nachzuweisen. Kann aber im Bezweifelnsfalle nachgeliefert werden oder könnte auch sein, dass ich was übersehen habe. Wie gesagt: Mein Vorschlag soll Diskussionsgrundlage sein und ich freue mich über kritische Anregungen.

---

@pleindespoir, Du schriebst: "Umgekehrt sollte es keine zwei natürlichen Zahlen ... "

z.B. es gibt die \(30\) und die \(42\)

" ... mit gemeinsamen Teilern geben,... "

in diesem Fall die \(2\) und die \(3\)

"... die nach ihrer Division (größere durch die kleinere) einen Quotienten ergeben, .."

$$q = 42 : 30 = \frac{42}{30} = \frac{7}{6}$$

" ... der keine natürliche Zahl ist."

$$q=\frac{7}{6} \not \in \mathbb{N}$$

Halten wir fest: es gibt die Zahlen \(30\) und \(42\), sie haben gemeinsame Teiler und ihr Quotient ist keine natürliche Zahl.

---

Danke - dann hab ich wohl Käse produziert. So einfach und doch vermurkst.

Schade ...