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 ${\displaystyle U_{n}(P,Q)}${\displaystyle U_{n}(P,Q)} und ${\displaystyle V_{n}(P,Q)}${\displaystyle V_{n}(P,Q)}, die abhängig von den Parametern ${\displaystyle P}${\displaystyle P} und ${\displaystyle Q}${\displaystyle Q} als diejenigen Folgen definiert sind, die

${\displaystyle U_{0}=0,\quad U_{1}=1}${\displaystyle U_{0}=0,\quad U_{1}=1} bzw. ${\displaystyle V_{0}=2,\quad V_{1}=P}${\displaystyle V_{0}=2,\quad V_{1}=P}

erfüllen und den Rekursionsformeln

${\displaystyle U_{n}=PU_{n-1}-QU_{n-2},円}${\displaystyle U_{n}=PU_{n-1}-QU_{n-2},円} bzw. ${\displaystyle V_{n}=PV_{n-1}-QV_{n-2},円}${\displaystyle V_{n}=PV_{n-1}-QV_{n-2},円}

für ${\displaystyle n>1}${\displaystyle 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.

• Sei ${\displaystyle P=1}${\displaystyle P=1} und ${\displaystyle Q=-1}${\displaystyle Q=-1}. Dann ist ${\displaystyle U_{n}(P,Q)=U_{n}(1,-1)}${\displaystyle U_{n}(P,Q)=U_{n}(1,-1)} die folgende Folge:

${\displaystyle U_{0}=0,U_{1}=1,}${\displaystyle U_{0}=0,U_{1}=1,}

${\displaystyle U_{2}=PU_{1}-QU_{0}=1\cdot 1-(-1)\cdot 0=1,}${\displaystyle U_{2}=PU_{1}-QU_{0}=1\cdot 1-(-1)\cdot 0=1,}

${\displaystyle U_{3}=PU_{2}-QU_{1}=1\cdot 1-(-1)\cdot 1=2,}${\displaystyle U_{3}=PU_{2}-QU_{1}=1\cdot 1-(-1)\cdot 1=2,}

${\displaystyle U_{4}=PU_{3}-QU_{2}=1\cdot 2-(-1)\cdot 1=3,}${\displaystyle U_{4}=PU_{3}-QU_{2}=1\cdot 2-(-1)\cdot 1=3,}

${\displaystyle U_{5}=PU_{4}-QU_{3}=1\cdot 3-(-1)\cdot 2=5,\ldots }${\displaystyle U_{5}=PU_{4}-QU_{3}=1\cdot 3-(-1)\cdot 2=5,\ldots }

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 ${\displaystyle P=1}${\displaystyle P=1} und ${\displaystyle Q=-1}${\displaystyle Q=-1}. Dann ist ${\displaystyle V_{n}(P,Q)=V_{n}(1,-1)}${\displaystyle V_{n}(P,Q)=V_{n}(1,-1)} die folgende Folge:

${\displaystyle V_{0}=2,V_{1}=P=1,}${\displaystyle V_{0}=2,V_{1}=P=1,}

${\displaystyle V_{2}=PV_{1}-QV_{0}=1\cdot 1-(-1)\cdot 2=3,}${\displaystyle V_{2}=PV_{1}-QV_{0}=1\cdot 1-(-1)\cdot 2=3,}

${\displaystyle V_{3}=PV_{2}-QV_{1}=1\cdot 3-(-1)\cdot 1=4,}${\displaystyle V_{3}=PV_{2}-QV_{1}=1\cdot 3-(-1)\cdot 1=4,}

${\displaystyle V_{4}=PV_{3}-QV_{2}=1\cdot 4-(-1)\cdot 3=7,}${\displaystyle V_{4}=PV_{3}-QV_{2}=1\cdot 4-(-1)\cdot 3=7,}

${\displaystyle V_{5}=PV_{4}-QV_{3}=1\cdot 7-(-1)\cdot 4=11,\ldots }${\displaystyle V_{5}=PV_{4}-QV_{3}=1\cdot 7-(-1)\cdot 4=11,\ldots }

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 ${\displaystyle P}${\displaystyle P} und ${\displaystyle Q}${\displaystyle Q} die Tabelle im Abschnitt Spezialfälle.

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 ${\displaystyle a}${\displaystyle a} und ${\displaystyle b}${\displaystyle b} der quadratischen Gleichung ${\displaystyle x^{2}-Px+Q=0\ }${\displaystyle x^{2}-Px+Q=0\ } benötigt. Es sind dies

${\displaystyle a={\frac {P}{2}}+{\sqrt {{\frac {P^{2}}{4}}-Q}}={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}}${\displaystyle a={\frac {P}{2}}+{\sqrt {{\frac {P^{2}}{4}}-Q}}={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}}

und

${\displaystyle b={\frac {P}{2}}-{\sqrt {{\frac {P^{2}}{4}}-Q}}={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}}${\displaystyle b={\frac {P}{2}}-{\sqrt {{\frac {P^{2}}{4}}-Q}}={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}}

Ist ${\displaystyle P^{2}-4Q<0}${\displaystyle P^{2}-4Q<0}, so ist eine der beiden komplexen Wurzeln zu wählen. Welche der beiden Zahlen ${\displaystyle a}${\displaystyle a} und welche ${\displaystyle b}${\displaystyle b} genannt wird, ist hierbei nicht von Belang.

Die Parameter ${\displaystyle P}${\displaystyle P} und ${\displaystyle Q}${\displaystyle Q} und die Werte ${\displaystyle a}${\displaystyle a} und ${\displaystyle b}${\displaystyle b} sind voneinander abhängig, es gilt umgekehrt

${\displaystyle P=a+b,\quad Q=a\cdot b.}${\displaystyle P=a+b,\quad Q=a\cdot b.} (Satz von Vieta)

Die Formeln für ${\displaystyle a}${\displaystyle a} und ${\displaystyle b}${\displaystyle b} lassen sich in Bezug auf die Potenzen verallgemeinern. Und zwar gilt:

${\displaystyle a^{n}={\frac {V_{n}+U_{n}{\sqrt {P^{2}-4Q}}}{2}},円}${\displaystyle a^{n}={\frac {V_{n}+U_{n}{\sqrt {P^{2}-4Q}}}{2}},円}

${\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {P^{2}-4Q}}}{2}},円}${\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {P^{2}-4Q}}}{2}},円}

