Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Induktion mit ggT

Induktion mit ggT

Universität / Fachhochschule

Relationen

Tags: Relation.

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
mathbirl

mathbirl aktiv_icon

10:40 Uhr, 11.12.2023

Antworten
Hallo,
ich hätte eine Frage zu einer Aufgabe.
Aufgabe: Für n aus N (Natürliche Zahlen mit 0), sei eine ganze Zahl fn aus N (Natürliche Zahlen mit 0), durch f0=0,f1=1 und fn =f(n-1)+f(n-2), rekursiv definiert (Fibonacci-Folge)
(die n bei den f sollen als Index stehen, sind ja Fibonacci-Zahlen)

Zuerst sollte ich die Fibonacci Zahlen f2,…,f12 berechnen:
f1=0
f2=f1+f0=1
f3=f2+f1=2
….
f12=f11+f10=144


Nun ist die Frage hier:
Zweite Aufgabe: Ich sollte, durch Induktion nach n aus N (Natürliche Zahlen mit 0) zeigen, das f(n+1) und fn für alle n aus N teilerfremd sind (Hinweis : Euklidischer Algorithmus)

Mein Ansatz:
fn und f(n+1) sind teilerfremd ⇔ ggT(f(n +1), fn) =1

Induktionsanfang: n=1: ggT(f2,f1) = ggT(1,1) =1

Induktionsvorraussetzung: Es gibt ein n aus N und ein fn, f(n+1) aus N: ggT(f(n+1), fn) =1

Behauptung: f(n+2),f(n+1) sind auch teilerfremd:
ggT(f(n +2),f(n+1))= ggT(f(n +1)+ fn, fn +f(n-1))= ggT(f(n +1)+ fn, f(n+1))= ggT(fn, f(n+1))
= ggT(f(n +1), fn)
nach Induktionsvorraussetzung ist das teilerfremd.

Hab ich die Induktion korrekt gemacht?


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

michaL aktiv_icon

11:03 Uhr, 11.12.2023

Antworten
Hallo,

> Hab ich die Induktion korrekt gemacht?

Ja, die Induktion ist korrekt durchgeführt.
Wie du selbst gemerkt hast(?), brauchst du nur f(n+2) zu ersetzen (also die Fibonaccizahl mit größerem Argument).

Mfg Michael
Antwort
HAL9000

HAL9000

11:14 Uhr, 11.12.2023

Antworten
Der Induktionsschritt wird womöglich transparenter, wenn man angibt, welche ggT-Umformungsregel man hier nutzt - also sowas wie

ggT(a,b)=ggT(a-b,b) angewandt auf a=f(n+1)+f(n) und b=f(n+1).



P.S.: Interessant ist übrigens, dass für die Fibonacci-Folge gilt

ggT(f(n),f(m))=f(ggT(n,m)) für beliebige natürliche Indizes m,n .

Das oben ist diesbezüglich der Spezialfall m=n+1. ;-)
Frage beantwortet
mathbirl

mathbirl aktiv_icon

13:49 Uhr, 11.12.2023

Antworten
Alles klar, dankeschön! :-)