ecm 7

2 files changed, 271 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..765cf1b
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,11 @@
+*.lock
+*.db
+*.aux
+*.bbl
+*.fdb_latexmk
+*.fls
+*.log
+*.out
+*.pdf
+*.synctex.gz
+*.toc
\ No newline at end of file
diff --git a/ECM 7.tex b/ECM 7.tex
new file mode 100644
index 0000000..3a2d0d5
--- /dev/null
+++ b/ECM 7.tex
@@ -0,0 +1,260 @@
+\documentclass[12pt]{article}
+
+% try removing packages if errors happen. package may need to be installed to your Tex Distribution manually.
+
+
+% Encoding and language
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[ngerman]{babel}
+
+% Math
+\usepackage{mathtools}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+
+\newcommand{\lt}{<}
+\newcommand{\gt}{>}
+\newtheoremstyle{customtheorem}
+  {}{}{}{}{\bfseries}{:}{ }{}
+\theoremstyle{customtheorem}
+\newtheorem*{lemma}{Lemma}
+\newtheorem*{theorem}{Satz}
+\renewenvironment{proof}{{\\ \bfseries Beweis:\pushQED{\qed}}}{\popQED\\}
+
+% Graphics
+\usepackage{epsfig}
+\usepackage{graphicx}
+
+% URLs and hyperlinks
+\usepackage{hyperref}
+\usepackage{url}
+
+% Colors
+\usepackage{xcolor}
+
+% Page geometry
+\usepackage[a4paper, margin=2.5cm]{geometry}
+
+% Better tables
+\usepackage{array}
+\usepackage{booktabs}
+
+% Nicer lists
+\usepackage{enumitem}
+
+% For nicer captions (optional)
+\usepackage{caption}
+
+% For code listings (optional)
+\usepackage{listings}
+\lstset{
+  literate={→}{$\rightarrow$}1 {←}{$\leftarrow$}1,
+  basicstyle=\ttfamily
+}
+
+
+
+%footer and header
+\usepackage{fancyhdr}
+%
+\pagestyle{fancy}
+\fancyhf{} % clear defaults
+
+%
+\fancyhead[L]{ \small{Linnea Gräf \& Lexi Naatz}}
+\fancyhead[R]{\small{ Einführung in die computerorientierte Mathematik }}
+\renewcommand{\footrulewidth}{0.4pt}
+\fancyfoot[L]{\small{ Goethe Universität Frankfurt am Main}}
+
+
+\title{Einführung in die computerorientierte Mathematik}
+\author{ Linnea Gräf \& Lexi Naatz \\ Tutorium Gruppe 3 }
+\date{\today}
+
+\begin{document}
+\begin{titlepage}
+        \Huge
+        \maketitle
+\end{titlepage}
+\tableofcontents\pagebreak
+
+\section{Übung 7}
+Weitere Aufgaben hier als \verb|\subsection{}|.
+\subsection{Fibonacci-Zahlen}
+\begin{lemma}
+    $\forall m,n \in \mathbb N : ggT(m, m+n) = ggT(m,n)$.
+    \begin{proof}
+        \begin{align*}
+            ggT(m,m+n) &= ggT((m + n) \mod m, m) \\
+                       &= ggT(((m \mod m) + (n \mod m)) \mod m, m) \\
+                       &= ggT((0 + (n \mod m)) \mod m, m) \\
+                       &= ggT(n \mod m, m) \\
+                       &= ggT(m, n)
+        \end{align*}
+    \end{proof}
+\end{lemma}
+
+\begin{theorem}
+    Zwei auffeinanderfolgende Fibonacci-Zahlen sind teilerfremd.
+    \begin{proof}
+        Zwei Zahlen $a,b$ sind teilerfremd, genau dann wenn $ggT(a,b) = 1$. 
+        Es ist also zu zeigen, dass $ggT(f_a, f_{a+1}) = 1$. Wir benutzen eine Induktion über die natürlichen Zahlen.
+
+        \textbf{Induktionsanfang}. $ggT(f_0, f_1) = ggT(0, 1) = 1$.
+
+        \textbf{Induktionsschritt}. Wir wissen, dass $a > 0$, also ist es für uns möglich $f_{a+1}$ über die rekursive Definition umzuformen. $ggT(f_a, f_{a+1}) = ggT(f_a, f_a + f_{a-1}) = ggT(f_a, f_{a-1})$. Aus der Induktionsvorraussetzung wissen wir, dass $ggT(f_a, f_{a-1}) = 1$.
+
+
+    \end{proof}
+\end{theorem}
+
+Anbei ist eine \href{https://live.lean-lang.org//#codez=HYewLghmCWLABAIkKiEj4F4B88ByUBQ+AJgKYBm8Z0ARvAFzzLyBJhI/PvJwD7wAMG2Xh27wAjALHD4PBAGp4AJgkAKKrWABKePNU14yuWI0bCYABYkQAJxIBbSjQD6ALxJWQ9fbtq8t6Plp0/lZkADb45pY29mqOcCSeyt5GGClB8CHhkdZ2DtSOYADuII4ADqEArgDO+ggMyCacDElqtbIKfvqtmtpdegayosbG9MFhphY59gDmAMZEjlUkoWSOEEQLVtDTZmD69nWMjZ54YAB0c0Tw9sr28j3+pxfz1/B1/tQAnsJWhfAA2k9Lo4bLMADS4KDPBazEC2WwQp7rBa2EBEMFSTiQ86ohZLFaIqGudxrDaEnFoxy4jFYrFA+aOWHwiGABMJsdCQSRZgBdCZRXLA2JVCqzWaOEgARziwASBk8DWEDHpV2SPWSAyGnXE6S+wmgwCIIpgcDe8EK0HMwh4xI8WExvwBsRt5I5NscoXIYAhsXivJEwtF8FK8DMAntf3+sSKJXK1RdyMZcJurVKWkcNNpdKhwPxqwTWx2XvZwKZCJDvIAxLMLLMANbwQVOANiyXShKiXhAA}{Formalisierung des oberen Beweises in Lean4} (mit minimaler Nutzung der Standardbibliothek, außer da wo ich zu faul wurde Aussagen über den ggT zu beweisen.)
+\begin{lstlisting}
+def fib : Nat → Nat
+   | 0 => 0
+   | 1 => 1
+   | n + 2 => (fib n) + (fib (n + 1))
+
+theorem fib_zero : ((fib 0) = 0) := rfl
+theorem fib_one : ((fib 1) = 1) := rfl
+theorem fib_two_plus (n : Nat)
+  : ((fib (n+2) = (fib n) + (fib (n+1)))) := rfl
+
+theorem gcd_self_add_right (m n : Nat)
+  : Nat.gcd m (m + n) = Nat.gcd m n := by
+  rw [Nat.gcd_rec, Nat.gcd_comm, Nat.add_mod,
+      Nat.mod_self, Nat.zero_add, Nat.mod_mod,
+      Nat.gcd_comm, ← Nat.gcd_rec]
+
+theorem gcd_fib_succ_eq_one (n : Nat)
+  : Nat.gcd (fib n) (fib (n+1)) = 1 := by
+  induction n with
+  | zero =>
+    rw [fib_zero, Nat.gcd_zero_left, fib_one]
+  | succ p h =>
+    rw [fib_two_plus, Nat.add_comm (fib p) _,
+        Nat.gcd_self_add_right, Nat.gcd_comm, h]
+\end{lstlisting}
+
+\subsection{Lineare Differenzgleichung}
+Finden Sie für die folgenden linearen Differenzengleichungen eine Lösung:
+\begin{itemize}
+\item $a_n = 7 a_{n-1} - 10 a_{n-2}$ mit $a_0 = 2, a_1 = 3$
+\item $a_n = 6 a_{n-1} - 11 a_{n-2} + 6 a_{n-3}$ mit $a_0 = 3, a_1 = 6, a_2 = 14$
+\end{itemize}
+
+\subsubsection*{Lösung (a): $a_n = 7 a_{n-1} - 10 a_{n-2}$}
+
+Das charakteristische Polynom $\lambda^2 - 7\lambda + 10 = 0$ hat Nullstellen $\lambda_1 = 5$ und $\lambda_2 = 2$.
+
+Die allgemeine Lösung ist $a_n = c_1 \cdot 5^n + c_2 \cdot 2^n$.
+
+Mit den Anfangsbedingungen ergibt sich das Gleichungssystem:
+\begin{align*}
+    c_1 + c_2 &= 2 \\
+    5c_1 + 2c_2 &= 3
+\end{align*}
+
+Lösung: $c_1 = -\frac{1}{3}$, $c_2 = \frac{7}{3}$.
+
+$$
+    \boxed{a_n = -\frac{1}{3} \cdot 5^n + \frac{7}{3} \cdot 2^n}
+$$
+
+\subsubsection*{Lösung (b): $a_n = 6 a_{n-1} - 11 a_{n-2} + 6 a_{n-3}$}
+
+Das charakteristische Polynom $\lambda^3 - 6\lambda^2 + 11\lambda - 6 = 0$ hat Nullstellen $\lambda_1 = 1$, $\lambda_2 = 2$, und $\lambda_3 = 3$.
+
+Die allgemeine Lösung ist $a_n = c_1 + c_2 \cdot 2^n + c_3 \cdot 3^n$.
+
+Mit den Anfangsbedingungen ergibt sich das Gleichungssystem:
+\begin{align*}
+    c_1 + c_2 + c_3 &= 3 \\
+    c_1 + 2c_2 + 3c_3 &= 6 \\
+    c_1 + 4c_2 + 9c_3 &= 14
+\end{align*}
+
+Lösung: $c_1 = 1$, $c_2 = 1$, $c_3 = 1$.
+
+$$
+    \boxed{a_n = 1 + 2^n + 3^n}
+$$
+
+\subsubsection*{Berechnung mit SymPy}
+
+\begin{lstlisting}[language=Python]
+import sympy as sp
+
+# Problem (a): a_n = 7*a_{n-1} - 10*a_{n-2}
+lam = sp.Symbol('lambda')
+char_poly_a = lam**2 - 7*lam + 10
+roots_a = sp.solve(char_poly_a, lam)  # [2, 5]
+
+# Solve linear system for coefficients
+c1, c2 = sp.symbols('c1 c2')
+eq1 = sp.Eq(c1 + c2, 2)        # a_0 = 2
+eq2 = sp.Eq(5*c1 + 2*c2, 3)    # a_1 = 3
+sol_a = sp.solve([eq1, eq2], [c1, c2])
+# sol_a = {c1: -1/3, c2: 7/3}
+
+n = sp.Symbol('n', integer=True, positive=True)
+a_n = sol_a[c1] * 5**n + sol_a[c2] * 2**n
+# a_n = 7*2**n/3 - 5**n/3
+
+# Problem (b): a_n = 6*a_{n-1} - 11*a_{n-2} + 6*a_{n-3}
+char_poly_b = lam**3 - 6*lam**2 + 11*lam - 6
+roots_b = sp.solve(char_poly_b, lam)  # [1, 2, 3]
+
+# Solve linear system for coefficients
+c1, c2, c3 = sp.symbols('c1 c2 c3')
+eq1 = sp.Eq(c1 + c2 + c3, 3)        # a_0 = 3
+eq2 = sp.Eq(c1 + 2*c2 + 3*c3, 6)    # a_1 = 6
+eq3 = sp.Eq(c1 + 4*c2 + 9*c3, 14)   # a_2 = 14
+sol_b = sp.solve([eq1, eq2, eq3], [c1, c2, c3])
+# sol_b = {c1: 1, c2: 1, c3: 1}
+
+b_n = sol_b[c1] + sol_b[c2] * 2**n + sol_b[c3] * 3**n
+# b_n = 2**n + 3**n + 1
+\end{lstlisting}
+
+\subsection{\LaTeX. I}
+
+\begin{theorem}
+    Die Folge 
+    $$
+        x_n := \sum_{k=1}^{N}\frac{1}{k^2}
+    $$
+    ist eine Cauchy-Folge.
+    \begin{proof}
+        Zu zeigen ist: $\forall \varepsilon \gt 0 \exists N \in \mathbb N$
+        mit $\left|x_n - x_m\right|\lt\varepsilon, \forall m,n \gt N$.
+
+        Also
+        \begin{align}
+            \left|x_n - x_m\right|
+                &= \left|\sum_{k=1}^{n}\frac{1}{k^2} - \sum_{k=1}^{m}\frac{1}{k^2}\right| \\
+                &= \sum_{k=m+1}^{n}\frac{1}{k^2} \\
+                &\lt \sum_{k=m+1}^{n}\frac{1}{k(k-1)} \\
+                &= \sum_{k=m+1}^{N}(\frac{1}{k-1} - \frac{1}{k}) \\
+                &= \frac{1}{m} - \frac{1}{n} \stackrel{!}{\lt} \varepsilon
+        \end{align}
+        \dots
+    \end{proof}
+    % {\tiny\textsubscript{i know that there is no \qed in the template but i cant be fucked changing my proof env just for this}}
+\end{theorem}
+
+\subsection{\LaTeX. II}
+
+Ist dieses ganze Dokument \cite{1}.
+
+\pagebreak
+\addcontentsline{toc}{section}{Literatur}
+\begin{thebibliography}{1}
+    \bibitem{1} Donald E. Knuth. \textit{The art of Computer Programming.} Addison-Wesley, 1968-.
+    \bibitem{2} Thorsten Theobald und Saidk Iliman. \textit{Einführung in die computerorientierte Mathematik mit Sage.} Springer-Verlag, 2016.
+\end{thebibliography}
+
+\end{document}