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

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

a_n= 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:

a_n=a_n-4,     a₀=4, a₁=1, a₂=2, a₃=1,

und daher

$A(x)=\sum _{n\ge 0}{a}_n{x}^n=\frac{4+x+2x^2+x^3}{1-x^4}=\frac{C}{x-1}+\frac{D}{x+1}+\frac{E}{x-i}+\frac{F}{x+i}$.

Der Ansatz

$4+x+2x^2+x^3=C(1+x+x^2+x^3)+D(x^3+x-x^2-1)+E(x^3-x+i{x}^2-i)+F(x^3-x-i{x}^2+i)$

führt auf das Gleichungssystem

$\begin{array}{cc}4& =C-D-iE+iF\\ 1& =C+D-E-F\\ 2& =C-D+iE-iF\\ 1& =C+D+E+F\end{array}$

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

$a_n=𝐠𝐠𝐓(n,4)=2+(-1{)}^n+\frac{i^n+(-i{)}^n}{2}$.