komplexe Fibonacci-Zahlen

6 files changed, 324 insertions, 10 deletions

diff --git a/buch/chapters/040-rekursion/beta.tex b/buch/chapters/040-rekursion/beta.tex
index 24d6ac5..f244d18 100644
--- a/buch/chapters/040-rekursion/beta.tex
+++ b/buch/chapters/040-rekursion/beta.tex
@@ -256,7 +256,7 @@ Für $x=\frac12$ wird der Ausdruck besonders einfach:
 =
 \int_0^1 t^{-\frac12}(1-t)^{-\frac12}\,dt
 =
-\int_0^1 \frac{1}{\sqrt{t(1-t)}}\,dt.
+\int_0^1 \frac{1}{\sqrt{t(1-t)\mathstrut}}\,dt.
 \]
 Mit der Substition $t=\sin^2 s$ wird daraus
 \[
@@ -475,7 +475,8 @@ Setzt man $x=\frac12$ in die Verdoppelungsformel ein, erhält man
 \qquad\Rightarrow\qquad
 \Gamma({\textstyle\frac12}) = \sqrt{\pi},
 \]
-in Übereinstimmung mit dem bereits bekannten Wert.
+in Übereinstimmung mit dem aus \eqref{buch:rekursion:gamma:gamma12}
+bereits bekannten Wert.
 
 \subsubsection{Beta-Funktion und Binomialkoeffizienten}
 Die Binomialkoeffizienten können mit Hilfe der Fakultät als
diff --git a/buch/chapters/040-rekursion/images/Makefile b/buch/chapters/040-rekursion/images/Makefile
index 58f79b8..9608a94 100644
--- a/buch/chapters/040-rekursion/images/Makefile
+++ b/buch/chapters/040-rekursion/images/Makefile
@@ -3,10 +3,16 @@
 #
 # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
 #
-all:	gammaplot.pdf
+all:	gammaplot.pdf fibonacci.pdf
 
 gammaplot.pdf:	gammaplot.tex gammapaths.tex
 	pdflatex gammaplot.tex
 
 gammapaths.tex:	gammaplot.m
 	octave gammaplot.m
