Kurs:Diskrete Mathematik (Osnabrück 2026)/Vorlesung 17

Eine lineare Rekursion definiert eine Folge $a_n$, die allein aufgrund der Tatsache, dass sie durch endlich viele Anfangsdaten und die Rekursionsgleichung bestimmt ist, über eine große Gesetzmäßigkeit verfügen muss. Generell ist es ein wichtiges Hilfsmittel, eine Folge dadurch besser zu verstehen, dass man sie als Koeffizienten einer Potenzreihe auffasst, in der Hoffnung, dass sich die Gesetzmäßigkeiten dadurch zeigen, dass die Potenzreihe eine (bekannte) Funktion beschreibt, die mit analytischen Methoden untersucht werden kann.

Potenzreihen

Definition

Es sei $K$ ein Körper und $T$ eine Variable. Eine formale Potenzreihe in $T$ über $K$ ist ein Ausdruck der Form

$F=\sum _{n\in \mathbb{N}}{a}_n{T}^n,$

mit  $a_n\in K$  für alle  $n\in \mathbb{N}$. 

Man addiert zwei Potenzreihen komponentenweise und multipliziert sie in der gleichen Weise wie Polynome. D.h. man setzt

$F\cdot G=\left({\sum }_{i=0}^{\mathrm{\infty }}{a}_i{T}^i\right)\left({\sum }_{j=0}^{\mathrm{\infty }}{b}_j{T}^j\right)={\sum }_{k=0}^{\mathrm{\infty }}{c}_k{T}^k$

mit  $c_k=\sum _{i=0}^k{a}_i{b}_{k-i}$.  Die Multiplikation ist also durch das Cauchy-Produkt gegeben.

Definition

Es sei $K$ ein Körper und $T$ eine Variable. Dann nennt man die Menge aller formalen Potenzreihen über $K$ in $T$ den Potenzreihenring in einer Variablen (oder den Ring der formalen Potenzreihen in einer Variablen) über $K$. Er wird mit

$K[[T]]$

bezeichnet.

Lemma

Der Ring der formalen Potenzreihen $K[[T]]$ in einer Variablen über einem Körper $K$

ist ein kommutativer Ring.

Beweis

Siehe Aufgabe 17.5.

$◻$

Der Polynomring $K[T]$ ist im Potenzreihenring $K[[T]]$ als Unterring

enthalten.

Satz

Es sei $K$ ein Körper und sei $K[[T]]$ der Ring der formalen Potenzreihen in einer Variablen.

Dann ist eine formale Potenzreihe  $F={\sum }_{n=0}^{\mathrm{\infty }}{a}_n{T}^n$  genau dann eine Einheit, wenn der konstante Term  $a_0\ne 0$  ist.

Beweis

Die angegebene Bedingung ist notwendig, da die Abbildung

$K[[T]]⟶K,F⟼a_0,$

die eine Potenzreihe $F$ auf ihren konstanten Term schickt, ein Ringhomomorphismus ist, siehe Aufgabe 17.6. Für die Umkehrung müssen wir eine Potenzreihe  $G={\sum }_{j=0}^{\mathrm{\infty }}{b}_j{T}^j$  mit

$FG=\left({\sum }_{i=0}^{\mathrm{\infty }}{a}_i{T}^i\right)\left({\sum }_{j=0}^{\mathrm{\infty }}{b}_j{T}^j\right)=1$

angeben. Für $b_0$ ergibt sich daraus die Bedingung  $a_0{b}_0=1$,  die wegen  $a_0\ne 0$  eine eindeutige Lösung besitzt, nämlich  $b_0=a_0^{-1}$.  Nehmen wir induktiv an, dass die Koeffizienten $b_j$ für  $j<n$  schon konstruiert seien, und zwar derart, dass sämtliche Koeffizienten $c_k$, $1\le k<n$, der Produktreihe $FG$ gleich $0$ sind. Für den $n$-ten Koeffizienten ergibt sich die Bedingung

$0=c_n=a_0{b}_n+a_1{b}_{n-1}+\cdots +a_{n-1}{b}_1+a_n{b}_0.$

