Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Die Perrin-Folge

Über die vor allem zahlentheoretischen Eigenschaften der Perrin-Folge bietet die Wikipedia einen Artikel. Wir wollen die geschlossene Form dieser Zahlenfolge ausgehend von ihrer Differenzengleichung

a_n+3 = a_n+1 + a_n, mit a₀=3, a₁=0, a₂=2

herleiten. Sei P(x) die entsprechende erzeugende Funktion

$P(x)=\sum _{n\geq 0}a_{n}x^{n}=3+2x^{2}+3x^{3}+2x^{4}+5x^{5}+\cdots$,

dann gilt

${\frac {P(x)-3-2x^{2}}{x^{3}}}={\frac {P(x)-3}{x}}+P(x)$

$\,P(x)-3-2x^{2}=x^{2}P(x)-3x^{2}+x^{3}P(x)$

$P(x)={\frac {3-x^{2}}{1-x^{2}-x^{3}}}$.

Seien z₁, z₂, z₃ die Lösungen der Gleichung 1-x²-x³=0, dann ist

$P(x)={\frac {3-x^{2}}{1-x^{2}-x^{3}}}={\frac {A}{x-z_{1}}}+{\frac {B}{x-z_{2}}}+{\frac {C}{x-z_{3}}}$.     (1)

Zunächst wollen wir eine asymptotische Abschätzung machen, weiter unten in diesem Kapitel werden wir aber eine Möglichkeit zur Bestimmung der A, B, C kennenlernen.

Das asymptotische Verhalten der Perrin-Folge

P(x) ist, wie in Gleichung (1) gesehen, die Summe dreier Brüche, deren Nenner x−z durch Division zu 1−x/z umgeformt werden kann. Der dabei entstehende Faktor 1/z von x entspricht der Konstanten c in einer unserer Potenzreihen-Identitäten, und daher können wir die Perrin-Zahlen als Summe dreier Potenzen, multipliziert mit jeweils einem unbekannten Faktor, darstellen:

$\,a_{n}=D(1/z_{1})^{n}+E(1/z_{2})^{n}+F(1/z_{3})^{n}$     (2)

Die drei Nullstellen z₁, z₂, z₃ des Nennerpolynoms von P(x) können mit Taschenrechner oder PC-Software (z.B. ein Computer-Algebra-System) numerisch erhalten werden:

• z₁ = 0,754877666
• z₂ = −0,877438833 − 0,744861767i
• z₃ = −0,877438833 + 0,744861767i

Egal, welche Faktoren D, E, F gelten, mit zunehmendem n wird sich derjenige Term durchsetzen, dessen Basis (1/z) den größten Betrag besitzt, und wird das asymptotische Verhalten bestimmen. Der Rechner liefert

• |1/z₁| = 1,324717917
• |1/z₂| = 0,868936862
• |1/z₃| = 0,868936862

und daher

$a_{n}\sim D\cdot 1.324717917^{n}$.     (3)

Partialbruchzerlegung durch Koeffizientenvergleich

Die Berechnung der Faktoren A, B, C in Gleichung (1) ist möglich durch folgendes Standardverfahren. Die Gleichung wird mit dem Nennerpolynom von P(x) multipliziert.

$\,3-x^{2}=A(x-z_{2})(x-z_{3})+B(x-z_{1})(x-z_{3})+C(x-z_{1})(x-z_{2})$

$\,3-x^{2}=A(x^{2}-z_{2}x-z_{3}x+z_{2}z_{3})+B(x^{2}-z_{1}x-z_{3}x+z_{1}z_{3})+C(x^{2}-z_{1}x-z_{2}x+z_{1}z_{2})$

Dies führt bei Berücksichtigung der jeweiligen Faktoren von 1, x und x² zu einem Gleichungssystem mit drei Unbekannten

${\begin{aligned}3&=z_{2}z_{3}A+z_{1}z_{3}B+z_{1}z_{2}C\\0&=(z_{2}+z_{3})A+(z_{1}+z_{3})B+(z_{1}+z_{2})C\\-1&=A+B+C\end{aligned}}$

mit der Lösung A=z₁, B=z₂, C=z₃, woraus wiederum folgt D=E=F=1. Durch Einsetzen in die Gleichungen (2) und (3) erhalten wir

$\,a_{n}=(1/z_{1})^{n}+(1/z_{2})^{n}+(1/z_{3})^{n}$

$\,a_{n}\sim 1.324717917^{n}$.

Die Abschätzung ist so gut, dass ab der zehnten Perrinzahl nur noch gerundet werden muss:

n   a(n)   (1/z1)^n

---

0    3     3.000000
1    0     1.324717
2    2     1.754877
3    3     2.324717
4    2     3.079595
5    5     4.079595
6    5     5.404313
7    7     7.159191
8   10     9.483909
9   12    12.563504
10  17    16.643100
11  22    22.047414
12  29    29.206605
13  39    38.690514
14  51    51.254019
15  68    67.897119
16  90    89.944533
17 119   119.15113
18 158   157.84165
19 209   209.09567
20 277   276.99279