new material on hypergeometric functions

5 files changed, 1072 insertions, 1 deletions

diff --git a/buch/chapters/040-rekursion/Makefile.inc b/buch/chapters/040-rekursion/Makefile.inc
index c9b454c..0da5fe4 100644
--- a/buch/chapters/040-rekursion/Makefile.inc
+++ b/buch/chapters/040-rekursion/Makefile.inc
@@ -6,4 +6,6 @@
 
 CHAPTERFILES = $(CHAPTERFILES)						\
 	chapters/040-rekursion/gamma.tex				\
+	chapters/040-rekursion/linear.tex				\
+	chapters/040-rekursion/hypergeometrisch.tex			\
 	chapters/040-rekursion/chapter.tex
diff --git a/buch/chapters/040-rekursion/chapter.tex b/buch/chapters/040-rekursion/chapter.tex
index 68a5e7a..a6881ab 100644
--- a/buch/chapters/040-rekursion/chapter.tex
+++ b/buch/chapters/040-rekursion/chapter.tex
@@ -10,6 +10,8 @@
 \rhead{}
 
 \input{chapters/040-rekursion/gamma.tex}
+\input{chapters/040-rekursion/linear.tex}
+\input{chapters/040-rekursion/hypergeometrisch.tex}
 
 %\section*{Übungsaufgaben}
 %\rhead{Übungsaufgaben}
diff --git a/buch/chapters/040-rekursion/gamma.tex b/buch/chapters/040-rekursion/gamma.tex
index 1691fc0..00eee19 100644
--- a/buch/chapters/040-rekursion/gamma.tex
+++ b/buch/chapters/040-rekursion/gamma.tex
@@ -5,6 +5,7 @@
 %
 \section{Die Gamma-Funktion
 \label{buch:rekursion:section:gamma}}
