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

Aus Wikibooks

< Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen

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\ge0}a_nx^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+ix^2-i)+F(x^3-x-ix^2+i)$

führt auf das Gleichungssystem

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

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

$\,a_n=\mathbf{ggT}(n,4)\quad=\quad2+(-1)^n+\frac{i^n+(-i)^n}{2}$ .

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

Aus Wikibooks

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Mitmachen

Werkzeuge

Drucken/exportieren