Falls ${\displaystyle P^{2}-4Q\neq 0}${\displaystyle P^{2}-4Q\neq 0} gilt, oder äquivalent dazu: falls die Zahlen ${\displaystyle a}${\displaystyle a} und ${\displaystyle b}${\displaystyle b} verschieden sind, so berechnet sich das Glied der allgemeinen Lucas-Folge ${\displaystyle U_{n}(P,Q)\ }${\displaystyle U_{n}(P,Q)\ } nach folgender Formel:

${\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}}${\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}}

für alle ${\displaystyle n\geq 0}${\displaystyle n\geq 0}. Im Spezialfall ${\displaystyle P^{2}-4Q=0}${\displaystyle P^{2}-4Q=0} gilt stattdessen

${\displaystyle U_{n}(P,Q)=na^{n-1}=n\left({\frac {P}{2}}\right)^{n-1}.}${\displaystyle U_{n}(P,Q)=na^{n-1}=n\left({\frac {P}{2}}\right)^{n-1}.}

Das Glied der allgemeinen Lucas-Folge ${\displaystyle V_{n}(P,Q)\ }${\displaystyle V_{n}(P,Q)\ } berechnet sich nach folgender Formel:

${\displaystyle V_{n}(P,Q)=a^{n}+b^{n}\ }${\displaystyle V_{n}(P,Q)=a^{n}+b^{n}\ }

für alle ${\displaystyle n\geq 0}${\displaystyle n\geq 0}

Eine Auswahl der Beziehungen zwischen den Folgengliedern ist:^[1]

• ${\displaystyle U_{2n}=U_{n}\cdot V_{n}\ }${\displaystyle U_{2n}=U_{n}\cdot V_{n}\ }
• ${\displaystyle V_{n}=U_{n+1}-QU_{n-1}\ }${\displaystyle V_{n}=U_{n+1}-QU_{n-1}\ }
• ${\displaystyle V_{2n}=V_{n}^{2}-2Q^{n}\ }${\displaystyle V_{2n}=V_{n}^{2}-2Q^{n}\ }
• ${\displaystyle \operatorname {ggT} (U_{m},U_{n})=U_{\operatorname {ggT} (m,n)}}${\displaystyle \operatorname {ggT} (U_{m},U_{n})=U_{\operatorname {ggT} (m,n)}}, falls ${\displaystyle \operatorname {ggT} (P,Q)=1}${\displaystyle \operatorname {ggT} (P,Q)=1}
• ${\displaystyle m\mid n\implies U_{m}\mid U_{n}}${\displaystyle m\mid n\implies U_{m}\mid U_{n}}; für alle ${\displaystyle U_{m}\neq 1}${\displaystyle U_{m}\neq 1}

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:

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

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