+\rhead{Gamma-Funktion}
 Die Fakultät $x!$ kann rekursiv durch 
 \[
 	x! = x\cdot (x-1)! \qquad\text{und}\qquad 0!=1
@@ -21,6 +22,390 @@ Kann man eine reelle oder komplexe Funktion finden, die die
 Funktionalgleichung~\eqref{buch:rekursion:eqn:gammadef}
 erfüllt und damit die Fakultät auf beliebige Argumente ausdehnt?
 
+\subsection{Produktformel}
+Die Fakultät $n!$ ist ein Produkt von $n$ Faktoren, es ist daher
+natürlich zu versuchen, auch $x!$ als ein Produkt zu schreiben.
+Allerdings kann es nicht möglich sein, dies mit einer endlichen
+Anzahl von Faktoren zu machen, denn wenn $x$ grösser wird, muss auch
+die Zahl der Faktoren grösser werden.
+Mit jedem zusätzlichen Faktor ist ein Sprung der Werte zu erwarten.
+Wir erwarten daher entweder ein unendliches Produkt oder einen
+Ausdreck, bei dem die ``Anzahl'' $x$ der Faktoren im Exponenten
+steht.
+In diesem Abschnitt soll zunächst eine solcher Ausdruck gefunden
+werden.
+Dieser ist jedoch für die numerische Berechnung absolut ungeeignet,
+so dass er später in ein unendliches Produkt umgeformt werden muss.
+
+\subsubsection{Fakultät als Bruch}
+Euler hat das Problem, die Fakultät auf beliebige reelle oder komplexe
+Zahlen auszudehnen, wie folgt angepackt.
+Zunächst hat er bemerkt, dass für ganzzahlige $x$ und natürliche $n$
+\begin{align}
+x! 
+&=
+1\cdot 2\cdot 3\cdot\ldots\cdot x
+\notag
+\\
+&=
+\frac{
+1\cdot 2\cdot 3\cdot\ldots\cdot x\cdot (x+1) (x+2)\cdots(x+n)
+}{
+(x+1)(x+2)\cdots(x+n)
+}
+\notag
+\\
+&=
+\frac{
+1\cdot 2\cdot\ldots\cdot n\cdot(n+1)\cdot(n+2)\cdots(n+x)
+}{
+(x+1)(x+2)\cdots(x+n)
+}
+\notag
+\\
+&=
+\frac{n! \cdot (n+1)(n+1)\cdots(n+x)}{(x+1)(x+2)\cdots(x+n)}
+\label{buch:rekursion:gamma:eqn:fakultaet}
+\end{align}
+gilt.
+Der Plan ist, dies so umzuformen, dass man für $x$ eine beliebige
+komplexe Zahl einsetzen kann.
+
+\subsubsection{Pochhammer-Symbol}
+Die spezielle Form des Nenners und des zweiten Faktors im Zähler
+von \eqref{buch:rekursion:gamma:eqn:fakultaet}
+rechtfertigt die folgende Definition.
+
+\begin{definition}[Pochhammer]
+Für $a\in\mathbb{C}$ und $n\in\mathbb{N}$ heisst das Produkt
+\[
+(a)_n = a\cdot(a+1)\cdot(a+2)\cdots(a+n-1)
+\]
+das Pochhammer-Symbol oder die verschobene Fakultät.
+\index{Pochhammer-Symbol}
+\end{definition}
+
+Die verschobene Fakultät $(a)_n$ hat also genau $n$ Faktoren, deren
+erster $1$ ist.
+Die gewöhnliche Fakultät hat $n$ Faktoren, deren erster $1$ ist, also
+ist $n! = (1)_n$.
+
+Der Ausdruck \eqref{buch:rekursion:gamma:eqn:fakultaet}
+für $x!$ wird unter Verwendung des Pochhammer-Symbols zu
+\begin{equation}
+x! = \frac{n! (n+1)_x}{(x+1)_n}.
+\label{buch:rekursion:gamma:eqn:produkt2}
+\end{equation}
+Leider ist dieser Ausdruck ebenfalls nicht auf beliebige $x$
+verallgemeinerungsfähig, denn $(n)_x$ ist nur natürliche $x$ definiert.
+Der Faktor $(n+1)_x$ enthält $x$ Faktoren beginnend bei $n$.
+Für grosses $n$ sind diese Faktoren nahe beeinander, man sollte also
+$(n+1)_x$ durch $n^x$ approximieren können.
+Wir erweitern daher \eqref{buch:rekursion:gamma:eqn:produkt2} mit $n^x$
+und erhalten
+\begin{equation}
+x!
+=
+\frac{n!n^x}{(x+1)_n}\cdot
+\frac{(n+1)_x}{n^x}.
+\label{buch:rekursion:gamma:eqn:produkt3}
+\end{equation}
+Der erste Faktor in diesem Ausdruck enthält jetzt nur noch Dinge,
+die für beliebige $x\in\mathbb{C}$ definiert sind.
+
+\subsubsection{Grenzwertdefinition}
+Der zweite Bruch in \eqref{buch:rekursion:gamma:eqn:produkt3}
+besteht aus Termen, die zwar nur für natürliches $x$ definiert sind,
+wir vermuten aber, dass er für grosses $n$ gegen $1$ konvergiert.
+Tatsächlich gilt
+\[
+\lim_{n\to\infty}
+\frac{(n+1)_x}{n^x}
+=
+\lim_{n\to\infty}
+\underbrace{\frac{n+1}{n}}_{\displaystyle\to 1}
+\cdot
+\underbrace{\frac{n+2}{n}}_{\displaystyle\to 1}
+\cdot\ldots\cdot
+\underbrace{\frac{n+x}{n}}_{\displaystyle\to 1}
+=
+1,
+\]
+da  $(n+x)/n=1+x/n\to 1$ für grosses $n$.
+Dies würde die folgende Definition rechtfertigen.
+
+\begin{definition}
+\label{buch:rekursion:gamma:def:definition}
+Die Gamma-Funktion $\Gamma(x)$ einer Zahl
+$x\in\mathbb{C}\setminus\{0,-1,-2,-3,\dots\}$ ist der Grenzwert
+\[
+\Gamma(x) = \lim_{n\to\infty} \frac{n!n^{x-1}}{(x)_n}.
+\] 
+\end{definition}
+
+\subsubsection{Rekursionsgleichung für $\Gamma(x)$}
+Es ist aus der Herleitung klar, dass $\Gamma(n)=(n-1)!$ sein muss.
+Wir sollten dies aber auch direkt aus der
+Definition~\ref{buch:rekursion:gamma:def:definition} ableiten
+können.
+Dazu müssen wir nur überprüfen, ob $\Gamma(1)=0!=1$ ist und ob
+die Rekursionsformel $\Gamma(n)=n\Gamma(n-1)$ gilt.
+
+Den Wert $\Gamma(1)$ kann man direkt berechnen:
+\[
+\Gamma(1)
+=
+\lim_{n\to\infty} \frac{n!}{(1)_n}
+=
+\lim_{n\to\infty} \frac{n!}{n!}
+=
+1
+\]
+wegen $(1)_n=n!$.
+
+Für die Rekursionsformel muss man den Grenzwert für $x$ und $x+1$
+miteinander vergleichen.
+Aus dem Term $(x+1)_n$ im Nenner muss man einen Term $(x)_n$ machen,
+dies ist möglich, indem man mit $x$ erweitert:
+\begin{align*}
+\Gamma(x+1)
+&=
+\lim_{n\to\infty}\frac{n!n^x}{(x+1)_n}
+=
+x\lim_{n\to\infty}\frac{n!n^x}{x(x+1)_n}
+=
+x\lim_{n\to\infty}\frac{n!n^x}{(x)_{n+1}}.
+\intertext{Wir müssen jetzt nur noch zeigen, dass der Grenzwert
+auf der rechten Seite gegen $\Gamma(x)$ konvergiert,
+in dessen Definition aber die Potenz $n^{x-1}$ vorkommt.
+Wir müssen also einen Faktor $n$ los werden und gleichzeitig
+aus $n$ überall $n+1$ machen, damit der Nenner wieder passt.
+Dabei wird}
+\Gamma(x+1)
+&=
+x\lim_{n\to\infty}
+\frac{(n+1)!n^{x-1}}{(x)_{n+1}}
+\cdot
+\underbrace{\frac{n}{n+1}}_{\displaystyle\to 1}
+\\
+&=
+x\lim_{n\to\infty}
+\underbrace{\frac{(n+1)!(n+1)^{x-1}}{(x)_{n+1}}}_{\displaystyle\to\Gamma(x)}
+\cdot
+\frac{n^{x-1}}{(n+1)^{x-1}}
+\\
+&=
+\Gamma(x)
+\lim_{n\to\infty} \biggl(\frac{n}{n+1}\biggr)^{x-1}
+=
+\Gamma(x),
+\end{align*}
+Weil $n/(n+1)\to 1$ ist und die Funktion $z\mapsto z^{x-1}$ für alle
+nach der Definition zulässigen Werte von $x$ eine stetige Funktion ist.
+
+\subsubsection{Numerische Unzulänglichkeiten der Grenzwertdefinition}
+Die Grenzwertdefinition~\ref{buch:rekursion:gamma:def:definition}
+ist zwar zweifellos richtig, kann aber nicht für die numerische 
+Berechnung der Gamma-Funktion verwendet werden.
+Die Existenz des Grenzwertes verwendet, dass $x\ll n$ sein muss,
+damit $(n+x)/n$ gegenüber $1$ vernachlässigt werden kann.
+Die Grenzwertdefinition beginnt also erst, vernünftige Approximationen
+von $\Gamma(x)$ zu geben, wenn $n$ viel grösser also $x$ ist.
+Andererseits wächst $n!$ sehr schnell an, schon für $n=171$ ist
+das Resultat grösser als was der \texttt{double}-Datentyp fassen kann.
+Dies ist aber viel zu kleine, um gute Approximationen auch für kleine
+Werte von $x$ zu geben.
+So findet man zum Beispiel für $x=\frac12$ und $n=170$ mit Octave
+\[
+\frac{n!n^{x-1}}{(x)_n}
+=
+\frac{170!}{\sqrt{170}\cdot \frac12\cdot\frac32\cdot\ldots\cdot\frac{339}{2}}
+=
+\frac{7.2574\cdot10^{307}}{13.308\cdot 3.1381\cdot10^{305}}
+=
+1.7738.
+\]
+Andererseits werden wir später sehen, dass 
+\[
+\Gamma({\textstyle\frac12})
+=
+\sqrt{\pi}
+=
+1.772453850905516
+\]
+ist.
+Die Approximation mit Hilfe der Grenzwertdefinition kann also
+grundsätzlich nicht mehr als zwei korrekte Nachkommastellen liefern.
+
+\subsubsection{Produktformel}
+Ein möglicher Ausweg aus den numerischen Schwierigkeiten mit der
+Grenzwertdefinition ist, den schnell wachsenden Faktor $n!$
+in den Zähler zu bringen, so dass er der Konvergenz etwas nachhilft.
+Wir berechnen daher den Kehrwert $1/\Gamma(x)$.
+
+\begin{satz}
+\label{buch:rekursion:gamma:satz:produktformel}
+Der Kehrwert der Gamma-Funktion kann geschrieben werden als
+\begin{equation}
+\frac{1}{\Gamma(x)}
+=
+xe^{\gamma x}
+\prod_{k=1}^\infty
+\biggl(1+\frac{x}k\biggr)\,e^{-\frac{x}{k}},
+\label{buch:rekursion:gamma:eqn:produktformel}
+\end{equation}
+wobei $\gamma$ die Euler-Mascheronische Konstante
+\[
+\gamma
+=
+\lim_{n\to\infty}
+\biggl(\sum_{k=1}^n\frac{1}{k}-\log n\biggr)
+\]
+ist.
+\end{satz}
+
+\begin{proof}[Beweis]
+Es sind zwei Dinge nachzuprüfen.
+Zunächst muss nachgewiesen werden, dass das unendliche Produkt 
+überhaupt konvergiert.
+Wenn das gesichert ist, muss noch gezeigt werden, dass der Grenzwert
+tatsächlich $1/\Gamma(x)$ ist.
+
+Für die Konvergenz beachtet man, dass die Faktoren des Produkts 
+die Form
+\begin{align*}
+\biggl(1+\frac{x}n\biggr)e^{-\frac{x}{n}}
+&=
+\biggl(1+\frac{x}n\biggr)
+\biggl(1-\frac{x}{n}+\frac{x^2}{2n^2}-\frac{x^3}{3!n^3}+\dots\biggr)
+\\
+&=
+1-\frac{x^2}{n^2} + 
+\biggl(1+\frac{x}n\biggr)
+\biggl(\frac{x^2}{2n^2}-\dots\biggr)
+\\
+&=
+1-\frac{x^2}{n^2} + \frac{x^2}{2n^2} + O\bigl((\textstyle\frac{x}{n})^2\bigr)
+\\
+&=
+1-\frac{x^2}{2n^2} + O\bigl((\textstyle\frac{x}{n})^3\bigr)
+\end{align*}
+haben.
+Da die Reihe 
+\[
+\sum_{n=1}^\infty \frac{x^2}{n^2}
+\]
+konvergent ist, konvergiert auch das Produkt.
+% XXX wir brauchen irgendwo das Konvergenzkriterium für ein Produkt
+
+Um die Übereinstimmung der Produktformel mit $1/\Gamma(x)$ zu zeigen,
+berechnen wir
+\begin{align*}
+\frac{1}{\Gamma(x)}
+&=
+\lim_{n\to\infty} 
+\frac{(x)_n}{n!n^{x-1}}
+=
+\lim_{n\to\infty} 
+\frac{x(x+1)(x+2)\cdots(x+n-1)}{1\cdot 2\cdot3\cdots (n-1)\cdot n\cdot n^{x-1}}
+\\
+&=
+x
+\lim_{n\to\infty} 
+\frac{x+1}{1}
+\cdot
+\frac{x+2}{2}
+\cdots
+\frac{x+n-1}{n-1}
+\cdot
+n^{-x}
+\\
+&=
+x
+\lim_{n\to\infty}
+\biggl(1+\frac{x}{1}\biggr)
+\cdot
+\biggl(1+\frac{x}{2}\biggr)
+\cdots
+\biggl(1+\frac{x}{n-1}\biggr)
+\cdot
+e^{-x\log n}
+\\
+&=
+x
+\prod_{k=1}^{n-1}
+\biggl(1+\frac{x}{k}\biggr)
+e^{-\frac{x}{k}}
+e^{\frac{x}{k}}
+e^{-x\log n}
+\\
+&=
+x
+\biggl(
+\lim_{n\to\infty}
+\prod_{k=1}^{n-1}
+\biggl(1+\frac{x}{k}\biggr)
+e^{-\frac{x}{k}}
+\biggr)
+\cdot
+\biggl(
+\lim_{n\to\infty}
+e^{x\bigl(\sum_{k=1}^{n-1}\frac{1}{k} - \log n\bigr)}
+\biggr)
+\end{align*}
+Der Klammerausdruck im Exponent des letzten Faktors auf der rechten Seite
+konvergiert nach Definition der Euler-Mascheronischen Konstanten gegen
+$\gamma$, somit folgt 
+\[
+\frac{1}{\Gamma(x)}
+=
+xe^{\gamma x}\prod_{k=1}^\infty \biggl(1+\frac{x}{k}\biggr)e^{-\frac{x}{k}},
+\]
+wie behauptet.
+Damit ist Satz~\ref{buch:rekursion:gamma:satz:produktformel}
+vollständig bewiesen.
+\end{proof}
+
+\begin{table}
+\centering
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
+\hline
+k &  \Gamma(\frac12,n) & \Gamma(\frac12) - \Gamma(\frac12,n) \\
+\hline
+1 & 1.\underline{7}518166478 & -0.0206372031 \\
+2 & 1.\underline{77}02543372 & -0.0021995137 \\
+3 & 1.\underline{772}2324556 & -0.0002213953 \\
+4 & 1.\underline{7724}316968 & -0.0000221541 \\
+5 & 1.\underline{77245}16354 & -0.0000022156 \\
+6 & 1.\underline{772453}6293 & -0.0000002216 \\
+\hline
+\end{tabular}
+\caption{Werte $\Gamma(\frac12,n)$ von $\Gamma(\frac12)$ berechnet mit
+$n=10^k$ Faktoren der
+Produktformel~\eqref{buch:rekursion:gamma:eqn:produktformel}
+und der zugehörige Fehler.
+Die korrekten Nachkommastellen sind unterstrichen.
+\label{buch:rekursion:gamma:gammatabelle}}
+\end{table}
+
+Um zu zeigen, dass die Produktform tatsächlich besser geeignet ist,
+sind in der Tabelle~\ref{buch:rekursion:gamma:gammatabelle}
+die Resultate der numerischen Rechnung  bis $n=1000000$ zusammengestellt.
+Die Produktformel kann gute Werte von $\Gamma(x)$ auch für derart grosse
+Werte von $n$ problemlos berechnen.
+
+Der Fehler der numersichen Approximation ist von der Grössenordnung
+$O(1/n)$ wie das auf Grund des verwendeten Konvergenzkriteriums
+zu erwarten war.
+Die Anzahl zu berücksichtigender Terme wächst daher exponentiall
+mit der Anzahl gewünschter Stellen an, was für praktische Zwecke
+zu langsam ist.
+Für die numersiche Berechnung der Gamma-Funktion ist die Produktformel
+daher im Allgemeinen nicht geeignet.
+
+%
+% Integralformel für die Gamma-Funktion
+%
 \subsection{Integralformel für die Gamma-Funktion}
 Euler hat die folgende Integraldefinition der Gamma-Funktion gegeben.
 
@@ -35,7 +420,7 @@ Die Gamma-Funktion ist die Funktion
 :
 z
 \mapsto
-\Gamma(z) = \int_0^\infty t^{x-1}e^{-t}\,dt
+\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}\,dt
 \]
 \end{definition}
 