Dabei sind bis auf $b_n$ alle Werte schon festgelegt, und wegen  $a_0\ne 0$  ergibt sich eine eindeutige Lösung für $b_n$.

$◻$

Korollar

Es sei $K$ ein Körper und sei $K[[T]]$ der Ring der formalen Potenzreihen in einer Variablen. Es seien $G,H$ Polynome über $K$ und der konstante Term von $H$ sei nicht $0$.

Dann lässt sich der Quotient $G/H$ als eine formale Potenzreihe darstellen.

Beweis

Dies folgt unmittelbar aus Satz 17.4, angewendet auf $H$.

$◻$

Beispiel

Wir betrachten $1-T$ im Potenzreihenring $K[[T]]$ über einem beliebigen Körper $K$. Nach Satz 17.4 besitzt $1-T$ ein inverses Element, das man über den Ansatz

$1=(1-T)(b_0+b_{1}T+b_2{T}^2+b_3{T}^3+\dots )$

bestimmen kann. Induktiv ergibt sich, dass  $b_n=1$  für alle  $n\in \mathbb{N}$  ist, das Inverse ist also die (formale) geometrische Reihe.

Erzeugende Funktionen

Definition

Zu einer Folge $a_n$ von komplexen Zahlen nennt man die Potenzreihe

$\sum _{n=0}^{\mathrm{\infty }}{a}_n{z}^n$

bzw. die durch diese Reihe dargestellte Funktion die erzeugende Funktion zur Folge.

Wenn die Potenzreihe gar nicht konvergiert, so existiert die erzeugende Funktion nur in einem formalen Sinn, als formale Potenzreihe. Die Sprechweise könnte auf den ersten Blick verwirrend sein, da man in der Definition mit einer beliebigen Folge startet und dazu die Potenzreihe bzw. die dadurch dargestellte Funktion betrachtet, also eher eine „erzeugte Funktion“. Es ist aber oft umgekehrt, dass die Potenzreihe zuerst da ist und durch sie eine enge Beziehung zwischen den Folgengliedern, nämlich den Koeffizienten der Reihe, bestimmt wird. Dies ist insbesondere dann der Fall, wenn die Potenzreihe eine rationale Funktion darstellt.

Beispiel

Zur konstanten Folge  $a_n=1$  gehört als erzeugende Funktion die geometrische Reihe $\sum _{n=0}^{\mathrm{\infty }}{z}^n$. Diese stellt nach Satz 9.13 (Analysis (Osnabrück 2021-2023)) auf der offenen Einheitskreisscheibe die rationale Funktion $\frac{1}{1-z}$ dar.

Beispiel

Zur Folge der natürlichen Zahlen  $a_n=n$  gehört als erzeugende Funktion die Potenzreihe $\sum _{n=0}^{\mathrm{\infty }}n{z}^n$. Diese Reihe ist gleich $z$ mal der Ableitung der geometrischen Reihe, also gleich

$z\cdot \left(\sum _{n=0}^{\mathrm{\infty }}{z}^n\right)=z\cdot \left(\frac{1}{1-z}\right).$

Es ist ja  $\left(\sum _{n=0}^{\mathrm{\infty }}{z}^n\right)=\sum _{n=1}^{\mathrm{\infty }}n{z}^{n-1}$  nach Satz 20.9 (Analysis (Osnabrück 2021-2023)). Wegen

$\left(\frac{1}{1-z}\right)=\frac{1}{(1-z{)}^2}$

stellt die erzeugende Funktion zu den natürlichen Zahlen die rationale Funktion $\frac{z}{(1-z{)}^2}$ dar.

Bemerkung  

Die Potenzreihe zu einer analytischen Funktion $f$, also einer Funktion, für die man a priori weiß, dass sie durch eine Potenzreihe beschrieben werden kann, lässt sich auf verschiedene Arten erhalten. Eine Möglichkeit ergibt sich über die Taylorreihe. Es werden also die Koeffizienten $a_n$ in der Reihenentwicklung