+
+fibonaccigrid.tex:	fibonacci.m
+	octave fibonacci.m
+
+fibonacci.pdf:	fibonacci.tex fibonaccigrid.tex
+	pdflatex fibonacci.tex
diff --git a/buch/chapters/040-rekursion/images/fibonacci.m b/buch/chapters/040-rekursion/images/fibonacci.m
new file mode 100644
index 0000000..4c9754e
--- /dev/null
+++ b/buch/chapters/040-rekursion/images/fibonacci.m
@@ -0,0 +1,136 @@
+#
+# fibonacci.m
+#
+# (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+global phi1;
+phi1 = (1+sqrt(5)) / 2;
+phi2 = (1-sqrt(5)) / 2;
+global logphi1;
+logphi1 = log(phi1)
+global logphi2;
+logphi2 = log(phi2)
+
+global s;
+s = 0.1;
+
+A = [ 1, 1; phi1, phi2 ];
+b = [ 0; 1 ];
+global a;
+a = A \ b
+
+global xmin;
+xmin = 0;
+global xmax;
+xmax = 10;
+global ylim;
+ylim = 10;
+
+global N;
+N = 200;
+
+function retval = fibonacci(n) 
+	global a;
+	global logphi1;
+	global logphi2;
+	retval = a(1,1) * exp(n * logphi1) + a(2,1) * exp(n * logphi2);
+endfunction
+
+for n = (0:10)
+	fibonacci(n)
+endfor
+
+function punkt(fn, z)
+	if (abs(z) > 100)
+		z = 100 * z / abs(z);
+	endif
+	fprintf(fn, "(%.5f,%.5f)", real(z), imag(z));
+endfunction
+
+function drawline(fn, p, color,lw)
+	global N;
+	fprintf(fn, "\\draw[color=%s,line width=%.1fpt] ", color, lw);
+	punkt(fn, p(1));
+	for i = (2:N+1)
+		fprintf(fn, "\n\t--");
+		punkt(fn, p(i));
+	endfor
+	fprintf(fn, ";\n");
+endfunction
+
+function realline(fn, x, ymin, ymax, color, lw)
+	global N;
+	h = (ymax - ymin) / N;
+	fprintf(fn, "%% real line for x = %f, h = %f\n", x, h);
+	count = 1;
+	for y = ymin + (0:N) * h
+		z(count) = fibonacci(x + i * y);
+		count = count + 1;
+	endfor
+	drawline(fn, z, color, lw);
+endfunction
+
+function imaginaryline(fn, y, xmin, xmax, color, lw)
+	global N;
+	h = (xmax - xmin) / N;
+	fprintf(fn, "%% imaginary line for y = %f, h = %f\n", y, h);
+	count = 1;
+	for x = xmin + (0:N) * h
+		z(count) = fibonacci(x + i * y);
+		count = count + 1;
+	endfor
+	drawline(fn, z, color, lw);
+endfunction
+
+function fibmapping(fn, n, name, lw)
+	global s;
+	fprintf(fn, "\\def\\%s{\n", name);
+	for x = n + s*(-5:5) 
+		realline(fn, x, -5*s, 5*s, "red", lw);
+	endfor
+	for y = s*(-5:5)
+		imaginaryline(fn, y, n-5*s, n+5*s, "blue", lw);
+	endfor
+	fprintf(fn, "}\n");
+endfunction
+
+function fibgrid(fn, lw)
+	global s;
+	fprintf(fn, "\\def\\fibgrid{\n");
+	for y = s*(-5:5)
+		imaginaryline(fn, y, -0.5, 6.5, "gray", lw);
+	endfor
+	for x = s*(-5:65)
+		realline(fn, x, -0.5, 0.5, "gray", lw);
+	endfor
+	fprintf(fn, "}\n");
+endfunction
+
+function fibcurve(fn, lw)
+	fprintf(fn, "\\def\\fibcurve{\n");
+	imaginaryline(fn, 0, 0, 6.5, "white", 1.2*lw);
+	imaginaryline(fn, 0, 0, 6.5, "darkgreen", lw);
+	for n = (0:6)
+		z = fibonacci(n);
+		fprintf(fn, "\\fill[color=darkgreen] ");
+		punkt(fn, z);
+		fprintf(fn, " circle[radius=0.08];\n");
+		fprintf(fn, "\\fill[color=white] ");
+		punkt(fn, z);
+		fprintf(fn, " circle[radius=0.04];\n");
+	endfor
+	fprintf(fn, "}\n");
+endfunction
+
+fn = fopen("fibonaccigrid.tex", "w");
+fibmapping(fn, 0, "fibzero", 1);
+fibmapping(fn, 1, "fibone", 1);
+fibmapping(fn, 2, "fibtwo", 1);
+fibmapping(fn, 3, "fibthree", 1);
+fibmapping(fn, 4, "fibfour", 1);
+fibmapping(fn, 5, "fibfive", 1);
+fibmapping(fn, 6, "fibsix", 1);
+fibgrid(fn, 0.3);
+fibcurve(fn, 1.4);
+
+fclose(fn);
diff --git a/buch/chapters/040-rekursion/images/fibonacci.pdf b/buch/chapters/040-rekursion/images/fibonacci.pdf
new file mode 100644
index 0000000..e745b73
--- /dev/null
+++ b/buch/chapters/040-rekursion/images/fibonacci.pdf
diff --git a/buch/chapters/040-rekursion/images/fibonacci.tex b/buch/chapters/040-rekursion/images/fibonacci.tex
new file mode 100644
index 0000000..3bd8b63
--- /dev/null
+++ b/buch/chapters/040-rekursion/images/fibonacci.tex
@@ -0,0 +1,149 @@
+%
+% fibonacci.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\input{fibonaccigrid.tex}
+\def\skala{1}
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\achsen{
+	\draw[->] (-2.1,0) -- (10.8,0)
+		coordinate[label={$\operatorname{Re}F(z)$}];
+	\draw[->] (0,-2.6) -- (0,2.7)
+		coordinate[label={right:$\operatorname{Im}F(z)$}];
+	\node at (10.8,2.7) {$\mathbb{C}$};
+}
+
+\def\zahl#1#2{
+	\fill[color=white,opacity=0.8]
+		({#1-0.65},-0.6) rectangle ({#1+0.65},-0.2);
+	\node[color=darkgreen] at (#1,-0.43) {$#2\mathstrut$};
+}
+
+\draw[color=gray!20,line width=2.0pt] (-2,3.2) -- (11.3,3.2);
+
+\def\topskala{1.55}
+
+\draw[->,color=darkgreen!30,line width=5pt]
+		({-0.2*\topskala},4.3) to[out=-120,in=120] (-0.1,0.2);
+\draw[->,color=darkgreen!30,line width=5pt]
+		({0.9*\topskala},4.3) to[out=-110,in=70] (0.9,-5.1);
+\draw[->,color=darkgreen!30,line width=5pt]
+		({2.0*\topskala},4.3) to[out=-90,in=76] (1.0,-10.6);
+
+\draw[->,color=darkgreen!30,line width=5pt]
+		({3.0*\topskala},4.3) to[out=-90,in=90] (2.0,0.2);
+\draw[->,color=darkgreen!30,line width=5pt]
+		({3.9*\topskala},4.3) to[out=-110,in=80] (3.0,-5.3);
+\draw[->,color=darkgreen!30,line width=5pt]
+		({4.8*\topskala},4.3) to[out=-120,in=90] (5.0,-10.8);
+
+\draw[->,color=darkgreen!30,line width=5pt]
+		({6.0*\topskala},4.3) to[out=-90,in=70] (8.1,0.2);
+
+
+\begin{scope}[yshift=4.8cm,scale=\topskala]
+
+	\draw[->] (-0.7,0) -- (6.8,0)
+		coordinate[label={$\operatorname{Re}z$}];
+	\draw[->] (0,-0.7) -- (0,0.8)
+		coordinate[label={right:$\operatorname{Im}z$}];
+	\foreach \x in {-0.5,-0.4,...,6.501}{
+		\draw[color=gray,line width=0.1pt] (\x,-0.5) -- (\x,0.5);
+	}
+	\foreach \y in {-0.5,-0.4,...,0.501}{
+		\draw[color=gray,line width=0.1pt] (-0.5,\y) -- (6.5,\y);
+	}
+
+	\foreach \n in {0,3,6}{
+		\foreach \x in {-0.5,-0.4,...,0.501}{
+			\draw[color=blue,line width=0.7pt]
+				({\n+\x},-0.5) -- ({\n+\x},0.5);
+		}
+		\foreach \y in {-0.5,-0.4,...,0.501}{
+			\draw[color=red,line width=0.7pt]
+				({\n-0.5},\y) -- ({\n+0.5},\y);
+		}
+	}
+	\foreach \n in {0,...,6}{
+		\fill[color=white,opacity=0.8]
+			({\n-0.1},-0.28) rectangle ({\n+0.1},-0.05);
+		\node[color=darkgreen] at (\n,0) [below] {$\n$};
+		\fill[color=darkgreen] (\n,0) circle[radius=0.05];
+		\fill[color=white] (\n,0) circle[radius=0.02];
+	}
+
+	\node at (6.8,0.8) {$\mathbb{C}$};
+
+\end{scope}
+
+\begin{scope}[scale=1]
+	\begin{scope}
+		\clip (-2,-2.6) rectangle (10.5,2.6);
+		\fibgrid
+	\end{scope}
+	\achsen
+	\begin{scope}
+		\clip (-2,-2.6) rectangle (10.5,2.6);
+		\fibzero
+		\fibthree
+		\fibsix
+	\end{scope}
+	\fibcurve
+	\node[color=magenta] at (-1.3,-1.8) {$n=0$};
+	\node[color=magenta] at (1.9,0.8) {$n=3$};
+	\node[color=magenta] at (8,2.3) {$n=6$};
+	\zahl{0}{F(0)=0}
+	\zahl{2}{F(3)=2}
+	\zahl{8}{F(6)=8}
+\end{scope}
+
+\begin{scope}[yshift=-5.5cm,scale=1]
+	\begin{scope}
+		\clip (-2,-2.6) rectangle (10.5,2.6);
+		\fibgrid
+	\end{scope}
+	\achsen
+	\begin{scope}
+		\clip (-2,-2.6) rectangle (10.5,2.6);
+		\fibone
+		\fibfour
+	\end{scope}
+	\fibcurve
+	\node[color=magenta] at (1,1.2) {$n=1$};
+	\node[color=magenta] at (3,1.1) {$n=4$};
+	\zahl{1}{F(1)=1}
+	\zahl{4}{F(4)=3}
+\end{scope}
+
+\begin{scope}[yshift=-11cm,scale=1]
+	\begin{scope}
+		\clip (-2,-2.6) rectangle (10.5,2.6);
+		\fibgrid
+	\end{scope}
+	\achsen
+	\begin{scope}
+		\clip (-2,-2.6) rectangle (10.5,2.6);
+		\fibtwo
+		\fibfive
+	\end{scope}
+	\fibcurve
+	\node[color=magenta] at (0.7,1.1) {$n=2$};
+	\node[color=magenta] at (5,1.5) {$n=5$};
+	\zahl{2}{F(2)=1}
+	\zahl{5}{F(5)=5}
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/040-rekursion/linear.tex b/buch/chapters/040-rekursion/linear.tex
index a3ff0c2..33b8043 100644
--- a/buch/chapters/040-rekursion/linear.tex
+++ b/buch/chapters/040-rekursion/linear.tex
@@ -110,25 +110,47 @@ Die Nullstellen des charakteristischen Polynoms
 \qquad
 \lambda_\pm = \begin{cases}
 \displaystyle
-\frac{\sqrt{5}+1}{2}=\varphi
+\frac{1+\sqrt{5}}{2}=\varphi
 \\[8pt]
 \displaystyle
-\frac{\sqrt{5}-1}{2}=\frac{1}{\varphi},
+\frac{1-\sqrt{5}}{2}=-\frac{1}{\varphi},
 \end{cases}
 \]
 dabei ist $\varphi$ das Verhältnis des goldenen Schnittes.
 Die Anfangsbedingungen $F(0)=0$ und $F(1)=1$ bedeutet, dass
-\[
-F(z) = \varphi^z - \frac{1}{\varphi^z}
-\]
-Dies ist die Funktion, die Matt Parker visualisiert hat.
+\begin{equation}
+F(z) = \frac{1}{\sqrt{5}}\varphi^z - \frac{1}{\sqrt{5}}\frac{1}{(-\varphi)^z}
+\label{buch:rekursion:linear:fibonaccifunktion}
+\end{equation}
+Dies ist die Funktion, die Matt Parker in seinem Video visualisiert hat.
+\begin{figure}
+\centering
+\includegraphics[width=0.82\textwidth]{chapters/040-rekursion/images/fibonacci.pdf}
+\caption{Komplexe Fibonacci-Zahlen-Funktion $F(z)$ von
+\eqref{buch:rekursion:linear:fibonaccifunktion}
+dargestellt als Abbildung $\mathbb{C}\to\mathbb{C}$.
+Die ganzzahligen $z$ werden auf die wohlbekannten Fibonacci-Zahlen
+abgebildet.
+Zur besseren Lesbarkeit wird der Wertebereich dreimal dargestellt,
+damit die Bilder der einzelnen reellen Teilintervalle in verschiedene
+Wertebereich-Bilder verteilt werden können.
+$x$-Werte zwischen $3n-\frac12$ und $3n+\frac12$ werden im obersten
+Bildbereich dargestellt, solche zwischen $3n+\frac12$ und $3n+\frac32$ 
+im mittleren und schliesslich solche zwischen $3n+\frac32$ und $3n+\frac52$
+im untersten.
+Die reelle Achse wird auf die grüne Kurve abgebildet.
+\label{buch:rekursion:linear:fibonaccigraph}}
+\end{figure}
+Abbildung~\eqref{buch:rekursion:linear:fibonaccigraph} zeigt die Abbildung
+$z\mapsto F(z)$.
 Allerdings sind die Funktionen
 \[
 F_{kl}(z)
 =
+\frac{1}{\sqrt{5}}
 \varphi^ze^{2k\pi iz}
 -
-\frac{1}{\varphi^z} e^{2l\pi z}
+\frac{1}{\sqrt{5}(-\varphi)^z} e^{2l\pi z}
 \]
 ebenfalls Lösungen der Differenzengleichung mit den gleichen 
 Anfangswerten.