Lucas-Folge - LinkFang.de





Lucas-Folge


Unter der Lucas-Folge versteht man zwei unterschiedliche Dinge:

  • Einerseits die Folge der Lucas-Zahlen
2, 1, 3, 4, 7, 11, 18, 29, …
bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist.
  • Andererseits die beiden allgemeinen Lucas-Folgen [math]U_n(P,Q)[/math] und [math]V_n(P,Q)[/math], die abhängig von den Parametern [math]P[/math] und [math]Q[/math] definiert sind als diejenigen Folgen, die
[math]U_0=0,\quad U_1=1[/math] bzw. [math]V_0=2,\quad V_1=P[/math]
erfüllen und den Rekursionsformeln
[math]U_n=PU_{n-1}-QU_{n-2}\,[/math] bzw. [math]V_n=PV_{n-1}-QV_{n-2}\,[/math]
für n > 1 genügen.
Im Spezialfall [math]P=1[/math] und [math]Q=-1[/math] ist [math]U_n[/math] die Folge der Fibonacci-Zahlen, [math]V_n[/math] die oben definierte spezielle Lucas-Folge.

Die Lucas-Folgen sind nach dem französischen Mathematiker Édouard Lucas benannt, der sich als erster mit ihnen beschäftigt hat.

Explizite Formeln

Vorbereitung

Zur Bestimmung der Folgenglieder der allgemeinen Lucas-Folge muss vorbereitend die zugeordnete quadratische Gleichung gelöst werden.

Für die expliziten Formeln werden die beiden Lösungen [math]a[/math] und [math]b[/math] der quadratischen Gleichung [math]x^2-Px+Q=0\ [/math] benötigt. Es sind dies

[math]a = \frac{P}{2} + \sqrt{ \frac{P^2}{4} - Q} = \frac{P + \sqrt{P^2 - 4Q}}{2}[/math]

und

[math]b = \frac{P}{2} - \sqrt{ \frac{P^2}{4} - Q} = \frac{P - \sqrt{P^2 - 4Q}}{2}[/math]

Ist [math]P^2-4Q\lt0[/math], so ist eine der beiden komplexen Wurzeln zu wählen. Welche der beiden Zahlen [math]a[/math] und welche [math]b[/math] genannt wird, ist hierbei nicht von Belang.

Die Parameter [math]P[/math] und [math]Q[/math] und die Werte [math]a[/math] und [math]b[/math] sind voneinander abhängig, es gilt umgekehrt

[math]P=a+b,\quad Q=a\cdot b.[/math] (Satzgruppe von Vieta)

Die Formeln für a und b lassen sich in Bezug auf die Potenzen verallgemeinern. Und zwar gilt:

[math]a^n = \frac{V_n + U_n \sqrt{P^2-4Q}}{2}\,[/math]
[math]b^n = \frac{V_n - U_n \sqrt{P^2-4Q}}{2}\,[/math]

Die allgemeinen Lucas-Folgen

Falls [math]P^2-4Q\ne0[/math] gilt, oder äquivalent dazu: falls die Zahlen [math]a[/math] und [math]b[/math] verschieden sind, so berechnet sich das Glied der allgemeinen Lucas-Folge [math]U_n(P,Q)\ [/math] nach folgender Formel:

[math]U_n(P,Q)=\frac{a^n-b^n}{a-b}[/math]

für alle [math]n \ge 0[/math]. Im Spezialfall [math]P^2-4Q=0[/math] gilt stattdessen

[math]U_n(P,Q)=na^{n-1}=n\left(\frac P2\right)^{n-1}.[/math]

Das Glied der allgemeinen Lucas-Folge [math]V_n(P,Q)\ [/math] berechnet sich nach folgender Formel:

[math]V_n(P,Q)=a^n+b^n\ [/math]

für alle [math]n \ge 0[/math]

Beziehungen zwischen den Folgegliedern

Eine Auswahl der Beziehungen zwischen den Folgengliedern ist:[1]

  • [math]U_{2n} = U_n\cdot V_n\ [/math]
  • [math]V_n = U_{n+1} - QU_{n-1}\ [/math]
  • [math]V_{2n} = V_n^2 - 2Q^n\ [/math]
  • [math]\operatorname{ggT}(U_m,U_n)=U_{\operatorname{ggT}(m,n)}[/math], falls [math]\operatorname{ggT}(P,Q)=1[/math]
  • [math]m\mid n\implies U_m\mid U_n[/math]; für alle [math]U_m\ne 1[/math]

Spezialfälle

