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-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 der Rekursionsformel

U_n = PU_{n − 1} − QU_{n − 2} für n > 1

(entsprechend für V_n) 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

• $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	$a_i = 1+a_{i-1}\cdot A$ mit $a_0=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 allgemeine Lucas-Folgen U_n(P,Q), V_n(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 bei bestimmten Verfahren zur Bestimmung der Primalität einer Zahl angewandt. Leider waren diese Verfahren für bestimmte Arten von Pseudoprimzahlen anfällig.

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.

V(P,Q)

Für alle Lucas-Folgen $V_n(P,Q) = a^n + b^n\$ gilt: wenn $n\$ eine Primzahl ist, dann ist $(V_n(P,Q) - P)\$ durch $n\$ teilbar. Oder, anders ausgedrückt:

$V_n(P,Q) \equiv P \mod n$

für alle $n\$, die Primzahlen sind. Zusammengesetzte Zahlen die diese Bedingung erfüllen, mit der Einschränkung das $P\$ positiv und $Q\$ entweder 1 oder -1 ist, nennt man Fibonacci-Pseudoprimzahlen.

Der kleine Fermatsche Satz

Besonders interessant ist dies 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 also $V_p(a+1,a) \equiv V_1(a+1,a) \mod p$

Anwendungen der allgemeinen Lucas-Folgen

Die allgemeinen Lucas-Folgen spielen in der Zahlentheorie und der Kryptographie eine Rolle.

Siehe auch: Lucas-Lehmer-Test, Lucassche Pseudoprimzahl, Fibonacci-Folge, Jacobsthal-Folge, Pell-Folge

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 auf unterschiedlichste Art und Weise erzeugen:

• Ü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$
die sich aus der allgemeinen Lucas-Folge Ln = Vn( − 1,1) = an + bn mit a = $\frac{1 + \sqrt{5}}{2}$ und b = $\frac{1 - \sqrt{5}}{2}$ ableiten lässt

• Über die rekursive Formel, die der rekursiven Formel für die Fibonacci-Folge gleicht:

$L_n = L_{n-1} + L_{n-2}\$ mit den Anfangswerten $L_0 = 2\$ und $L_1 = 1\$

• Über eine Potenz des goldenen Schnitt:

$L_n = \Phi^n + \Psi^n\$

• Eine andere rekursive Formel:

$L_{n+1} = \left[\frac{L_n(1+\sqrt{5})+1}{2}\right]$

• Als Summe zweier Glieder der Fibonacci-Folge:

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

Siehe auch

• lineare Differenzengleichung

Literatur

• Paulo Ribenboim: The new Book of Primenumber Records, ISBN 0-387-94457-5.
• Paulo Ribenboim: My Numbers, my Friends, ISBN 0-387-98911-0.

Weblinks

• Lucas-Folgen in der Mathworld
• Lucas-Zahlen in der Mathworld