Lucas-Folge

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 Un(P,Q) und Vn(P,Q), die abhängig von den Parametern P und Q definiert sind als diejenigen Folgen, die
U_0=0,\quad U_1=1 bzw. V_0=2,\quad V_1=P
erfüllen und den Rekursionsformeln
U_n=PU_{n-1}-QU_{n-2}\, bzw. V_n=PV_{n-1}-QV_{n-2}\,
für n > 1 genügen.
Im Spezialfall P = 1 und Q = − 1 ist Un die Folge der Fibonacci-Zahlen, Vn 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.

Inhaltsverzeichnis

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 a und b der quadratischen Gleichung x^2-Px+Q=0\ benötigt. Es sind dies

a = \frac{P}{2} + \sqrt{ \frac{P^2}{4} - Q} = \frac{P + \sqrt{P^2 - 4Q}}{2}

und

b = \frac{P}{2} - \sqrt{ \frac{P^2}{4} - Q} = \frac{P - \sqrt{P^2 - 4Q}}{2}

Ist P2 − 4Q < 0, so ist eine der beiden komplexen Wurzeln zu wählen. Welche der beiden Zahlen a und welche b genannt wird, ist hierbei nicht von Belang.

Die Parameter P und Q und die Werte a und b sind von einander abhängig, es gilt umgekehrt

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

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

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

Die allgemeinen Lucas-Folgen

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

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

für alle n \ge 0. Im Spezialfall P2 − 4Q = 0 gilt stattdessen

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

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

V_n(P,Q)=a^n+b^n\

für alle n \ge 0

Beziehungen zwischen den Folgegliedern

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

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

Spezialfälle

P Q a b U(P,Q) V(P,Q)
1 -1 \frac{1+\sqrt{5}}{2} \frac{1-\sqrt{5}}{2} Fibonacci-Folge Lucas-Folge
2 -1 1+\sqrt{2} 1-\sqrt{2} Pell-Folge Companion Pell-Folge
1 -2 \frac{1+\sqrt{9}}{2} \frac{1-\sqrt{9}}{2} 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 U(P,Q)\, und V(P,Q)\, haben für ganzzahlige Parameter P und Q 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 U_n(P,Q) = \frac{a^n - b^n}{a-b} gilt:

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

Dabei ist \left(\frac Dp\right) 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 V_n(P,Q) = a^n + b^n\ gilt:

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

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

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

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

Dies ist eine spezielle Form des kleinen Fermatschen Satz.

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

Die spezielle Lucas-Folge

Die allgemein als Lucas-Folge bekannte Folge Ln der Lucas-Zahlen 2, 1, 3, 4, 7, 11, 18, 29, … lässt sich außer durch die Rekursion Ln = Ln − 1 + Ln − 2 mit den Anfangswerten L0 = 2 und L1 = 1 auch wie folgt erzeugen:

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

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

da a= \frac{1 + \sqrt{5}}{2} und b= \frac{1 - \sqrt{5}}{2} gilt. a ist übrigens die goldene Zahl Φ.

2) Eine andere rekursive Formel:

L_{n+1} = \left[\frac{L_n(1+\sqrt{5})+1}{2}\right], wobei die eckige Klammer die Gauss-Klammer ist (abrunden).

3) Als Summe zweier Glieder der Fibonacci-Folge:

L_n = f_{n-1} + f_{n+1}\ .

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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lucas-Folgen — Unter der Lucas Folge versteht man zwei unterschiedliche Dinge: Einerseits die Folge 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… …   Deutsch Wikipedia

  • Lucas-Zahlen — Unter der Lucas Folge versteht man zwei unterschiedliche Dinge: Einerseits die Folge 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… …   Deutsch Wikipedia

  • Lucas Brandis — (* vor 1450 in Delitzsch bei Leipzig; † nach 1500 wahrscheinlich in Lübeck; auch Lukas Brandis geschrieben) war ein bedeutender Buchdrucker und Typograf der Inkunabelzeit, der hauptsächlich in Merseburg, Magdeburg und Lübeck tätig war.… …   Deutsch Wikipedia

  • Lucas di Grassi — Automobil /Formel 1 Weltmeisterschaft Nation: Brasilien …   Deutsch Wikipedia

  • Lucas [2] — Lucas, 1) Eduard, Pomolog, geb. 19. Juli 1816 in Erfurt, gest. 24. Juli 1882 in Reutlingen, erlernte seit 1831 im Luisium bei Dessau die Gärtnerei, übernahm 1840 die praktische Leitung des Botanischen Gartens in Regensburg und wurde 1843 Vorstand …   Meyers Großes Konversations-Lexikon

  • Lucas-Lehmer Test — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Lucas-Lehmer-Test — Ausschnitt von Seite 316 der Arbeit Théorie des Fonctions Numériques Simplement Périodiques von Édouard Lucas (1878) Der Lucas Lehmer Test ist ein Primzahltest für Mersenne Zahlen, das heißt für Zahlen der Form Mn = 2n − 1. Der Test wird im GIMPS …   Deutsch Wikipedia

  • Lucas-Carmichael-Zahl — Eine Lucas Carmichael Zahl ist eine zusammengesetzte, natürliche Zahl, die eine ähnliche Bedingung wie eine Carmichael Zahl erfüllt. Inhaltsverzeichnis 1 Definition 2 Beispiel 3 Die kleinsten Lucas Carmichael Zahlen 4 …   Deutsch Wikipedia

  • Lucas d' Achéry — Luc d’Achery (* 1609 in Saint Quentin; † 29. April 1685 in Paris) war ein bedeutender Bibliothekar und Historiker der Mauriner, der zahlreiche textkritische Editionen herausgab. Inhaltsverzeichnis 1 Leben 2 Werke (Auswahl) 3 Literatur …   Deutsch Wikipedia

  • Edouard Lucas — François Édouard Anatole Lucas (* 4. April 1842 in Amiens; † 3. Oktober 1891 in Paris) war ein französischer Mathematiker. Édouard Lucas Lucas studierte an der École normale superieure, arbeitete am Pariser Observatorium, war Mathematiklehrer am… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”