$f(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$

über

$a_n=\frac{f^{(n)}(0)}{n!}$

bestimmt, wobei $f^{(n)}(0)$ die $n$-te Ableitung von $f$ im Nullpunkt bezeichnet. Bei einer rationalen Funktion

$f=\frac{g}{h}$

mit  $h(0)\ne 0$  muss man konsequent die Ableitungsregeln anwenden, und dabei möglichst eine Gesetzmäßigkeit erkennen, um nicht nur die Anfangswerte $a_0,a_1,a_2$, sondern möglichst alle $a_n$ angeben zu können.

Eine andere Möglichkeit ergibt sich durch algebraische Manipulationen. Hierzu muss man erkennen, wie die Funktion $f$ aus Funktionen konstruiert ist, für die man die Potenzreihenentwicklung schon kennt, und wissen, wie sich die Potenzreihenentwicklungen bei der Konstruktion zueinander verhalten. Ein wichtiges Beispiel ist Satz 17.4, das die Potenzreihe der inversen Funktion  $f=\frac{1}{h}$  aus $h$ beschreibt. Auch der Einsatz von algebraischen Ableitungsregeln wie in Beispiel 17.9 gehört hier dazu.

	Folge	Potenzreihe	Funktion
	$c_n$	$\sum _{n=0}^{\mathrm{\infty }}{c}_n{z}^n$	$F(z)$
	$c_0,c_1,\dots ,c_d$	$\sum _{n=0}^d{c}_n{z}^n$	$\sum _{n=0}^d{c}_n{z}^n$
	$c_n=1$	$\sum _{n=0}^{\mathrm{\infty }}{z}^n$	$\frac{1}{1-z}$
	$c_n=n$	$\sum _{n=0}^{\mathrm{\infty }}n{z}^n$	$\frac{z}{(1-z{)}^2}$
	$c_n=n^2$	$\sum _{n=0}^{\mathrm{\infty }}{n}^2{z}^n$	$\frac{z(1+z)}{(1-z{)}^3}$
	$c_n=\frac{1}{n!}$	$\sum _{n=0}^{\mathrm{\infty }}\frac{1}{n!}{z}^n$	$e^z$
	$c_n=\frac{(-1{)}^{n+1}}{n}$	$\sum _{n=1}^{\mathrm{\infty }}\frac{(-1{)}^{n+1}}{n}{z}^n$	$\ln (1+z)$
	$c_n=\frac{1}{n}$	$\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n}{z}^n$	$\ln \frac{1}{1-z}$
	$c_n=b^n$	$\sum _{n=0}^{\mathrm{\infty }}{b}^n{z}^n$	$\frac{1}{1-bz}$
	$c_n=(\genfrac{}{}{0ex}{}{r}{n})$	$\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{r}{n})z^n$	$(1+z{)}^r$

Die beiden Folgen in den Logarithmusreihen fangen bei $c_1$ an. In der letzten Folge kann das $r$ eine beliebige positive reelle Zahl sein.

Die folgende Aussage kann man beispielsweise auf die Situation anwenden, wo (beliebig viele) Münzen mit $k$ verschiedenen Werten $m_1,\dots ,m_k$ gegeben sind und man sich fragt, auf wie viele Arten man einen bestimmten Betrag $n$ begleichen kann.

Satz

Es seien  $0<m_1<m_2<\dots <m_k$  natürliche Zahlen.

Dann ist die Anzahl der Möglichkeiten, eine natürliche Zahl $n$ als Summe

$n=c_1{m}_1+c_2{m}_2+\cdots +c_k{m}_k$

mit  $c_i\in \mathbb{N}$  darzustellen, gleich dem $n$-ten Koeffizienten der Potenzreihe (bzw. der erzeugenden Funktion)

$\left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{1}j}\right)\left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{2}j}\right)\cdots \left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{k}j}\right)=\frac{1}{1-z^{m_1}}\cdot \frac{1}{1-z^{m_2}}\cdots \frac{1}{1-z^{m_k}}.$

Beweis

Induktion über $k$. Bei  $k=1$  ist eine Darstellung

$n=c_1{m}_1$