@@ -151,7 +536,55 @@ Daher hat auch der Quotient einen Pol erster Ordnung.
 Abbildung~\ref{buch:rekursion:fig:gamma} zeigt die Pole bei den
 nicht negativen ganzen Zahlen.
 
+\subsubsection{Numerische Berechnung}
+\begin{table}
+\centering
+\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|}
+\hline
+k & y(10^k) & y(10^k) - \Gamma(\frac{5}{2}) \\
+\hline
+1 & 0.0000000000 & -0.9027452930 \\
+2 & 0.3319129461 & -0.5708323468 \\
+3 & 0.\underline{902}5209490 & -0.0002243440 \\
+4 & 0.\underline{902745}1207 & -0.0000001723 \\
+5 & 0.\underline{902745}0962 & -0.0000001968 \\
+6 & 0.\underline{902745}0962 & -0.0000001968 \\
+\hline
+\end{tabular}
+\caption{Resultate der Berechnung von $\Gamma(\frac{5}{2})$ mit Hilfe
+der Differentialgleichung \eqref{buch:rekursion:gamma:eqn:gammadgl}.
+Die korrekten Stellen sind unterstrichen.
+Es sind immerhin sechs korrekte Stellen gefunden, wobei nur 337
+Auswertungen des Integranden notwendig waren.
+\label{buch:rekursion:gamma:table:gammaintegral}}
+\end{table}
+Im Prinzip könnte die Integraldefinition der numerischen Berechnung
+entgegenkommen.
+Um diese Hypothese zu prüfen, berechnen wir das Integral für
+$z=\frac52$ mit Hilfe der äquivalenten Differentialgleichungen
+\begin{equation}
+\dot{y}(t) = t^{z-1}e^{-t}
+\qquad\text{mit Anfangsbedingung $y(0)=0$}.
+\label{buch:rekursion:gamma:eqn:gammadgl}
+\end{equation}
+Der gesuchte Wert ist der Grenzwert $\lim_{t\to\infty} y(t)$.
+In der Tabelle~\ref{buch:rekursion:gamma:table:gammaintegral}
+sind die Werte von $y(10^k)$ sowie die Differenzen 
+$y(10^k) - \Gamma(\frac{5}{2})$ zusammengefasst.
+Die Genauigkeit erreicht sechs korrekte Nachkommastellen mit nur
+337 Auswertungen des Integranden.
 
