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 $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

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 $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

Falls $P^{2}-4Q\neq 0$ 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\geq 0$. Im Spezialfall $P^{2}-4Q=0$ gilt stattdessen

$U_{n}(P,Q)=na^{n-1}=n\left({\frac {P}{2}}\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\geq 0$

Beziehungen zwischen den Folgegliedern

Eine Auswahl der Beziehungen zwischen den Folgengliedern ist:

• $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)}$, falls $\operatorname {ggT} (P,Q)=1$
• $m\mid n\implies U_{m}\mid U_{n}$; für alle $U_{m}\neq 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).

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 {D}{p}}\right)$ durch p teilbar.

Dabei ist $\left({\frac {D}{p}}\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 $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}\$ .

Nach 1) lässt sich alternativ auch $L_{n}=\Phi ^{n}+(1-\Phi )^{n}$ schreiben. Da für n > 1 der Betrag von $(1-\Phi )^{n}$ 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: $L_{n}=\left\lfloor {\Phi ^{n}+{\frac {1}{2}}}\right\rfloor$.

Siehe auch

• lineare Differenzengleichung

Literatur

• Paulo Ribenboim: Die Welt der Primzahlen. Springer Verlag, 1996

Weblinks

• Eric W. Weisstein: Lucas Number. In: MathWorld (englisch).
• Eric W. Weisstein: Lucas Sequence. In: MathWorld (englisch).