Fibonacci Folge

Neue Frage »

17.07.2008, 17:41

Felix

Auf diesen Beitrag antworten »

Fibonacci Folge

Ich soll beweisen, dass zwei benachtbarte Zahlen der Folge teilerfremd sind. Wie gehe ich das am besten an?

lg Felix

17.07.2008, 17:53

therisen

Auf diesen Beitrag antworten »

Nimm dir einen gemeinsamen Teiler zweier benachbarter Fibonacci-Zahlen und zeige, dass er die Zahl 1 teilen muss.

17.07.2008, 21:00

Auf diesen Beitrag antworten »

Ob der Felix über diese Antwort so besonders glücklich war? Augenzwinkern

Eigentlich ist die Sache im Nu erledigt, wenn man an die für beliebige ganze Zahlen $\begin{eqnarray*} a,b \end{eqnarray*}$ geltende Eigenschaft

$\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-a) \end{eqnarray*}$

des größten gemeinsamen Teilers denkt. Ja Ok, formal kann ein bissel Induktion in dem Zusammenhang nicht schaden.

18.07.2008, 00:47

tmo

Auf diesen Beitrag antworten »

Ob man jetzt $\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-a) \end{eqnarray*}$ oder $\begin{eqnarray*} a|b \wedge a|c \Longrightarrow a|b-c \end{eqnarray*}$ nutzt, ist doch egal Augenzwinkern

therisen wollte wohl in Verbindung mit $\begin{eqnarray*} f_1 = 1 \end{eqnarray*}$ auf letzteres hinaus.

18.07.2008, 10:13

therisen

Auf diesen Beitrag antworten »

Ja, ich wollte nur nicht zu viel verraten (was bei dieser Aufgabe gar nicht so leicht ist, da sie im Prinzip ein Einzeiler (ohne Induktion) ist). Die zweite Antwort wäre dann verständlich(er) geworden, aber bislang gibt es ja noch keine Antwort von Felix. Wink

18.07.2008, 11:35

Auf diesen Beitrag antworten »

Zitat:

Original von therisen
da sie im Prinzip ein Einzeiler (ohne Induktion) ist).

Naja, manche Induktion nimmt man als solche nicht für voll - ist aber trotzdem eine. Augenzwinkern

18.07.2008, 11:39

Felix

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-a) \end{eqnarray*}$ warum gilt das bzw wie beweist man das. Für a = b kann das ja nicht gelten ?

Und wenn ich diese Eigenschaft jetzt verwende, dann komme ich durch ständiges wiederholen des Vorgangs auf ggT(1,1) die ersten zwei Glieder der Fibonaccifolge -----> daraus folgt der ggT zweier beliebiger Zahlen a,b der Fibonaccifolge muss 1 teilen womit die beiden Zahlen teilerfremd sind. Hab ich das so richtig verstanden ?

2)

$\begin{eqnarray*} a|b \wedge a|c \Longrightarrow a|b-c \end{eqnarray*}$ ---> könntest du mir erklären wie das gemeint ist ? bzw was das überhaupt bedeutet ? unglücklich

18.07.2008, 11:58

Auf diesen Beitrag antworten »

Zitat:

Original von Felix
$\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-a) \end{eqnarray*}$ warum gilt das bzw wie beweist man das. Für a = b kann das ja nicht gelten ?

Wieso nicht? Auch da gilt das!

Zitat:

Original von Felix
Und wenn ich diese Eigenschaft jetzt verwende, dann komme ich durch ständiges wiederholen des Vorgangs auf ggT(1,1) die ersten zwei Glieder der Fibonaccifolge

Richtig.

Zitat:

Original von Felix
-----> daraus folgt der ggT zweier beliebiger Zahlen a,b der Fibonaccifolge muss 1 teilen womit die beiden Zahlen teilerfremd sind.

Mit dieser unlogischen Schlussfolgerung bist du übers Ziel hinausgeschossen, sie ist übrigens auch falsch: Es geht um zwei aufeinander folgende Glieder der Folge, NICHT um zwei beliebige.

Was das betrifft, gibt es übrigens eine interessante Eigenschaft der Fbonaccifolge: Es gilt uneingeschränkt

$\begin{eqnarray*} \operatorname{ggT}(F_m,F_n) = F_{\operatorname{ggT}(m,n)} \end{eqnarray*}$

Eine im ersten Moment verblüffende Eigenschaft, die sich aber relativ einfach nachweisen lässt.

18.07.2008, 12:30

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Felix
$\begin{eqnarray*} a|b \wedge a|c \Longrightarrow a|b-c \end{eqnarray*}$ ---> könntest du mir erklären wie das gemeint ist ? bzw was das überhaupt bedeutet ? unglücklich

$\begin{eqnarray*} a|b \end{eqnarray*}$ bedeutet, dass a die Zahl b teilt.

Die Aussage lautet in Worten: Eine Zahl, die zwei Zahlen teilt, teilt auch deren Differenz.

18.07.2008, 12:34

Felix

Auf diesen Beitrag antworten »

Zitat:

Mit dieser unlogischen Schlussfolgerung bist du übers Ziel hinausgeschossen, sie ist übrigens auch falsch: Es geht um zwei aufeinander folgende Glieder der Folge, NICHT um zwei beliebige

Gut da war ein Fehler in der Formulierung aber gemeint hab ich, dass der ggT zweier beliebiger benachbarter Glieder 1 teilen können muss. Das stimmt doch oder ??

Zitat:

Wieso nicht? Auch da gilt das!

Aso jede reele Zahl ist ja ein Teiler von 0 ....

Zitat:

Eine im ersten Moment verblüffende Eigenschaft, die sich aber relativ einfach nachweisen lässt.

Über einen Ansatz wäre ich wieder froh smile

18.07.2008, 12:50

Auf diesen Beitrag antworten »

Zitat:

Original von Felix
Aso jede reele Zahl ist ja ein Teiler von 0 ....

Eben! Also ist $\begin{eqnarray*} \operatorname{ggT}(a,0)=a \end{eqnarray*}$ , das steht doch in Übereinstimmung mit $\begin{eqnarray*} \operatorname{ggT}(a,a)=a \end{eqnarray*}$ . Ich weiß nicht, was du da noch rumzumäkeln hast. Forum Kloppe

18.07.2008, 12:52

Felix

Auf diesen Beitrag antworten »

Also wenn a b teilt und a c teilt dann teilt a auch b - c.

Auf die Fibonaccifolge angewendet wäre angenommen (b und c sind benachbart) b - c as Glied vor b und c. Auch hier wiederhohlt man den den Vorgang bis man am Anfang der Folge angelangt und damit bewieden hat das a 1 teilen können muss.
Stimmt das ?

lg

Edit @ Arthur

gar nichts, ich hab ja "aso" und nicht "wieso" geschrieben Augenzwinkern

18.07.2008, 13:01

Auf diesen Beitrag antworten »

Was den Ansatz zu

$\begin{eqnarray*} \operatorname{ggT}(F_m,F_n) = F_{\operatorname{ggT}(m,n)} \end{eqnarray*}$

betrifft: Erstmal diese Eigenschaft nachweisen (über Induktion), dann kann man

$\begin{eqnarray*} \operatorname{ggT}(F_m,F_n) = \operatorname{ggT}(F_m,F_{n-m}) \end{eqnarray*}$

für beliebige ganze Zahlen $\begin{eqnarray*} n\geq m\geq 0 \end{eqnarray*}$ folgern. Und das ist mehr als die halbe, nämlich nahezu schon die ganze Miete.

Neue Frage »

Antworten »

Fibonacci Folge

Verwandte Themen