path: root/ECM 7.tex

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