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, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, … (Folge A000032 in OEIS)

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$ als diejenigen Folgen definiert sind, die

$U_0=0,U_1=1$ bzw. $V_0=2,V_1=P$

erfüllen und den Rekursionsformeln

$U_n=P{U}_{n-1}-Q{U}_{n-2}$ bzw. $V_n=P{V}_{n-1}-Q{V}_{n-2}$

für $n>1$ genügen.

Die Lucas-Folgen sind nach dem französischen Mathematiker Édouard Lucas benannt, der sich als erster mit ihnen beschäftigt hat.

Beispiele

• Sei $P=1$ und $Q=-1$. Dann ist $U_n(P,Q)=U_n(1,-1)$ die folgende Folge:

$U_0=0,U_1=1,$

$U_2=P{U}_1-Q{U}_0=1\cdot 1-(-1)\cdot 0=1,$

$U_3=P{U}_2-Q{U}_1=1\cdot 1-(-1)\cdot 1=2,$

$U_4=P{U}_3-Q{U}_2=1\cdot 2-(-1)\cdot 1=3,$

$U_5=P{U}_4-Q{U}_3=1\cdot 3-(-1)\cdot 2=5,\dots$

Kurz geschrieben erhält man die Fibonacci-Folge:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, … (Folge A000045 in OEIS)

• Sei $P=1$ und $Q=-1$. Dann ist $V_n(P,Q)=V_n(1,-1)$ die folgende Folge:

$V_0=2,V_1=P=1,$

$V_2=P{V}_1-Q{V}_0=1\cdot 1-(-1)\cdot 2=3,$

$V_3=P{V}_2-Q{V}_1=1\cdot 3-(-1)\cdot 1=4,$

$V_4=P{V}_3-Q{V}_2=1\cdot 4-(-1)\cdot 3=7,$

$V_5=P{V}_4-Q{V}_3=1\cdot 7-(-1)\cdot 4=11,\dots$

Kurz geschrieben erhält man eine Folge, die man ebenfalls kurz spezielle Lucas-Folge (oder noch einfacher nur Lucas-Folge) nennt, nämlich:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, … (Folge A000032 in OEIS)

Die einzelnen Zahlen dieser Folge nennt man Lucas-Zahlen, auf die weiter unten näher eingegangen wird.