P Q a b U(P,Q) V(P,Q)
1 -1 [math]\frac{1+\sqrt{5}}{2}[/math] [math]\frac{1-\sqrt{5}}{2}[/math] Fibonacci-Folge Lucas-Folge
2 -1 [math]1+\sqrt{2}[/math] [math]1-\sqrt{2}[/math] Pell-Folge Companion Pell-Folge
1 -2 [math]\frac{1+\sqrt{9}}{2}[/math] [math]\frac{1-\sqrt{9}}{2}[/math] Jacobsthal-Folge
A+1 A A 1 ai = 1+ai-1·A mit a0=0 An+1 Folge
3 -10 5 -2 Folge A015528 in OEIS
4 -5 5 -1 Folge A015531 in OEIS
5 -6 6 -1 Folge A015540 in OEIS
8 -9 9 -1 Folge A015577 in OEIS

Die allgemeinen Lucas-Folgen U(P,Q), V(P,Q) und die Primzahlen

Die allgemeinen Lucas-Folgen [math]U(P,Q)\,[/math] und [math]V(P,Q)\,[/math] haben für ganzzahlige Parameter [math]P[/math] und [math]Q[/math] eine spezielle Eigenschaft hinsichtlich der Teilbarkeit durch Primzahlen. Diese Eigenschaft wurde für Verfahren zur Bestimmung der Primalität einer Zahl angewandt (siehe auch Lucas-Lehmer-Test).[2]

Die Folgen U(P,Q)

Für alle Lucas-Folgen [math]U_n(P,Q) = \frac{a^n - b^n}{a-b}[/math] gilt:

Ist p eine Primzahl, so ist [math]U_p(P,Q)-\left(\frac Dp\right)[/math] durch p teilbar.

Dabei ist [math]\left(\frac Dp\right)[/math] das Legendre-Symbol.

Es existieren auch zusammengesetzte Zahlen, die diese Bedingung erfüllen. Diese Zahlen nennt man Lucas-Pseudoprimzahlen.

Die Folgen V(P,Q)

Für alle Lucas-Folgen [math]V_n(P,Q) = a^n + b^n\ [/math] gilt:

Ist p eine Primzahl, so ist [math]V_p(P,Q) - P\ [/math] durch p teilbar.

Eine zusammengesetzte Zahl, die diese Bedingung (im Fall von P > 0 und [math]Q = \pm 1[/math]) erfüllt, heißt Fibonacci-Pseudoprimzahl.

Besonders interessant ist die Teilbarkeitsbedingung für die Folge [math]V_n(3,2) = a^n + b^n = 2^n+1\ [/math]. Für diese Folge gilt nämlich:

Wenn n eine Primzahl ist, dann gilt: n teilt [math]2^n+1-3 = 2^n-2\ [/math].

Dies ist eine spezielle Form des kleinen Fermatschen Satz.

Analog zu [math]a^p \equiv a \mod p[/math] gilt hier [math]V_p(a+1,a) \equiv V_1(a+1,a) \mod p[/math].

Die spezielle Lucas-Folge

Die allgemein als Lucas-Folge bekannte Folge [math]L_n[/math] der Lucas-Zahlen 2, 1, 3, 4, 7, 11, 18, 29, … lässt sich außer durch die Rekursion [math]L_n = L_{n-1} + L_{n-2}[/math] mit den Anfangswerten [math]L_0 = 2[/math] und [math]L_1 = 1[/math] auch wie folgt erzeugen:

1) Wie im allgemeinen Fall für die Folgen [math]V_n[/math] erwähnt, über die Formel von Binet (nach Jacques Philippe Marie Binet):

[math]L_n = \left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n[/math],

da [math]a= \frac{1 + \sqrt{5}}{2}[/math] und [math]b= \frac{1 - \sqrt{5}}{2}[/math] gilt. a ist übrigens die goldene Zahl [math]\Phi[/math].

2) Eine andere rekursive Formel (mit Gaußklammer):

[math]L_{n+1} = \left\lfloor\frac{L_n(1+\sqrt{5})+1}{2}\right\rfloor[/math]

3) Als Summe zweier Glieder der Fibonacci-Folge:

[math]L_n = f_{n-1} + f_{n+1}\ [/math] .

Nach 1) lässt sich alternativ auch [math]L_n = \Phi^n + (1 - \Phi)^n[/math] schreiben. Da für n > 1 der Betrag von [math](1 - \Phi)^n[/math] stets kleiner 0,5 ist, ergibt sich die Eigenschaft dass die n-te (n > 1) Lukaszahl dem gerundeten Wert der Golden Zahl zur Potenz n entspricht: [math]L_n = \left\lfloor{\Phi^n + \frac12}\right\rfloor[/math].

Siehe auch

Einzelnachweise

  1. Siehe Ribenboim: Die Welt der Primzahlen, S. 44–70.
  2. Siehe das schon angegebene Kapitel im Buch von Ribenboim.

Literatur

Weblinks


Kategorien: Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Lucas-Folge (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.