Mathematik: Sätze über Teilbarkeiten bei Fibonaccizahlen
Released by matroid on Di. 05. Juni 2007 20:20:20 [Statistics]
Written by robbe - 5222 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\) Der folgende Artikel ist meine Mitschrift eines Vortrags vom letzten Mathewochenende in Gütersloh. Bekanntlich ist die Folge der Fibonaccizahlen folgendermaßen definiert: Definition: F_0=0, F_1=1, F_(n+2):=F_(n+1)+F_n

\ Beginnen wir mit einer Summenformel für Fibonaccizahlen: Formel: sum(F_k,k=1,n)=F_(n+2)-1 Beweis: Laut Definition gilt F_1=F_3-F_2 F_2=F_4-F_3 F_3=F_5-F_4 ... F_(n-1)=F_(n+1)-F_n F_(n)=F_(n+2)-F_(n+1) Summiert man diese Gleichungen nun auf, bleibt lediglich F_1+F_2+...+F_n=F_(n+2)-F_2=F_(n+2)-1, da F_2=1 Bevor wir zu Teilbarkeiten innerhalb der Folge der Fibonaccizahlen übergehen, benötigen wir noch folgende Formel zum "Aufsplitten" einer Fibonaccizahl. Formel A: F_(n+m)=F_(n-1) F_m+F_n F_(m+1) Beweis durch Induktion: Offensichtlich gilt die Formel für m=0 und m=1. Angenommen, sie gilt für m=k und m=k+1, so folgt F_(n+k)=F_(n-1) F_k+F_n F_(k+1) F_(n+k+1)=F_(n-1) F_(k+1)+F_n F_(k+2). Durch Aufsummieren und Verwenden der Definition erhält man: F_(n+k+2)=F_(n-1) F_(k+2)+F_n F_(k+3). Nun kommen wir zum ersten Satz über Teilbarkeiten bei Fibo´s Satz: Aus m\|n folgt F_m \|F_n Beweis: Aus m\|n folgt n=m_1 m. Wir führen vollständige Induktion über m_1 durch; der Fall m_1=1 ist trivial. Angenommen, der Satz gilt für m_1=k, d.h. F_m \|F_(mk), so folgt daraus, dass F_(mk-1) F_m+F_(m k) F_(m+1) durch F_m teilbar ist, das sowohl F_m als auch F_(mk) nach Induktionsannahme durch F_m teilbar sind. Es ist aber nach Formel A F_(mk-1) F_m+F_(m k) F_(m+1)=F_(mk+m)=F_(m(k+1)), was ja zu zeigen war. Im folgenden wird (a,b) als Abkürzung für ggT(a,b) benutzt. Satz B: (F_m, F_n)=F_(m,n) Beweis: Es ist m=nq_0 +r_1 (F_m, F_n)=(F_(nq_0 +r_1), F_n)=(F_(nq_0 -1) F_(r_1)+F_(nq_0) F_(r_1), F_n) nach Formel A. (F_(nq_0 -1) F_(r_1)+F_(nq_0) F_(r_1), F_n)=(F_(nq_0 -1) F_(r_1), F_n), da F_(nq_0) F_(r+1) durch F_n teilbar ist. (F_(nq_0 -1) F_(r_1), F_n )=(F_(r_1) ,F_n), da F_(nq_0 -1) und F_n teilerfremd sind. Anwendung des Euklidischen Algorithmus bringt: (F_(r_1) ,F_n)=(F_(r_2) ,F_(r_1))=(F_(r_3) ,F_(r_2))=... =(F_(n,m) ,F_(n,m))=F_(n,m) Da n und n+1 teilerfremd sind folgt aus diesem Satz auch, dass zwei aufeinanderfolgende Fibonaccizahlen teilerfremd sind. Nehmen wir uns nun eine natürliche Zahl k und betrachten die kleinste Fibo-Zahl, die durch k teilbar ist, wir nennen sie F_m. Wir wollen nun zeigen, dass wenn auch F_n durch k teilbar ist, F_m \| F_n gilt. Angenommen, es gäbe ein F_p mit k\|F_p und F_m \teiltnicht F_p .Dann teilt m p ebenfalls nicht und es gilt k\|(F_m ,F_p)=F_(m,p). (Satz B) Da F_m die kleinste durch k teilbare Fibo-Zahl ist, gilt F_(m,p) >=F_m =>(m,p) >=m =>(m,p)= m (da der ggT zweier Zahlen nicht größer als eine von beiden sein kann) =>m\|p =>F_m \|F_p Die letzte Zeile stellt einen Widerspruch zu der Annahme F_m \teiltnicht F_p dar, damit existiert ein solches F_p nicht. Als nächstes wollen wir zeigen, dass zu jeder natürlichen Zahl m eine Fibonaccizahl F_q existiert, die durch m teilbar ist. Betrachten wir dazu die Folge der Fibonaccizahlen modulo m und nenne die Reste p_0, p_1, ... , wobei die Indizes denen der zugehörigen Fibo´s entsprechen sollen. Teilen wir diese p´s in Paare auf: (p_0 ,p_1 ), (p_1 ,p_2 ), (p_2 ,p_3 ), ... Da es lediglich m^2 verschiedene Paare gibt, ist irgendwann für natürliche Zahlen i und j (p_j , p_(j+1))=(p_i , p_(i+1)). Nun ist p_(j-1)==p_(j+1)-p_j==p_(i+1)-p_i==p_(i-1) Also ist auch (p_(j-1) ,p_j )=(p_(i-1) ,p_i ) Mehrmalige Wiederholung dieses Vorgangs führt irgendwann auf (p_1 ,p_2 )=(p_k , p_(k+1)), woraus p_k =1 und p_(k+1) =1 folgt. Damit ist auch p_(k-1) =0 und somit gilt m\|F_(k-1) . Zum Schluss wollen wir den Wert der Folgenden Zahl bestimmen: p= 0,0 +0,01 +0,001 +0,0002 +0,00003 +0,000005 +0,0000008 +0,00000013 +0,000000021 +0,0000000034 +0,00000000055 ... --------------------- p=0,0112359549... Es ist: p=1/10 F_0 +(1/10)^2 F_1 +(1/10)^3 F_2 +(1/10)^4 F_3 +... p/10=(1/10)^2 F_0 +(1/10)^3 F_1 +(1/10)^4 F_2 +(1/10)^5 F_3 +... p/100=(1/10)^3 F_0 +(1/10)^4 F_1 +(1/10)^5 F_2 +(1/10)^6 F_3 +... Subtraktion der beiden unteren Gleichungen von der ersten und Anwendung der Definition bringt: p-p/10-p/100 = 1/10 F_0 + (1/10)^2 F_1 - (1/10)^2 F_0 =1/100 (wegen F_0 = 0 und F_1 = 1). Diese Gleichung ist äquivalent zu p=1/89.
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Fibonacci-Zahlen :: Schüler aufwärts :
Sätze über Teilbarkeiten bei Fibonaccizahlen  
Eine Mitschrift von einem Vortrags eines Mathewochenendes. Der Artikel behandelt Fibonaccizahlen, mit dem Schwerpunkt bei Teilbarkeitsfragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5222
 
