Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Alternierende Folgen

Mit den Methoden des letzten Beispiels können auch komplexere Aufgabenstellungen bewältigt werden. Sei die Definition gegeben

$f(n)={\begin{cases}f_{1}(n),&n{\mbox{ gerade;}}\\f_{2}(n),&n{\mbox{ ungerade.}}\end{cases}}$

Solche periodisch wechselnden Folgen werden mit dem Ansatz

$f(n)={\frac {f_{1}(n)+f_{2}(n)}{2}}+{\frac {f_{1}(n)-f_{2}(n)}{2}}(-1)^{n}.$

bearbeitet. Das Prinzip: ist n gerade, bleibt das zwischen den Brüchen stehende Vorzeichen ein Plus, und die f₂-Terme heben sich gegenseitig auf. Ist n ungerade, wird das Vorzeichen ein Minus und die f₁-Terme verschwinden.

Ein Beispiel, von der Definition über die Erzeugende zur Rekurrenz:

${\begin{aligned}f_{n}&={\begin{cases}2^{n},&n{\text{ gerade;}}\\n+1,&n{\text{ ungerade.}}\end{cases}}\qquad ={\tfrac {2^{n}+n+1}{2}}+{\tfrac {2^{n}-n-1}{2}}(-1)^{n}\\F(x)&={\frac {1}{2}}\left({\frac {1}{1-2x}}+{\frac {x}{(1-x)^{2}}}+{\frac {1}{1-x}}+{\frac {1}{1+2x}}-{\frac {-x}{(1+x)^{2}}}-{\frac {1}{1+x}}\right)\\&={\frac {-x^{4}+8x^{3}+2x^{2}-2x-1}{4x^{6}-9x^{4}+6x^{2}-1}}.\end{aligned}}$

Das Resultat

$\,f_{n+6}=6f_{n+4}-9f_{n+2}+4f_{n}$

besteht nur aus Folgengliedern, die einer einzigen der in der Definition angegebenen Teilfolgen angehören, gilt aber für die ganze Folge. Das bedeutet, dass durch Halbierung der Indices eine Rekurrenz entsteht, die für jede der beiden Einzelfolgen 2²ⁿ und 2n gilt, und wir eine Methode entdeckt haben, mit der sich eine solche berechnen läßt.