Lucas-Folge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 U_n(P,Q) und V_n(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 U_n die Folge der Fibonacci-Zahlen, V_n 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[Bearbeiten]

Vorbereitung[Bearbeiten]

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 P^2-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 voneinander 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[Bearbeiten]

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 P^2-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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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)[Bearbeiten]

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)[Bearbeiten]

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[Bearbeiten]

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

1) Wie im allgemeinen Fall für die Folgen V_n 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 \Phi.

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

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

3) Als Summe zweier Glieder der Fibonacci-Folge:

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

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

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

Literatur[Bearbeiten]

Weblinks[Bearbeiten]