Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Ein gemeinsamer Teiler

Die Zahlenfolge mit der Formel an=ggT(n,4) ist 4-periodisch:

an= 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, ...

Wenngleich die Folge damit eine eindeutige und leicht berechenbare Form hat, würde uns eine geschlossene Form interessieren, die nur aus Potenzen besteht. Dazu versuchen wir zunächst, eine Rekurrenz zu finden.

Die Periodizität liefert sofort:

an=an-4,     a0=4, a1=1, a2=2, a3=1,

und daher

.

Der Ansatz

führt auf das Gleichungssystem

mit der Lösung C=2, D=-1, E=i/2, F=-i/2. Wir erhalten die Formel

.