Aufrufstatistik des Artikels
Insgesamt 1014 externe Seitenaufrufe zwischen 2012.01 und 2022.05 [Anzeigen]
DomainAnzahlProz
https://google.com272.7%2.7 %
https://matheplanet.com10.1%0.1 %
https://google.de35234.7%34.7 %
http://google.de44543.9%43.9 %
http://google.fr323.2%3.2 %
http://google.pl494.8%4.8 %
https://duckduckgo.com262.6%2.6 %
http://google.se272.7%2.7 %
https://www.bing.com161.6%1.6 %
https://google.lu141.4%1.4 %
https://www.startpage.com60.6%0.6 %
http://google.com30.3%0.3 %
http://avira.search.ask.com20.2%0.2 %
https://www.ecosia.org30.3%0.3 %
http://google.ch30.3%0.3 %
http://search.conduit.com10.1%0.1 %
http://www.bing.com30.3%0.3 %
http://google.at10.1%0.1 %
http://duckduckgo.com10.1%0.1 %
http://www.fabianmeier.de10.1%0.1 %
https://startpage.com10.1%0.1 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 12 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.05.02-2022.05.25 (12x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 965 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2022 (274x)https://google.de/
2012-2018 (194x)http://google.de/url?sa=t&rct=j&q=
202006-06 (46x)https://google.de/search?q=fibonacci zahlen teilbarkeit
201411-11 (45x)http://google.de/url?sa=t&source=web&cd=6&ved=0CCwQFjAF
201305-05 (33x)http://google.de/url?sa=t&rct=j&q=teilbarkeit fibonacci zahlen
201211-11 (32x)http://google.fr/url?sa=t&rct=j&q=f_{m+n} = f_{n+1} ; f_m + f_n ; f_{m-1} bew...
201205-05 (27x)http://google.pl/url?sa=t&rct=j&q=fibonacci zahlen teilbarkeit durch 2012
2020-2022 (24x)https://duckduckgo.com/
201302-10 (23x)http://google.de/url?sa=t&rct=j&q=fibonacci zahlen teilbarkeit
202005-05 (23x)https://google.de/url?sa=t
201304-04 (23x)http://google.de/url?sa=t&rct=j&q=zeige dass es fibonacci zahlen sind
201210-10 (23x)http://google.se/url?sa=t&rct=j&q=fibonacci ggt teilerfremd
201401-01 (22x)http://google.de/url?sa=t&rct=j&q=fibonacci teilbarkeit beweis
201404-04 (22x)http://google.pl/url?sa=t&rct=j&q=
201204-04 (18x)http://google.de/url?sa=t&rct=j&q=zwei aufeinander folgende fibonaccizahlen t...
2021-2022 (16x)https://www.bing.com/
2020-2022 (15x)https://google.com/
202201-01 (14x)https://google.lu/
2012-2013 (14x)http://google.de/url?sa=t&rct=j&q=zwei aufeinanderfolgende fibonacci zahlen t...
201402-02 (13x)http://google.de/url?sa=t&rct=j&q=sätze mit wort teilbar
201303-03 (9x)http://google.de/url?sa=t&rct=j&q=teilbarkeitsregeln fibonacci
201203-03 (9x)http://google.de/url?sa=t&rct=j&q=sätze über teilbarkeiten
2020-2021 (8x)https://google.de
201201-01 (7x)http://google.de/url?sa=t&rct=j&q=fibonaccizahlen teilerfremd
201206-06 (6x)http://google.de/url?sa=t&rct=j&q=teilbarkeit von zahlen-teilbarkeitsregeln
2020-2021 (6x)https://www.startpage.com/
2016-2017 (6x)http://google.de/
201505-05 (5x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCAQFjAB
201602-02 (4x)http://google.de/url?sa=t&source=web&cd=1&rct=j&q=beweis fibonacci zahl durch...
201209-09 (4x)http://google.se/url?sa=t&rct=j&q=aufeinanderfolgende fibonacci zahlen teiler...

[Top of page]

"Mathematik: Sätze über Teilbarkeiten bei Fibonaccizahlen" | 10 Comments
The authors of the comments are responsible for the content.

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: matroid am: Do. 07. Juni 2007 20:14:03
\(\begingroup\) \ Hi robbe, Fibonaccizahlen sind wirklich ein schönes und vielfältiges Gebiet. Das hast Du hier gut dargestellt. Zum letzten Ergebnis: Statt für x=1/10 kann man allgemein formulieren: f(x):=sum(F_n*x^n,n=0,\inf) =F_0+F_1*x+sum(F_n*x^n,n=2,\inf) =F_0+F_1*x+sum((F_(n-1)+F_(n-2))*x^n,n=2,\inf) =F_0+F_1*x+sum(F_(n-1)*x^n,n=2,\inf)+sum(F_(n-2)*x^n,n=2,\inf) =F_0+F_1*x+sum(F_n*x^(n+1),n=1,\inf)+sum(F_n*x^(n+2),n=0,\inf) =F_0+F_1*x+x*sum(F_n*x^n,n=1,\inf)+x^2*sum(F_n*x^n,n=0,\inf) bigop(=,,\red\ denn F_0=0 \black)=F_1*x+x*sum(F_n*x^n,n=0,\inf)+x^2*sum(F_n*x^n,n=0,\inf) => f(x)=x+x*f(x)+x^2*f(x) => f(x)=x/(1-x-x^2) Das nennt man die erzeugende Funktion der Fibonaccizahlen. Und wenn man, wie in Deinem Artikel sucht: sum(F_n*x^(n+1),n=0,\inf)=x*f(x), so ergibt sich für x=1/10 gerade 1/89. Gruß Matroid \(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: kostja am: Do. 07. Juni 2007 22:06:28
\(\begingroup\) \ Hallo Martin, irgendetwas erscheint mir daran ziemlich merkwürdig. Alle Fibonaccizahlen F_n \(für n>1\) sind > 1 und monoton steigend. Das heißt aber, dass die Summe sum(F_n x^n,n=0,\inf) für x \to \inf divergiert. Wie kommt es aber, dass f(x) \to 0, für x \to \inf? MfG Konstantin \(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: owk am: Do. 07. Juni 2007 22:42:23
\(\begingroup\)Außerhalb des Konvergenzbereiches ist die Reihe divergent, das hat mit dem Verhalten der zugehörigen Funktion dort extrem wenig zu tun. Das gilt aber auch schon für einfachere Beispiele wie 1/(1−x) bei x=2. owk\(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: kostja am: Do. 07. Juni 2007 23:26:43
\(\begingroup\)Ah! Natürlich. Danke. Es ist einfach schon spät. ☹️ Guten Abend Konstantin\(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: robbe am: Fr. 08. Juni 2007 14:27:09
\(\begingroup\)Hallo matroid! Danke für die schöne Verallgemeinerung! =) Die war mir unbekannt, aber es war auch meine erste Auseinandersetzung mit Fibonaccizahlen... Kennt jemand evtl. gute Internetseiten wo das Thema weiter vertieft wird? robbe\(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: matroid am: Sa. 09. Juni 2007 10:18:07
\(\begingroup\)Es gibt sicher noch mehr, aber ein paar Links sind hier search.php?type=links&query=fibonacci&orderby=dateD gesammelt. Übrigens, aus \stress(Satz B: (F_m, F_n)=F_(m,n)) \normal\ folgt u.a. auch die Lösung der beliebten Aufgabe: \blue\ Zeige, daß zwei aufeinanderfolgende Fibonaccizahlen teilerfremd sind. Gruß Matroid\(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: portnoy am: Sa. 09. Juni 2007 23:34:44
\(\begingroup\)"Außerhalb des Konvergenzbereiches ist die Reihe divergent" Bin mit dem Thema nicht sehr vertraut, aber ist das nicht eine Tautologie? Habe mal ein wenig mit x gespielt (Mathematica) und es scheint, als ob die Reihe für alle positiven x<1/Phi konvergiert (Phi = Goldenes Verhältnis). Wie aber kann die Reihe dann für x->inf konvergieren?\(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: portnoy am: Sa. 09. Juni 2007 23:52:12
\(\begingroup\)Ok, habe mir Matroids Beitrag nochmal ordentlich durchgelesen. Schöne Herleitung. Das Ergebnis ist dennoch sehr erstaunlich, wenn man nur die ursprüngliche Summe betrachtet.\(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: matroid am: So. 10. Juni 2007 09:22:54
\(\begingroup\) \ Das Quotienkriterium sagt: wenn lim(n->\inf,F_(n+1)/F_n*x)=q<1, dann konvergiert die Reihe sum(F_n*x^n,n=0,\inf). Betrachte den Quotienten: F_(n+1)/F_n=(F_n+F_(n-1))/F_n=1+F_(n-1)/F_n Wenn lim F_(n+1)/F_n =: c >0, dann ist lim F_(n-1)/F_n = 1/c. Dann gilt also: c = 1 +1/c und man löst auf c^2-c-1=0 Lösungen sind c_1,2=(1+-sqrt(5))/2. Die positive Lösung ist \phi=(1+sqrt(5))/2~=1.618033989 Nach dem Quotientenkriterium konvergiert die Reihe für x*\phi=q<1. Das sichert mindestens die Konvergenz für abs(x)<0.618033989, denn 1/1.618033989=0.618033989. Das ist genau, was Du auch festgestellt hast @portnoy. \small\Es ist das gerade die charakteristische Eigenschaft aus c = 1 +1/c: "der Kehrwert ist um 1 größer als der Wert". \(\endgroup\)
 

Re: Sätze über Teilbarkeiten bei Fibonaccizahlen
von: matroid am: So. 10. Juni 2007 11:12:03
\(\begingroup\) \ Noch ein Nachtrag: oben hatte ich gesagt: 'wenn die Quotientenfolge konvergiert, dann ist der Grenzwert \phi2 '. Nun muß man aber auch zeigen, daß die Quotientenfolge konvergiert. Da gibt z.B. Fabi im Forum den Beweis, hier: Konvergenz und Fibonacci-Folge Bei der Gelegenheit: gerade lese ich einen Beitrag von Buri im Thread Bruch zwischen 2/3 und 3/4 gesucht. Was er dort schreibt kann man gut brauchen: \frameon\boxon\blue\ Wenn a,b,c,d positive Zahlen mit a/b\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]