genau dann möglich, wenn $n$ ein Vielfaches von $m_1$ ist, und in diesem Fall gibt es genau eine Darstellung. Deshalb ist die zugehörige Potenzreihe gleich $\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{1}j}$. Diese kann man so auffassen, dass in die geometrische Reihe der Term $z^{m_1}$ eingesetzt wird. Deshalb beschreibt diese Potenzreihe die Funktion $\frac{1}{1-z^{m_1}}$.

Zum Beweis des Induktionsschlusses sei angenommen, dass die Aussage für $k$ bewiesen ist und seien $k+1$ natürliche Zahlen gegeben. Die Anzahl der Tupel $(c_1,\dots ,c_{k+1})$ mit

$\sum _{i=1}^{k+1}{c}_i{m}_i=n$

kann man auffassen als die Summe über die Anzahl der Tupel $(c_1,\dots ,c_k)$ mit

$\sum _{i=1}^k{c}_i{m}_i=r$

für  $0\le r\le n$,  wobei $n-r$ ein Vielfaches von $m_{k+1}$ sein muss. Daher ist aufgrund der Induktionsvoraussetzung, dem Fall  $k=1$  und der Definition des Cauchy-Produktes für Potenzreihen

$\begin{array}{cc}& \mathrm{\#}\left(\{(c_1,\dots ,c_{k+1})\mid \sum _{i=1}^{k+1}{c}_i{m}_i=n\}\right)\\ & =\sum _{0\le r\le n}\mathrm{\#}\left(\{(c_1,\dots ,c_k)\mid \sum _{i=1}^k{c}_i{m}_i=r\}\right)\cdot \mathrm{\#}\left(\{c_{k+1}\mid c_{k+1}{m}_{k+1}=n-r\}\right)\\ & =\sum _{0\le r\le n}(r-\text{ter Koeffizient von }\left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{1}j}\right)\cdots \left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{k}j}\right))\cdot ((n-r)-\text{ter Koeffizient von }\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{k+1}j})\\ & =(n-\text{ter Koeffizient von }\left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{1}j}\right)\cdots \left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{k}j}\right)\cdot \left(\sum _{j=0}^{\mathrm{\infty }}{z}^{m_{k+1}j}\right)).\end{array}$

$◻$

Lineare Rekursionen und erzeugende Funktionen

Satz

Es sei $K$ ein Körper und sei ${\left(x_n\right)}_{n\in \mathbb{N}}$ eine Folge in $K$. Dann sind folgende Aussagen äquivalent.

1. Die Folge erfüllt eine lineare Rekursion der Länge $d$, also

   $x_n=a_1{x}_{n-1}+a_2{x}_{n-2}+\cdots +a_d{x}_{n-d}$

   für alle  $n\ge d$  und  $a_d\ne 0$. 

2. Die erzeugende Funktion der Folge besitzt eine rationale Darstellung

   $F_x(t)=\sum _{n=0}^{\mathrm{\infty }}{x}_n{t}^n=\frac{P(t)}{Q(t)}$

   mit

   $Q(t)=1-a_{1}t-a_2{t}^2-\cdots -a_d{t}^d$

   und $P(t)$ ein Polynom vom Grad $\le d-1$.

Beweis

Es sei zunächst (1) erfüllt. Die Koeffizienten des Produktes

$(1-a_{1}t-\cdots -a_d{t}^d)\left(\sum _{n=0}^{\mathrm{\infty }}{x}_n{t}^n\right)=\sum _{n=0}^{\mathrm{\infty }}{c}_n{t}^n$

sind

$c_n=x_n-a_1{x}_{n-1}-a_2{x}_{n-2}-\cdots -a_d{x}_{n-d}$

für  $n\ge d$.  Da die entsprechende lineare Rekursion vorliegt, sind diese Koeffizienten gleich $0$ und das Produkt ist ein Polynom vom Grad $\le d-1$.

Es sei nun (2) erfüllt. Gemäß dem Beweis zu Satz 17.4 besitzt

$Q=1-a_{1}t-a_2{t}^2-\cdots -a_d{t}^d$

eine inverse Potenzreihe $\sum _{n=0}^{\mathrm{\infty }}{b}_n{t}^n$, deren Koeffizienten für  $n\ge d$  durch die Bedingungen

$b_n+a_1{b}_{n-1}+a_2{b}_{n-2}+\cdots +a_{d-1}{b}_{n-d+1}+a_d{b}_{n-d}=0$

charakterisiert sind. Diese erfüllen also eine lineare Rekursion wie behauptet. Dies gilt auch, wenn man die Potenzreihe von $1/Q(t)$ mit einer Potenz von $t$ multipliziert und von solchen Termen eine Linearkombination nimmt.

$◻$

Satz

Es sei ${\left(x_n\right)}_{n\in \mathbb{N}}$ eine komplexe Folge und seien $a_1,\dots ,a_d$ komplexe Zahlen mit  $a_d\ne 0$.  Dann sind folgende Aussagen äquivalent.

1. Die Folge erfüllt eine lineare Rekursion der Länge $d$, also

   $x_n=a_1{x}_{n-1}+a_2{x}_{n-2}+\cdots +a_d{x}_{n-d}$

   für alle  $n\ge d$. 

2. Die erzeugende Funktion der Folge besitzt eine rationale Darstellung

   $F_x(t)=\sum _{n=0}^{\mathrm{\infty }}{x}_n{t}^n=\frac{P(t)}{Q(t)}$

   mit

   $Q(t)=1-a_{1}t-a_2{t}^2-\cdots -a_d{t}^d$

   und $P(t)$ ein Polynom vom Grad $\le d-1$.

3. Die Folge besitzt eine explizite Beschreibung

   $x_n=\sum _{i=1}^k{\lambda }_i^n{P}_i(n)$

   mit komplexen Zahlen ${\lambda }_1,\dots ,{\lambda }_k$ und derart, dass

   $\mathrm{grad}(P_i)\le d_i-1$

   und dass

   $t^d-a_1{t}^{d-1}-\cdots -a_{d-1}t-a_d=\prod _{i=1}^k{(t-{\lambda }_i)}^{d_i}$

   ist.

Beweis

Die Äquivalenz von (1) und (2) ergibt sich aus Satz 17.12, die Implikation von (1) nach (3) folgt aus Korollar 16.12. Wenn (3) erfüllt ist, so schreiben wir

$\prod _{i=1}^k{(T-{\lambda }_i)}^{d_i}=T^d-a_1{T}^{d-1}-\cdots -a_{d-1}T-a_d.$

Wenn diese Situation von (1) herkommt, so stimmt dieses Polynom mit dem charakteristischen Polynom der linearen Rekursion überein. Wir vergleichen (1) und (3), wenn dieses Polynom $\chi$ und damit auch seine Nullstellen ${\lambda }_i$ mit den Vielfachheiten $d_i$ fixiert ist, und wir betrachten die Vektorräume

$V=\{{\left(x_n\right)}_{n\in \mathbb{N}}\mid {\left(x_n\right)}_{n\in \mathbb{N}}\text{ erfüllt die durch }\chi \text{ kodierte lineare Rekursion }\}$

und

$W=\{{\left(x_n\right)}_{n\in \mathbb{N}}\mid \text{ es ist }{x}_n=\sum _{i=1}^k{\lambda }_i^n{P}_i(n),\mathrm{grad}(P_i)\le d_i-1\}.$

Hierbei ist $V$ ein $ℂ$-Vektorraum (ein Untervektorraum des Folgenraumes). Da ferner eine rekursiv definierte Folge durch die Anfangsglieder $x_0,\dots ,x_{d-1}$ festgelegt ist und da die Zuordnung, die diesem Anfangsgliedtupel ihre Folge zuordnet, gemäß Lemma 16.4 linear ist, besitzt $V$ die Dimension $d$. Die Bedingung in $W$ ist ebenfalls linear, daher ist auch $W$ ein Vektorraum. Korollar 16.12 kann man direkt als  $V\subseteq W$  interpretieren. Für jedes $i$ ist die Dimension des Raumes der Polynome vom Grad $\le d_i-1$ gleich $d_i$. Die Summe über $k$ ergibt ebenfalls die Dimension $d$. Daher ist  $V=W$. 

$◻$

<< | Kurs:Diskrete Mathematik (Osnabrück 2026) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)