\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}