Die allgemeinen Lucas-Folgen ${\displaystyle U(P,Q),円}${\displaystyle U(P,Q),円} und ${\displaystyle V(P,Q),円}${\displaystyle V(P,Q),円} haben für ganzzahlige Parameter ${\displaystyle P}${\displaystyle P} und ${\displaystyle Q}${\displaystyle 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]

Für alle Lucas-Folgen ${\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}}${\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}} gilt:

Ist p eine Primzahl, so ist ${\displaystyle U_{p}(P,Q)-\left({\frac {D}{p}}\right)}${\displaystyle U_{p}(P,Q)-\left({\frac {D}{p}}\right)} durch p teilbar.

Dabei ist ${\displaystyle \left({\frac {D}{p}}\right)}${\displaystyle \left({\frac {D}{p}}\right)} das Legendre-Symbol.

Es existieren auch zusammengesetzte Zahlen, die diese Bedingung erfüllen. Diese Zahlen nennt man Lucas-Pseudoprimzahlen.

Für alle Lucas-Folgen ${\displaystyle V_{n}(P,Q)=a^{n}+b^{n}\ }${\displaystyle V_{n}(P,Q)=a^{n}+b^{n}\ } gilt:

Ist p eine Primzahl, so ist ${\displaystyle V_{p}(P,Q)-P\ }${\displaystyle V_{p}(P,Q)-P\ } durch ${\displaystyle p}${\displaystyle p} teilbar.

Eine zusammengesetzte Zahl, die diese Bedingung (im Fall von ${\displaystyle P>0}${\displaystyle P>0} und ${\displaystyle Q=\pm 1}${\displaystyle Q=\pm 1}) erfüllt, heißt Fibonacci-Pseudoprimzahl.

Besonders interessant ist die Teilbarkeitsbedingung für die Folge ${\displaystyle V_{n}(3,2)=a^{n}+b^{n}=2^{n}+1\ }${\displaystyle V_{n}(3,2)=a^{n}+b^{n}=2^{n}+1\ }. Für diese Folge gilt nämlich:

Wenn ${\displaystyle n}${\displaystyle n} eine Primzahl ist, dann gilt: ${\displaystyle n}${\displaystyle n} teilt ${\displaystyle 2^{n}+1-3=2^{n}-2\ }${\displaystyle 2^{n}+1-3=2^{n}-2\ }.

Dies ist eine spezielle Form des kleinen Fermatschen Satz.

Analog zu ${\displaystyle a^{p}\equiv a\mod p}${\displaystyle a^{p}\equiv a\mod p} gilt hier ${\displaystyle V_{p}(a+1,a)\equiv V_{1}(a+1,a)\mod p}${\displaystyle V_{p}(a+1,a)\equiv V_{1}(a+1,a)\mod p}.

Die allgemein als Lucas-Folge bekannte Folge ${\displaystyle L_{n}}${\displaystyle L_{n}} der Lucas-Zahlen 2, 1, 3, 4, 7, 11, 18, 29, ... lässt sich außer durch die Rekursion ${\displaystyle L_{n}=L_{n-1}+L_{n-2}}${\displaystyle L_{n}=L_{n-1}+L_{n-2}} mit den Anfangswerten ${\displaystyle L_{0}=2}${\displaystyle L_{0}=2} und ${\displaystyle L_{1}=1}${\displaystyle L_{1}=1} auch wie folgt erzeugen:

