Fibonacci-Folgen und Lucas-Folgen: Die allgemeine Lucas-Folge

Fibonacci-Folgen und Lucas-Folgen

Einleitung

Hier geht es um 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 Folgen mit den Anfangswerten

$U_{0}=0,\quad U_{1}=1\$ und

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

und der Rekursionsformel

$U_{n}=PU_{n-1}-QU_{n-2}\$ für $n>1\$ (entsprechend für $V_{n}\$).

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

Explizite Formeln

Vorbereitung

Die allgemeine Lucas-Folge hat zum einen mit quadratischen Gleichungen zu tun, und andererseits ist es zum Verständnis von Vorteil, ableiten (Differentialrechnung) zu können.

Für die expliziten Formeln werden die beiden Lösungen $a$ und $b$ der quadratischen Gleichung $x^{2}-Px+Q=0\$ benötigt. Sie sind

$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}}$

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 auch verallgemeinern:

$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\neq 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\geq 0$. Im Spezialfall $P^{2}-4Q=0$ gilt stattdessen

$U_{n}(P,Q)=na^{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\geq 0$

Wenn man die ganze Folge meint, und nicht nur das einzelne Glied der Folge, dann läßt sich dieses so ausdrücken:

$U(P,Q)=(U_{n}(P,Q))_{n\geq 1}$ bzw. $V(P,Q)=(V_{n}(P,Q))_{n\geq 1}$

U₀, U₁ und V₀ sind definiert

$U_{0}(P,Q),\ U_{1}(P,Q)\$ und $V_{0}(P,Q)\$ hängen nicht von $a\$ und $b\$, und damit auch nicht von $P\$ und $Q\$, ab.

$U_{0}={\frac {a^{0}-b^{0}}{a-b}}={\frac {1-1}{a-b}}={\frac {0}{a-b}}=0$

$U_{1}={\frac {a^{1}-b^{1}}{a-b}}={\frac {a-b}{a-b}}={\frac {1}{1}}=1$

$V_{0}=a^{0}+b^{0}=1+1=2\$

$V_{1}(P,Q)\$ nimmt den Wert von $P\$ an, da nach der Satzgruppe von Vieta gilt $P=a+b\$:

$V_{1}=a^{1}+b^{1}=a+b=P\$

Beziehungen zwischen den Folgegliedern

Es gibt viele Beziehungen zwischen den Gliedern der allgemeinen Lucas-Folgen $U(P,Q)\$ und $V(P,Q)\$. Da die Fibonacci-Folge, und auch die Lucas-Folge (2, 1, 3, 4, 7, ...) Teil der allgemeinen Lucas-Folge sind, gelten diese Beziehungen auch für diese beiden Folgen. Gleiches trifft auch auf die Pell-Folge und ihre Companion-Folge zu.

Da man bei diesen Beziehungen davon ausgehen kann, dass die Parameter $P\$ und $Q\$ für alle Glieder der Folgen identisch sind, lässt man sie weg. Statt $V(P,Q)_{2n}=V(P,Q)_{n}^{2}-2Q^{n}\$ reicht es aus $V_{2n}=V_{n}^{2}-2Q^{n}\$ zu schreiben.

• $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}\neq 1$

_{Quelle: Ein großer Teil dieses Kapitels stammt aus dem Artikel Lucas-Folgen von der deutschsprachigen de.wikipedia.org.}