Das Kefk Network Wiki befindet sich im Testbetrieb.

Lucas-Folge

Aus Kefk.

Wechseln zu: Navigation, Suche

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 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 der Rekursionsformel
Un = PUn − 1 − QUn − 2 für n > 1
(entsprechend für Vn) 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 Edouard 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

  • 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 Un(P,Q), Vn(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: 

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\
  • Eine andere rekursive Formel: 
L_{n+1} = \left[\frac{L_n(1+\sqrt{5})+1}{2}\right]

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



Siehe auch

Literatur

Weblinks

Von „http://www.kefk.org/wiki/Lucas-Folge“
Persönliche Werkzeuge
Andere Sprachen