+%
+% Spiegelformel
+%
+\subsection{Die Spiegelungsformel}
 
+%
+% Beta-Integrale
+%
+\subsection{Die Beta-Funktion}
 
+%
+%
+%
 
diff --git a/buch/chapters/040-rekursion/hypergeometrisch.tex b/buch/chapters/040-rekursion/hypergeometrisch.tex
new file mode 100644
index 0000000..ac07789
--- /dev/null
+++ b/buch/chapters/040-rekursion/hypergeometrisch.tex
@@ -0,0 +1,603 @@
+%
+% hypergeometrisch.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\section{Hypergeometrische Funktionen
+\label{buch:rekursion:ssection:hypergeometrische-funktion}}
+\rhead{Hypergeometrische Funktionen}
+Kann man eine Formel für die Lösung $S_n$ der lineare Differenzengleichung
+\[
+n^3S_{n}
+=
+16(n-{\textstyle\frac12})(2n^2-2n+1)S_{n-1}
+-256(n-1)^3S_3
+\]
+mit Anfangswerten $S_0=1$ und $S_1=8$ angeben?
+Dies scheint auf den ersten Blick unmöglich kompliziert, man kann aber
+zeigen, dass
+\[
+S_n
+=
+\sum_{k=0}^n 
+\binom{2n-2k}{n-k}^2 \binom{2k}{k}^2
+\]
+gilt (\cite[p.~xi]{buch:ab}).
+Die Lösung ist also eine Summe von Summanden, die sehr viel einfacher
+aussehen und vor allem die besondere Eigenschaft haben, dass die
+Quotienten aufeinanderfolgender Terme rationale Funktionen von von $k$
+sind.
+% XXX Quotient berechnen
+
+Eine besonders simple solche Funktion ist die geometrische Reihe, die
+im Abschnitt~\ref{buch:rekursion:hypergeometrisch:geometrisch}
+in Erinnerung gerufen wird.
+Abschnitt~\ref{buch:rekursion:hypergeometrisch:reihen}
+definiert den Begriff der hypergeometrischen Reihe und zeigt, 
+wie sie in eine Standardform gebracht werden können.
+In Abschnitt~\ref{buch:rekursion:hypergeometrisch:beispiele}
+schliesslich wird an Hand von Beispielen gezeigt, wie bekannte
+Funktionen als hypergeometrische Funktionen interpretiert werden können.
+
+\subsection{Die geometrische Reihe
+\label{buch:rekursion:hypergeometrisch:geometrisch}}
+Die besonders einfache Potenzreihe
+\[
+f(q)
+=
+\sum_{k=0}^\infty aq^k
+\]
+heisst die {\em geometrische Reihe}.
+Die Partialsummen 
+\[
+S_n
+=
+\sum_{k=0}^n aq^k
+\]
+kann mit der Differenz
+\begin{equation}
+(1-q)S_n
+=
+S_n - qS_n
+=
+\sum_{k=0}^n aq^k
+-
+\sum_{k=1}^{n+1} aq^k
+=
+a -aq^{n+1}
+\label{buch:rekursion:hypergeometrisch:eqn:qsumme}
+\end{equation}
+berechnet werden, die man nach
+\begin{equation}
+S_n 
+=
+a\frac{1-q^{n+1}}{1-q}
+\label{buch:rekursion:hypergeometrisch:eqn:geomsumme}
+\end{equation}
+auflösen kann.
+
+Fü $q<1$ geht $q^n\to 0$ und damit konvergiert
+$S_n$  gegen
+\[
+\sum_{k=0}^\infty aq^k
+=
+a\frac{1}{1-q}.
+\]
+
+Die geometrische Reihe ist charakterisiert dadurch, dass aufeinanderfolgende
+Terme den gleichen Quotienten
+\[
+\frac{aq^{k+1}}{aq^k}
+=
+q
+\]
+haben.
+Die Berechnung der Summe in 
+\eqref{buch:rekursion:hypergeometrisch:eqn:qsumme}
+beruht darauf, dass die Multiplikation mit $q$ einen ``anderen''
+Teil der Summe ergibt, der sich in der Differenze weghebt.
+
+\subsection{Hypergeometrische Reihen
+\label{buch:rekursion:hypergeometrisch:reihen}}
+Es ist plausibel, dass eine etwas lockerere Bedingung an die
+Quotienten aufeinanderfolgender Terme einer Reihe immer noch
+ermöglichen wird, interessante Aussagen über die durch die
+Reihe beschriebenen Funktionen zu machen.
+
+\begin{definition}
+Eine Reihe
+\[
+f(x) = \sum_{k=0}^\infty a_k x^k
+\]
+heisst {\em hypergeometrisch}, wenn der Quotient aufeinanderfolgender
+Koeffizienten eine rationale Funktion von $k$ ist,
+wenn also
+\[
+\frac{a_{k+1}}{a_k}
+=
+\frac{p(k)}{q(k)}
+\]
+mit Polynomen $p(k)$ und $q(k)$ ist.
+\end{definition}
+
+Die geometrische Reihe ist natürlich eine hypergeometrische Reihe,
+wobei $p(k)/q(k)=1$ ist.
+Etwas interessanter ist die Exponentialfunktion, durch die Taylor-Reihe
+\[
+e^x = \sum_{k=0}^\infty \frac{x^k}{k!}
+\]
+dargestellt werden kann.
+Der Quotient aufeinanderfolgender Koeffizienten ist
+\[
+\frac{a_{k+1}}{a_k}
+=
+\frac{1/(k+1)!}{1/k!}
+=
+\frac{k!}{(k+1)!}
+=
+\frac{1}{k+1},
+\]
+eine rationale Funktion mit Zählergrad $0$ und Nennergrad $1$.
+
+Die Kosinus-Funktion wird durch die Taylor-Reihe
+\[
+\cos x = \sum_{k=0}^\infty \frac{(-1)^k}{(2k)!} x^{2k}
+\]
+dargestellt.
+Als Potenzreihe in $x$ kann die Kosinus-Reihe nicht hypergeometrisch sein,
+die ungeraden Koeffizienten verschwinden und damit undefinierte
+Quotienten haben.
+Als Reihe in $z=x^2$ ist aber
+\[
+\sum_{k=0}^\infty \frac{(-1)^k}{(2k)!} z^k
+\qquad\Rightarrow\qquad
+a_k = \frac{(-1)^k}{(2k)!}
+\]
+hypergeometrisch, weil der Quotient aufeinanderfolgender Koeffizienten
+\[
+\frac{a_{k+1}}{a_k}
+=
+\frac{(-1)^{k+1}}{(2k+2)!}\cdot \frac{(2k)!}{(-1)^k}
+=
+-\frac{1}{(2k+2)(2k+1)},
+\]
+eine rationale Funktion mit Zählergrad $0$ und Nennergrad $2$.
+Es gibt also eine hypergeometrische Reihe $f(z)$ derart, dass
+$\cos x = f(x^2)$ ist.
+
+Seien $p(k)$ und $q(k)$ zwei Polynome derart, dass
+\[
+\frac{a_{k+1}}{a_k} = \frac{p(k)}{q(k)}.
+\]
+Daraus lässt sich der Koeffizient $a_{k+1}$ als
+\begin{equation}
+a_{k+1}
+=
+\frac{p(k)}{q(k)}
+\cdot
+a_k
+=
+\frac{p(k)}{q(k)}
+\cdot
+\frac{p(k-1)}{q(k-1)}
+\cdot
+a_{k-1}
+=\dots=
+\frac{p(k)}{q(k)}
+\frac{p(k-1)}{q(k-1)}
+\cdots
+\frac{p(1)}{q(1)}
+\frac{p(0)}{q(0)}
+a_0
+\label{buch:rekursion:hypergeometrisch:ak+1}
+\end{equation}
+berechnen.
+Alle Koeffizienten haben also den Faktor $a_0=f(0)$ gemeinsam.
+
+Die Produkte von Quotienten $p(k)/q(k)$ sollen jetzt weiter
+vereinfacht werden.
+Sei $n$ der Grad von $p(k)$ und $m$ der Grad von $q(k)$.
+Dazu nehmen wir an, dass $a_i$, $i=1,\dots,n$ die Nullstellen von $p(k)$ sind
+und $b_j$, $j=1,\dots,m$ die Nullstellen von $q(k)$, dass man also
+die Polynome als
+\begin{align*}
+p(k) &= x(k-a_1)(k-a_2)\cdots(k-a_n)
+\\
+q(k) &= (k-b_1)(k-b_2)\cdots(k-b_m)
+\end{align*}
+schreiben kann.
+Der Faktor $x$ ist nötig, weil die Polynome $p(k)$ und $q(k)$ nicht
+notwendigerweise normiert sind.
+
+Um das Produkt der Quotienten zu vereinfachen, nehmen wir für den Moment
+an, dass Zähler und Nenner vom Grad $n=m=1$ ist.
+Dann ist nach 
+\eqref{buch:rekursion:hypergeometrisch:ak+1}
+\[
+a_{k}
+=
+x^{k}
+\frac{
+(k-1-a_1) \cdots (2-a_1)(1-a_1)(0-a_1)
+}{
+(k-1-b_1) \cdots (2-b_1)(1-b_1)(0-b_1)
+}
+=
+\frac{(-a_1)_k}{(-b_1)_k} x^k.
+\]
+Die Koeffizienten können daher als Quotienten von Pochhammer-Symbolen
+geschrieben werden.
+Für Polynome $p(k)$ und $q(k)$ höheren Grades sind die Koeffizienten
+von der Form
+\[
+a_k
+=
+\frac{(-a_1)_k(-a_2)_k\cdots (-a_n)_k}{(-b_1)_k(-b_2)_k\cdots(-b_m)_k}
+x^ka_0.
+\]
+Jede hypergeometrische Reihe kann daher in der Form
+\[
+a_0
+\sum_{k=0}^\infty
+\frac{(-a_1)_k(-a_2)_k\cdots (-a_n)_k}{(-b_1)_k(-b_2)_k\cdots(-b_m)_k}
+x^k
+\]
+geschrieben werden.
+
+\begin{definition}
+\label{buch:rekursion:hypergeometrisch:def}
+Die hypergeometrische Funktion
+$\mathstrut_pF_q$ ist definiert durch die Reihe
+\[
+\mathstrut_pF_q
+\biggl(
+\begin{matrix}
+a_1,\dots,a_p\\
+b_1,\dots,b_q
+\end{matrix}
+;
+x
+\biggr)
+=
+\mathstrut_pF_q(a_1,\dots,a_p;b_1,\dots,b_q;x)
+=
+\sum_{k=0}^\infty
+\frac{(a_1)_k\cdots(a_p)_k}{(b_1)_k\cdots(b_q)_k}\frac{x^k}{k!}.
+\]
+\end{definition}
+
+Da $(1)_k=k!$ hätte die Definition den Nenner $k!$ in der Reihe
+auch durch eines der Pochhammer-Symbole ausdrücken können.
+Wird dieser Nenner nicht gebraucht, kann man ihn durch einen 
+zusätzlichen Faktor $(1)_k$ im Zähler des Bruchs von Pochhammer-Symbolen
+kompensieren, wodurch sich der Grad $p$ des Zählers natürlich um $1$
+erhöht.
+
+Die oben analysierte Summe $S$ kann mit der Definition als
+\[
+S
+=
+a_0
+\,
+\mathstrut_{n+1}F_m \biggl(
+\begin{matrix}
+-a_1,-a_2,\dots,-a_n,1\\
+-b_1,-b_2,\dots,-a_m
+\end{matrix}; x
+\biggr)
+\]
+beschrieben werden.
+
+\subsection{Beispiele von hypergeometrischen Funktionen
+\label{buch:rekursion:hypergeometrisch:beispiele}}
+Viele der bekannten Reihenentwicklungen häufig verwendeter Funktionen
+lassen sich durch die hypergeometrischen Funktionen von
+Definition~\ref{buch:rekursion:hypergeometrisch:def} ausdrücken.
+In diesem Abschnitt werden einige Beispiel dazu gegeben.
+
+\subsubsection{Die geometrische Reihe}
+In der geometrischen Reihe fehlt der Nenner $k!$, es braucht
+daher einen Term $(1)_k$ im Zähler, um den Nenner zu kompensieren.
+Somit ist die geometrische Reihe
+\[
+\frac{a}{1-x}
+=
+\sum_{k=0}^\infty
+ax^k
+=
+a\sum_{k=0}^\infty
+\frac{(1)_k}{1}
+\frac{x^k}{k!}
+=
+a\,\mathstrut_1F_0(1,x).
+\]
+
+\subsubsection{Exponentialfunktion}
+Die Exponentialfunktion ist die Reihe
+\[
+e^x = \sum_{k=0}^\infty \frac{x^k}{k!}.
+\]
+In diesem Fall werden keine Quotienten von Pochhammer-Symbolen
+benötigt, es ist daher
+\[
+e^x = \mathstrut_0F_0(x).
+\]
+
+\subsubsection{Wurzelfunktion}
+Die Wurzelfunktion $x\mapsto \sqrt{x}$ hat keine Taylor-Entwicklung
+in $x=0$, aber die Funktion $x\mapsto\sqrt{1+x}$ hat die Taylor-Reihe
+\[
+\sqrt{1+x}
+=
+1
++
+\frac12 x
+-
+\frac{1\cdot 1}{2\cdot 4}x^2
++
+\frac{1\cdot 1\cdot 3}{2\cdot 4\cdot 6}x^3
+-
+\frac{1\cdot 1\cdot 3\cdot 5}{2\cdot 4\cdot 6\cdot 8}x^4
++
+\dots
+\]
+Um die Verbindung zu einer hypergeometrischen Funktion herzustellen,
+müssen wir den Term $x^k/k!$ abspalten.
+Dann wird
+\begin{align*}
+\sqrt{1+x}
+&=
+1
++
+\frac12 \frac{x}{1!}
+-
+\frac{1\cdot 1}{2^2}\frac{x^2}{2!}
++
+\frac{1\cdot 1\cdot 3}{2^3}\frac{x^3}{3!}
+-
+\frac{1\cdot 1\cdot 3\cdot 5}{2^4}\frac{x^4}{4!}
++
+\dots
+\\
+&=
+1
++
+\frac12 \cdot\frac{x}{1!}
+-
+\frac{1}{2}\cdot \frac{1}{2}\cdot\frac{x^2}{2!}
++
+\frac{1}{2}\cdot \frac{1}2\cdot \frac{3}{2}\cdot\frac{x^3}{3!}
+-
+\frac{1}{2}\cdot \frac{1}{2}\cdot \frac{3}{2}\cdot \frac{5}{2}\cdot\frac{x^4}{4!}
++
+\dots
+\end{align*}
+Es ist noch etwas undurchsichtig, warum die ersten beiden Terme
+das gleiche Vorzeichen haben und warum der Faktor $\frac12$ in jedem
+Term zweimal vorkommt.
+Diese Unklarheit kann jedoch beseitigt werden, wenn man den ersten
+Faktor als $-\frac12$ schreibt:
+\begin{align*}
+\sqrt{1+x}
+&=
+1
+-
+\biggl(-\frac12\biggr)\cdot\frac{x}{1!}
++
+\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot\frac{x^2}{2!}
+-
+\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}2\cdot \frac{3}{2}\cdot\frac{x^3}{3!}
++
+\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot \frac{3}{2}\cdot \frac{5}{2}\cdot\frac{x^4}{4!}
++
+\dots
+\\
+&=
+1 + 
+\biggl(-\frac12\biggr)\cdot\frac{-x}{1!}
++
+\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot\frac{(-x)^2}{2!}
++
+\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}2\cdot \frac{3}{2}\cdot\frac{(-x)^3}{3!}
++
+\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot \frac{3}{2}\cdot \frac{5}{2}\cdot\frac{(-x)^4}{4!}
++
+\dots
+\end{align*}
+Die Koeffizienten sind aufsteigende Produkte mit $k$ Faktoren, die alle bei
+$-\frac12$ beginnen, sie können daher als Pochhammer-Symbole $(-\frac12)_k$
+geschrieben werden.
+Die Wurzelfunktion ist daher die hypergeometrische Funktion
+\[
+\sqrt{1\pm x}
+=
+\sum_{k=0}^\infty
+\biggl(-\frac12\biggr)_k \frac{(-x)^k}{k!}
+=
+\mathstrut_1F_0(-{\textstyle\frac12};\mp x).
+\]
+
+\subsubsection{Logarithmusfunktion}
+Für $x\in (-1,1)$ konvergiert die Taylor-Reihe
+\[
+\log(1+x)
+=
+x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\dots
+\]
+der Logarithmusfunktion im Punkt $x=0$.
+Die Reihe beginnt nicht mit einem konstanten Term, daher klammern wir
+zunächst einen Faktor $x$ aus:
+\[
+\log(1+x)
+=
+x\cdot
+\biggl(
+1-\frac{x}{2}+\frac{x^2}{3}-\frac{x^3}{4}+\dots
+\]
+Um dies in die Form einer hypergeometrischen Funktion zu bringen,
+muss zunächst wieder der Nenner $k!$ hergestellt werden.
+\begin{align*}
+\log(1+x)
+&=
+x\cdot\biggl(
+1
+- \frac{1!}{2} \frac{x}{1!}
++ \frac{2!}{3} \frac{x^2}{2!} 
+- \frac{3!}{4} \frac{x^3}{3!}+\dots
+\biggr).
+\intertext{Den Nenner $k+1$ kann man als Quotienten $k!/(k+1)!$ erhalten,
+also}
+\log(1+x)
+&=
+x\cdot\biggl(
+1
+- \frac{(1!)^2}{2!} \frac{x}{1!}
++ \frac{(2!)^2}{3!} \frac{x^2}{2!} 
+- \frac{(3!)^2}{4!} \frac{x^3}{3!}+\dots
+\biggr).
+\end{align*}
+Die Fakultät
+\[
+(k+1)!
+=
+1\cdot 2 \cdot 3 \cdot\ldots\cdot k\cdot (k+1)
+=
+2 \cdot (2 + 1) \cdot (2+2) \cdot\ldots\cdot (2+k-2) \cdot (2+k-1)
+=
+(2)_{k}
+\]
+ist auch ein Pochhammer-Symbol, so dass die Logarithmusfunktion
+zur hypergeometrischen Funktion
+\[
+\log(1+x)
+=
+x\cdot\biggl(
+1
++ \frac{(1)_1(1)_1}{(2)_1} \frac{(-x)}{1!}
++ \frac{(1)_2(1)_2}{(2)_2} \frac{(-x)^2}{2!} 
++ \frac{(1)_3(1)_3}{(2)_2} \frac{(-x)^3}{3!}+\dots
+\biggr)
+=
+x\cdot
+\mathstrut_2F_1\biggl(\begin{matrix}1,1\\2\end{matrix};-x\biggr).
+\]
+
+
+\subsubsection{Trigonometrische Funktionen}
+Die Kosinus-Funktion wurde bereits als hypergeometrische Funktion erkannt,
+im Folgenden soll dies auch noch für die Sinus-Funktion
+durchgeführt werden.
+Die Taylor-Reihe der Sinus-Funktion im Punkt $0$ ist
+\begin{align*}
+\sin x
+&=
+x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\dots
+\end{align*}
+In dieser Reihe fehlen die geraden Potenzen, wir Klammern daher einen
+Faktor $x$ aus und schreiben den Rest als eine Funktion von $-x^2$
+\begin{align*}
+\sin x
+&=
+x
+\biggl(
+1+\frac{-x^2}{3!}+\frac{(-x^2)^2}{5!}-\frac{(-x^2)^3}{7!}+\dots
+\biggr)
+=
+x f(-x^2).
+\end{align*}
+Die Funktion $f(z)$ soll jetzt als hypergeometrische Funktion geschrieben
+werden.
+Dazu muss zunächst wieder der Nenner $k!$ wiederhergestellt werden:
+\[
+f(z)
+=
+1
++
+\frac{1!}{3!}\cdot \frac{z}{1!}
++
+\frac{2!}{5!}\cdot \frac{z^2}{2!}
++
+\frac{3!}{7!}\cdot \frac{z^3}{3!}
++
+\dots
+\]
+Die Koeffizienten $k!/(2k+1)!$ müssen jetzt durch Pochhammer-Symbole
+mit jeweils $k$ Faktoren ausgedrückt werden.
+Dazu muss die Fakultät $(2k+1)!$ in zwei Produkte
+\[
+(2k+1)
+=
+2\cdot 3 \cdot 4\cdot 5\cdot \ldots \cdot 2k \cdot (2k+1)
+=
+(2\cdot 4 \cdot 6\cdot\ldots\cdot 2k)
+\cdot
+(3\cdot 5\cdot 7\cdot \ldots \cdot (2k+1))
+\]
+aufgespaltet werden.
+Diese Produkte haben zwar $k$-Faktoren, aber sie sind keine
+Pochhammer-Symbole, weil die Differenz aufeinanderfolgender Faktoren 
+jeweils $2$ ist.
+Wir dividieren die geraden Faktoren durch $2$ und dividieren die 
+ungeraden durch $2$, dadurch ändert sich das Produkt nicht und wird
+\[
+(2k+1)!
+=
+(1\cdot2\cdot3\cdot\ldots\cdot k)
+\cdot
+\biggl(
+\frac{3}{2}\cdot
+\frac{5}{2}\cdot
+\frac{7}{2}\cdot
+\ldots\cdot
+\frac{2k+1}{2}
+\biggr)
+=
+(1)_k\cdot \biggl(\frac{3}{2}\biggr)_k
+\]
+Setzt man dies in die Reihe ein, wird
+\[
+f(z)
+=
+\sum_{k=0}^\infty
+\frac{(1)_k}{(1)_k\cdot (\frac{3}{2})_k}
+z^k
+=
+\mathstrut_1F_2(1;1,\frac{3}{2};z).
+\]
+Damit lässt sich die Sinus-Funktion als
+\[
+\sin x
+=
+x\,\mathstrut_1F_2\biggl(\begin{matrix}1\\1,\frac32\end{matrix};-x^2\biggr)
+\]
+durch eine hypergeometrische Funktion ausdrücken.
+
+\subsubsection{Hyperbolische Funktionen}
+Die für die Sinus-Funktion angewendete Methode lässt sich auch
+auf die Funktion 
+\begin{align*}
+\sinh x
+&=
+\sum_{k=0}^\infty \frac{x^{2k+1}}{(2k+1)!}
+\\
+&=
+x
+\,
+\biggl(
+1+\frac{x^2}{3!} + \frac{x^4}{5!}+\frac{x^6}{7!}+\dots
+\biggr)
+\\
+&=
+xf(-x^2)
+=
+x\,\mathstrut_1F_2\biggl(
+\begin{matrix}1\\1,\frac{3}{2}\end{matrix}
+;x^2
+\biggr).
+\end{align*}
+Bis auf das Vorzeichen des Arguments der hypergeometrischen Funktion
+ist diese Darstellung identisch mit der von $\sin x$.
+Dies illustriert die Rolle der hypergeometrischen Funktionen als
+``grosse Vereinheitlichung'' der bekannten speziellen Funktionen.
+
+
diff --git a/buch/chapters/040-rekursion/linear.tex b/buch/chapters/040-rekursion/linear.tex
new file mode 100644
index 0000000..7c0aac7
--- /dev/null
+++ b/buch/chapters/040-rekursion/linear.tex
@@ -0,0 +1,31 @@
+%
+% linear.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\section{Lineare Rekursionsgleichung mit konstanten Koeffizienten
+\label{buch:rekursion:section:linear}}
+\rhead{Lineare Rekursionsgleichungen}
+Die Funktionalgleichung der Gamma-Funktion, die im
+Abschnitt~\ref{buch:rekursion:section:gamma} untersucht wurde,
+hat die Form einer linearen Rekursionsgleichung
+\[
+\Gamma(x+1) = x\Gamma(x),\qquad \Gamma(1) = 1.
+\]
+Gleichungen, die Werte einer Funktion für verschiedene
+Argument in Beziehung setzen, heissen {\em Funktionalgleichungen}.
+\index{Funktionalgleichung}%
+Es war überraschend schwierig, eine Lösung für Funktionalgleichung
+der Gamma-Funktion für beliebige komplexe $x$ zu finden.
+In diesem Abschnitt soll daher eine Klasse von Rekursionsgleichungen
+näher untersucht werden, für die einfache Lösungen möglich sind.
+
+\subsection{Lineare Differenzengleichungen}
+
+\subsection{Lösung mit Polynomfunktionen}
+
+
+
+
+
+