1. Wie im allgemeinen Fall für die Folgen ${\displaystyle V_{n}}${\displaystyle V_{n}} erwähnt, über die Formel von Binet (nach Jacques Philippe Marie Binet):

   ${\displaystyle L_{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}${\displaystyle L_{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}, da ${\displaystyle a={\frac {1+{\sqrt {5}}}{2}}}${\displaystyle a={\frac {1+{\sqrt {5}}}{2}}} und ${\displaystyle b={\frac {1-{\sqrt {5}}}{2}}}${\displaystyle b={\frac {1-{\sqrt {5}}}{2}}} gilt. a ist übrigens die goldene Zahl ${\displaystyle \Phi }${\displaystyle \Phi }.

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

   ${\displaystyle L_{n+1}=\left\lfloor {\frac {L_{n}(1+{\sqrt {5}})+1}{2}}\right\rfloor }${\displaystyle L_{n+1}=\left\lfloor {\frac {L_{n}(1+{\sqrt {5}})+1}{2}}\right\rfloor }

3. Als Summe zweier Glieder der Fibonacci-Folge:

   ${\displaystyle L_{n}=f_{n-1}+f_{n+1}\ }${\displaystyle L_{n}=f_{n-1}+f_{n+1}\ } .

Nach 1) lässt sich alternativ auch ${\displaystyle L_{n}=\Phi ^{n}+(1-\Phi )^{n}}${\displaystyle L_{n}=\Phi ^{n}+(1-\Phi )^{n}} schreiben. Da für ${\displaystyle n>1}${\displaystyle n>1} der Betrag von ${\displaystyle (1-\Phi )^{n}}${\displaystyle (1-\Phi )^{n}} stets kleiner 0,5 ist, ergibt sich die Eigenschaft, dass die ${\displaystyle n}${\displaystyle n}-te (${\displaystyle n>1}${\displaystyle n>1}) Lucaszahl dem gerundeten Wert der Golden Zahl zur Potenz ${\displaystyle n}${\displaystyle n} entspricht: ${\displaystyle L_{n}=\left\lfloor {\Phi ^{n}+{\frac {1}{2}}}\right\rfloor }${\displaystyle L_{n}=\left\lfloor {\Phi ^{n}+{\frac {1}{2}}}\right\rfloor }.

Der Grenzwert der absolut konvergierenden reziproken Reihe spezieller Lucas-Zahlen

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

ist irrational.^[3]

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 ${\displaystyle n}${\displaystyle n} von ${\displaystyle L_{n}}${\displaystyle 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 ${\displaystyle L_{6}=18}${\displaystyle L_{6}=18} und ${\displaystyle L_{5}=11}${\displaystyle L_{5}=11}. Somit ist ${\displaystyle L_{7}=L_{6}+L_{5}=18+11=29\in \mathbb {P} }${\displaystyle L_{7}=L_{6}+L_{5}=18+11=29\in \mathbb {P} } eine Primzahl. Tatsächlich taucht der Index ${\displaystyle n=7}${\displaystyle n=7} in obiger Liste an der 5. Stelle auf, weil er zur fünftkleinsten Lucas-Primzahl ${\displaystyle L_{7}=29}${\displaystyle L_{7}=29} führt.

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

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

Es wird vermutet, dass es unendlich viele Lucas-Primzahlen gibt.^[4]

Die Artinsche Konstante, benannt nach Emil Artin, ist definiert durch

${\displaystyle C_{\mathrm {Artin} }=\prod _{p\ {\text{Primzahl}}}\left(1-{\frac {1}{p(p-1)}}\right)=\left(1-{\frac {1}{2\cdot 1}}\right)\left(1-{\frac {1}{3\cdot 2}}\right)\left(1-{\frac {1}{5\cdot 4}}\right)\cdots =0{,}3739558136\ldots .}${\displaystyle C_{\mathrm {Artin} }=\prod _{p\ {\text{Primzahl}}}\left(1-{\frac {1}{p(p-1)}}\right)=\left(1-{\frac {1}{2\cdot 1}}\right)\left(1-{\frac {1}{3\cdot 2}}\right)\left(1-{\frac {1}{5\cdot 4}}\right)\cdots =0{,}3739558136\ldots .}

Dabei bezeichnet ${\displaystyle \textstyle \prod }${\displaystyle \textstyle \prod } das Produktsymbol, wobei sich das Produkt über alle Primzahlen erstreckt. Die Konstante ${\displaystyle C_{\mathrm {Artin} }}${\displaystyle C_{\mathrm {Artin} }} taucht in einer tiefen Vermutung von Artin über die asymptotische Dichte von Primzahlen, die Primitivwurzeln zu einer gegebenen Zahl sind, auf.^[5] Eine Primitivwurzel zu einer Primzahl ${\displaystyle p}${\displaystyle p} ist eine ganze Zahl, deren Potenzen, bis auf Vielfache von ${\displaystyle p}${\displaystyle p}, alle Zahlen zwischen ${\displaystyle 1\leq n\leq p-1}${\displaystyle 1\leq n\leq p-1} erzeugen können. Zum Beispiel ist ${\displaystyle 3}${\displaystyle 3} eine Primitivwurzel bezüglich ${\displaystyle p=5}${\displaystyle p=5}, denn die ersten echten Potenzen der ${\displaystyle 3}${\displaystyle 3} sind ${\displaystyle 3,9,27,81}${\displaystyle 3,9,27,81} und bis auf Vielfache von ${\displaystyle 5}${\displaystyle 5} entspricht dies den Zahlen ${\displaystyle 3,4,2,1}${\displaystyle 3,4,2,1}. Die Artinsche Vermutung besagt, grob gesprochen, dass zu festem ${\displaystyle a}${\displaystyle a} die Menge der Primzahlen, so dass ${\displaystyle a}${\displaystyle a} eine Primitivwurzel zu ${\displaystyle p}${\displaystyle p} ist, die asymptotische Dichte ${\displaystyle C_{\mathrm {Artin} }}${\displaystyle C_{\mathrm {Artin} }} innerhalb aller Primzahlen hat. Also haben ca. 37 % der Primzahlen diese Eigenschaft, unabhängig von ${\displaystyle a}${\displaystyle a}. Jedoch muss ${\displaystyle a}${\displaystyle a} dafür bestimmte Voraussetzungen erfüllen.

Bezeichnet ${\displaystyle L_{n}}${\displaystyle L_{n}} die ${\displaystyle n}${\displaystyle n}-te Lucas-Zahl, so gilt die Formel

${\displaystyle C_{\mathrm {Artin} }=\prod _{n=2}^{\infty }\zeta (n)^{-{\frac {1}{n}}\sum _{k|n}L_{k}\mu \left({\frac {n}{k}}\right)}={\frac {1}{\zeta (2)\zeta (3)\zeta (4)\zeta (5)^{2}\zeta (6)^{2}\zeta (7)^{4}\zeta (8)^{5}\zeta (9)^{8}\cdots }}.}${\displaystyle C_{\mathrm {Artin} }=\prod _{n=2}^{\infty }\zeta (n)^{-{\frac {1}{n}}\sum _{k|n}L_{k}\mu \left({\frac {n}{k}}\right)}={\frac {1}{\zeta (2)\zeta (3)\zeta (4)\zeta (5)^{2}\zeta (6)^{2}\zeta (7)^{4}\zeta (8)^{5}\zeta (9)^{8}\cdots }}.}

Dabei bedeutet ${\displaystyle k|n}${\displaystyle k|n} in der Summe, dass ${\displaystyle k>0}${\displaystyle k>0} die Zahl ${\displaystyle n}${\displaystyle n} teilt, und es ist ${\displaystyle \mu }${\displaystyle \mu } die Möbiusfunktion sowie ${\displaystyle \zeta }${\displaystyle \zeta } die Riemannsche Zeta-Funktion.^[6]

• lineare Differenzengleichung

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

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

1. ↑ Siehe Ribenboim: Die Welt der Primzahlen, S. 44–70.
2. ↑ Siehe das schon angegebene Kapitel im Buch von Ribenboim.
3. ↑ Paulo Ribenboim: Meine Zahlen, meine Freunde: Glanzlichter der Zahlentheorie. Springer-Lehrbuch, 2009, ISBN 978-3-540-87955-8, S. 323.
4. ↑ ^{a b} Chris K. Caldwell: Lucas prime. Prime Pages, abgerufen am 1. März 2020 (englisch). 
5. ↑ S. R. Finch: Mathematical Constants, Encyclopedia of Mathematics and its Applications 94, Cambridge University Press, 2003, S. 104.
6. ↑ S. R. Finch: Mathematical Constants, Encyclopedia of Mathematics and its Applications 94, Cambridge University Press, 2003, S. 105.

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Lucas-Folge&oldid=227751911#Lucas-Primzahlen"

Kategorien:

• Folge ganzer Zahlen
• Ganzzahlmenge
• Primzahl
• Zahlentheorie

Versteckte Kategorie:

• Wikipedia:Wikidata P2812 verschieden