• In einer Tabelle zusammengefasst erhält man für gewisse Startwerte für $P$ und $Q$ die Tabelle im Abschnitt Spezialfälle.

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,Q=a\cdot b.$ (Satz 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\ne 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\ge 0$. Im Spezialfall $P^2-4Q=0$ gilt stattdessen

$U_n(P,Q)=n{a}^{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\ge 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}-Q{U}_{n-1}$
• $V_{2n}=V_n^2-2Q^n$
• $\mathrm{ggT}(U_m,U_n)=U_{\mathrm{ggT}(m,n)}$, falls $\mathrm{ggT}(P,Q)=1$
• $m\mid n⟹U_m\mid U_n$; für alle $U_m\ne 1$

Spezialfälle

Es folgen ein paar Spezialfälle, die zu Folgen führen, die in der Mathematik eine wichtige Rolle spielen und deswegen sogar eigene Namen haben:

$P$	$Q$	$a$	$b$	$U(P,Q)$	$V(P,Q)$
$1$	$-1$	$\frac{1+\sqrt{5}}{2}$	$\frac{1-\sqrt{5}}{2}$	$0,1,1,2,3,5,8,13,21,34,\dots$ (Folge A000045 in OEIS) (Fibonacci-Folge)	$2,1,3,4,7,11,18,29,47,76,\dots$ (Folge A000032 in OEIS) ((spezielle) Lucas-Folge)
$1$	$-2$	$2$	$-1$	$0,1,1,3,5,11,21,43,85,171,\dots$ (Folge A001045 in OEIS) (Jacobsthal-Folge)	$2,1,5,7,17,31,65,127,257,511,\dots$ (Folge A014551 in OEIS) (Jacobsthal-Lucas-Folge)
$2$	$-1$	$1+\sqrt{2}$	$1-\sqrt{2}$	$0,1,2,5,12,29,70,169,408,985,\dots$ (Folge A000129 in OEIS) (Pell-Folge)	$2,2,6,14,34,82,198,478,1154,2786,\dots$ (Folge A002203 in OEIS) (Companion Pell-Folge, Pell-Lucas-Folge)
$3$	$2$	$2$	$1$	$0,1,3,7,15,31,63,127,255,511,\dots$ (Folge A000225 in OEIS) (Mersenne-Zahl-Folge)	$2,3,5,9,17,33,65,129,257,513,\dots$ (Folge A000051 in OEIS) (Zahlen der Form $2^n+1$ (enthalten die Fermat-Zahlen))
$A$	$-1$	$\frac{A+\sqrt{A^2+4}}{2}$	$\frac{A-\sqrt{A^2+4}}{2}$	Fibonacci-Polynome	Lucas-Polynome
$2A$	$1$	$A+\sqrt{A^2-1}$	$A-\sqrt{A^2-1}$	Tschebyschow-Polynome zweiter Art	Tschebyschow-Polynome erster Art, mit $2$ multipliziert
$A+1$	$A$	$A$	$1$	$a_i=1+a_{i-1}\cdot A$ mit $a_0=0$ Repunits zur Basis A	$(A^n+1)$ -Folge

Es gibt aber auch viele weitere Spezialfälle, die zu Folgen führen, die einen OEIS-Eintrag haben und somit in der Mathematik ebenfalls eine gewisse Rolle spielen. Es folgen ein paar Beispiele:

$P$	$Q$	$a$	$b$	$U(P,Q)$	$V(P,Q)$
$1$	$1$			$0,1,1,0,-1,-1,0,1,1,0,\dots$ (Folge A128834 in OEIS)	$2,1,-1,-2,-1,1,2,1,-1,-2,\dots$ (Folge A087204 in OEIS)
$1$	$2$			$0,1,1,-1,-3,-1,5,7,-3,-17,\dots$ (Folge A107920 in OEIS)	$2,1,-3,-5,1,11,9,-13,-31,-5,\dots$ (Folge A002249 in OEIS)
$2$	$1$	$1$	$1$	$0,1,2,3,4,5,6,7,8,9,\dots$ (Folge A001477 in OEIS)	$2,2,2,2,2,2,2,2,2,2,\dots$ (Folge A007395 in OEIS)
$2$	$2$			$0,1,2,2,0,-4,-8,-8,0,16,\dots$ (Folge A009545 in OEIS)	$2,2,0,-4,-8,-8,0,16,32,32,\dots$ (Folge A009545 in OEIS)
$2$	$3$			$0,1,2,1,-4,-11,-10,13,56,73,\dots$ (Folge A088137 in OEIS)	$2,2,-2,-10,-14,2,46,86,34,-190,\dots$
$2$	$4$			$0,1,2,0,-8,-16,0,64,128,0,\dots$ (Folge A088138 in OEIS)	$2,2,-4,-16,-16,32,128,128,-256,-1024,\dots$
$2$	$5$			$0,1,2,-1,-12,-19,22,139,168,-359,\dots$ (Folge A045873 in OEIS)	$2,2,-6,-22,-14,82,234,58,-1054,-2398,\dots$
$3$	$-10$	$5$	$-2$	$0,1,3,19,87,451,2223,11179,55767,279091,\dots$ (Folge A015528 in OEIS)	$2,3,29,117,641,3093,15689,77997,390881,1952613,\dots$
$3$	$-5$			$0,1,3,14,57,241,1008,4229,17727,74326,\dots$ (Folge A015523 in OEIS)	$2,3,19,72,311,1293,5434,22767,95471,400248,\dots$ (Folge A072263 in OEIS)
$3$	$-4$	$4$	$-1$	$0,1,3,13,51,205,819,3277,13107,52429,\dots$ (Folge A015521 in OEIS)	$2,3,17,63,257,1023,4097,16383,65537,262143,\dots$ (Folge A201455 in OEIS)
$3$	$-3$			$0,1,3,12,45,171,648,2457,9315,35316,\dots$ (Folge A030195 in OEIS)	$2,3,15,54,207,783,2970,11259,42687,161838,\dots$ (Folge A172012 in OEIS)
$3$	$-2$			$0,1,3,11,39,139,495,1763,6279,22363,\dots$ (Folge A007482 in OEIS)	$2,3,13,45,161,573,2041,7269,25889,92205,\dots$ (Folge A206776 in OEIS)
$3$	$-1$			$0,1,3,10,33,109,360,1189,3927,12970,\dots$ (Folge A006190 in OEIS)	$2,3,11,36,119,393,1298,4287,14159,46764,\dots$ (Folge A006497 in OEIS)
$3$	$1$			$0,1,3,8,21,55,144,377,987,2584,\dots$ (Folge A001906 in OEIS)	$2,3,7,18,47,123,322,843,2207,5778,\dots$ (Folge A005248 in OEIS)
$3$	$5$			$0,1,3,4,-3,-29,-72,-71,147,796,\dots$ (Folge A0190959 in OEIS)	$2,3,-1,-18,-49,-57,74,507,1151,918,\dots$
$4$	$-5$	$5$	$-1$	$0,1,4,21,104,521,2604,13021,65104,325521,\dots$ (Folge A015531 in OEIS)	$2,4,26,124,626,3124,15626,78124,390626,1953124,\dots$ (Folge A087404 in OEIS)
$4$	$-3$			$0,1,4,19,88,409,1900,8827,41008,190513,\dots$ (Folge A015530 in OEIS)	$2,4,22,100,466,2164,10054,46708,216994,1008100,\dots$ (Folge A080042 in OEIS)
$4$	$-2$			$0,1,4,18,80,356,1584,7048,31360,139536,\dots$ (Folge A090017 in OEIS)	$2,4,20,88,392,1744,7760,34528,153632,683584,\dots$
$4$	$-1$			$0,1,4,17,72,305,1292,5473,23184,98209,\dots$ (Folge A001076 in OEIS)	$2,4,18,76,322,1364,5778,24476,103682,439204,\dots$ (Folge A014448 in OEIS)
$4$	$1$			$0,1,4,15,56,209,780,2911,10864,40545,\dots$ (Folge A001353 in OEIS)	$2,4,14,52,194,724,2702,10084,37634,140452,\dots$ (Folge A003500 in OEIS)
$4$	$2$			$0,1,4,14,48,164,560,1912,6528,22288,\dots$ (Folge A007070 in OEIS)	$2,4,12,40,136,464,1584,5408,18464,63040,\dots$ (Folge A056236 in OEIS)
$4$	$3$	$3$	$1$	$0,1,4,13,40,121,364,1093,3280,9841,\dots$ (Folge A003462 in OEIS)	$2,4,10,28,82,244,730,2188,6562,19684,\dots$ (Folge A034472 in OEIS)
$4$	$4$	$2$	$2$	$0,1,4,12,32,80,192,448,1024,2304,\dots$ (Folge A001787 in OEIS)	$2,4,8,16,32,64,128,256,512,1024,\dots$ (Folge A000079 in OEIS)
$5$	$-6$	$6$	$-1$	$0,1,5,31,185,1111,6665,39991,239945,1439671,\dots$ (Folge A015540 in OEIS)	$2,5,37,215,1297,7775,46657,279935,1679617,10077695,\dots$ (Folge A0274074 in OEIS)
$5$	$-3$			$0,1,5,28,155,859,4760,26377,146165,809956,\dots$ (Folge A015536 in OEIS)	$2,5,31,170,943,5225,28954,160445,889087,4926770,\dots$
$5$	$-2$			$0,1,5,27,145,779,4185,22483,120785,648891,\dots$ (Folge A015535 in OEIS)	$2,5,29,155,833,4475,24041,129155,693857,3727595,\dots$
$5$	$-1$			$0,1,5,26,135,701,3640,18901,98145,509626,\dots$ (Folge A052918 in OEIS)	$2,5,27,140,727,3775,19602,101785,528527,2744420,\dots$ (Folge A087130 in OEIS)
$5$	$1$			$0,1,5,24,115,551,2640,12649,60605,290376,\dots$ (Folge A004254 in OEIS)	$2,5,23,110,527,2525,12098,57965,277727,1330670,\dots$ (Folge A003501 in OEIS)
$5$	$4$	$4$	$1$	$0,1,5,21,85,341,1365,5461,21845,87381,\dots$ (Folge A002450 in OEIS)	$2,5,17,65,257,1025,4097,16385,65537,262145,\dots$ (Folge A052539 in OEIS)
$8$	$-9$	$9$	$-1$	$0,1,8,73,656,5905,53144,478297,4304672,38742049,\dots$ (Folge A015577 in OEIS)	$2,8,82,728,6562,59048,531442,4782968,43046722,387420488,\dots$

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 amodp$ gilt hier $V_p(a+1,a)\equiv V_1(a+1,a)modp$.

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 $\mathrm{\Phi }$.

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

   $L_{n+1}=\lfloor \frac{L_n(1+\sqrt{5})+1}{2}\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={\mathrm{\Phi }}^n+(1-\mathrm{\Phi }{)}^n$ schreiben. Da für $n>1$ der Betrag von $(1-\mathrm{\Phi }{)}^n$ stets kleiner 0,5 ist, ergibt sich die Eigenschaft, dass die $n$-te ($n>1$) Lucaszahl dem gerundeten Wert der Golden Zahl zur Potenz $n$ entspricht: $L_n=\lfloor {\mathrm{\Phi }}^n+\frac{1}{2}\rfloor$.

Reziproke Reihe

Der Grenzwert der absolut konvergierenden reziproken Reihe spezieller Lucas-Zahlen

• $\sum _{n=0}^{\mathrm{\infty }}\frac{1}{L_{2^n}}$

ist irrational.

Lucas-Primzahlen

Eine Lucas-Primzahl ist eine Lucas-Zahl, die prim ist. Die kleinsten Lucas-Primzahlen lauten:

2, 3, 7, 11, 29, 47, 199, 521, 2207, 3571, 9349, 3010349, 54018521, 370248451, 6643838879, 119218851371, 5600748293801, 688846502588399, 32361122672259149, 412670427844921037470771, … (Folge A005479 in OEIS)

Für diese Lucas-Primzahlen ist der Index $n$ von $L_n$ der folgende:

0, 2, 4, 5, 7, 8, 11, 13, 16, 17, 19, 31, 37, 41, 47, 53, 61, 71, 79, 113, 313, 353, 503, 613, 617, 863, 1097, 1361, 4787, 4793, 5851, 7741, 8467, 10691, 12251, 13963, 14449, 19469, 35449, 36779, 44507, 51169, 56003, 81671, 89849, 94823, 140057, 148091, 159521, 183089, 193201, 202667, 344293, 387433, 443609, 532277, 574219, 616787, 631181, 637751, 651821, 692147, 901657, 1051849, … (Folge A001606 in OEIS)

Beispiel:

Es ist $L_6=18$ und $L_5=11$. Somit ist $L_7=L_6+L_5=18+11=29\in \mathbb{\mathbb{P}}$ eine Primzahl. Tatsächlich taucht der Index $n=7$ in obiger Liste an der 5. Stelle auf, weil er zur fünftkleinsten Lucas-Primzahl $L_7=29$ führt.

Es gelten folgende zwei Eigenschaften für Lucas-Primzahlen:

• Wenn $L_n$ eine Primzahl ist, dann ist der Index $n$ entweder gleich $0$ oder eine selbst Primzahl oder eine Zweierpotenz.
• $L_{2^m}$ ist eine Primzahl für $m\in \{1,2,3,4\}$. Für keine anderen bekannten Werte von $m$ erhält man weitere Primzahlen.

Es wird vermutet, dass es unendlich viele Lucas-Primzahlen gibt.

Siehe auch

• Lucas-Folge - Artikel in der deutschen Wikipedia
• lineare Differenzengleichung - Artikel in der deutschen Wikipedia

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).