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² − 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 P² − 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 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₀ = 2 und L₁ = 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 Φ.

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

• lineare Differenzengleichung

Einzelnachweise

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

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)