\documentclass{uebungsblatt}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{8}
\gruppe{11}

\begin{document}

\aufgabe

Induktionsvorraussetzung

$ \sum _{i = 1}^n (-1)^{i + 1} i = \frac{1 + (-1)^{n+1} \cdot (2n + 1)}{4} $

Induktionsanfang $n_0 = 1$

$ \sum_{i = 1}^1 (-1)^{i + 1}i = (-1)^{1+1} \cdot 1 = (-1)^2 \cdot 1 = 1 $

$ \frac{1+(-1)^(1+1) \cdot (2 + 1)}{4} = \frac{1 + (-1)^2 \cdot 3}{4} = \frac{1+3}{4} = \frac{4}{4} = 1$

Induktionsschluss

\begin{flalign*}
\sum_{i = 1}^{n + 1} (-1)^{i + 1} i = & \left( \sum_{i = 1}^n (-1)^{i + 1} i \right) + (-1)^{n + 1 + 1} \cdot (n+1) = & \\
 & \left( \sum_{i = 1}^n (-1)^{i + 1} i \right) + (-1)^{n + 2} \cdot (n+1) = & \\
 & \frac{1 + (-1)^{n+1} \cdot (2n + 1)}{4} + (-1)^{n + 2} \cdot (n+1) = & \\
 & \frac{1 + (-1)^{n+1} \cdot (2n + 1)}{4} + \frac{4(-1)^{n + 2} \cdot (n+1)}{4} = & \\
 & \frac{1 + (-1)^{n+1} \cdot (2n + 1) + 4(-1)^{n+2} \cdot (n+1)}{4} = & \\
 & \frac{1 + (-1)^{n+1} \cdot [(2n + 1) + 4(-1)^{-1} \cdot (n+1)]}{4} = & \\
 & \frac{1 + (-1)^{n+1} \cdot [(2n + 1) + (-4) \cdot (n+1)]}{4} = & \\
 & \frac{1 + (-1)^{n+1} \cdot [2n + 1 + (-4n -4)]}{4} = & \\
 & \frac{1 + (-1)^{n+1} \cdot (-2n -3)}{4} = & \\
 & \frac{1 + (-1)^{n+1} \cdot (-1)(2n +3)}{4} = & \\
 & \frac{1 + (-1)^{(n+1) + 1} \cdot (2(n+1) + 1)}{4} & \\
\end{flalign*}

\aufgabe

Induktionsvorraussetzung

$ l_n = \left(\frac{1 + \sqrt{5}}{2} \right)^n + \left(\frac{1 - \sqrt{5}}{2} \right)^n $

Induktionsbasis

$n = 0$

$l_0 = \left( \frac{1 + \sqrt{5}}{2} \right)^0 + \left( \frac{1 - \sqrt{5}}{2} \right)^0 = 1 + 1 = 2 $

$n = 1$

$l_1 = \left( \frac{1 + \sqrt{5}}{2} \right)^1 + \left( \frac{1 - \sqrt{5}}{2} \right)^1 = \frac{1 + \sqrt{5} + 1 - \sqrt{5}}{2} = \frac{2}{2} = 1 $

$n = 2$

$l_2 = \left( \frac{1 + \sqrt{5}}{2} \right)^2 + \left( \frac{1 - \sqrt{5}}{2} \right)^2 = 1 + \frac{1 + \sqrt{5}}{2} + 1 + \frac{1 - \sqrt{5}}{2} =
2 + \frac{1 + \sqrt{5} + 1 - \sqrt{5}}{2} = 2 + 1 = 3 $

$l_2 = l_1 + l_0 = 1 + 2 = 3 $

Induktionsschritt für $n + 1$

\begin{flalign*}
& l_{n+1} = l_{(n+1)-1} + l_{(n+1)-2} = l_n + l_{n-1} = & \\
& \left( \frac{1 + \sqrt{5}}{2} \right)^n \left( \frac{1 - \sqrt{5}}{2} \right)^n + \left( \frac{1 + \sqrt{5}}{2} \right)^{n-1} + \left( \frac{1 - \sqrt{5}}{2} \right)^{n-1} = & \\
& \left( \frac{1 + \sqrt{5}}{2} \right)^n \left( \frac{1 - \sqrt{5}}{2} \right)^n + \frac{\left( \frac{1 + \sqrt{5}}{2} \right)^n}{\frac{1 + \sqrt{5}}{2}} +
\frac{\left( \frac{1 - \sqrt{5}}{2} \right)^n}{\frac{1 - \sqrt{5}}{2}} = & \\
& \frac{\left( \frac{1 + \sqrt{5}}{2} \right)^{n+1}}{\frac{1 + \sqrt{5}}{2}} + \frac{\left( \frac{1 - \sqrt{5}}{2} \right)^{n+1}}{\frac{1 - \sqrt{5}}{2}} + 
\frac{\left( \frac{1 + \sqrt{5}}{2} \right)^n}{\frac{1 + \sqrt{5}}{2}} + \frac{\left( \frac{1 - \sqrt{5}}{2} \right)^n}{\frac{1 - \sqrt{5}}{2}} = & \\
& \frac{ \left( \frac{1 + \sqrt{5}}{2} \right)^{n+1} + \left( \frac{1 + \sqrt{5}}{2} \right)^n}{\frac{1 + \sqrt{5}}{2}} +
  \frac{ \left( \frac{1 - \sqrt{5}}{2} \right)^{n+1} + \left( \frac{1 - \sqrt{5}}{2} \right)^n}{\frac{1 - \sqrt{5}}{2}} = & \\
& \frac{ \left( \frac{1 + \sqrt{5}}{2} \right)^n \left( \frac{1 + \sqrt{5}}{2} \right) + \left( \frac{1 + \sqrt{5}}{2} \right)^n}{\frac{1 + \sqrt{5}}{2}} +
  \frac{ \left( \frac{1 - \sqrt{5}}{2} \right)^n \left( \frac{1 - \sqrt{5}}{2} \right) + \left( \frac{1 - \sqrt{5}}{2} \right)^n}{\frac{1 - \sqrt{5}}{2}} = & \\
& \left( \frac{1 + \sqrt{5}}{2} \right)^n \left( \frac{1 + \sqrt{5}}{2} \right)^n + \left( \frac{1 - \sqrt{5}}{2} \right)^n \left( \frac{1 - \sqrt{5}}{2} \right)^n = & \\
& \left( \frac{1 + \sqrt{5}}{2} \right)^{n+1} + \left( \frac{1 - \sqrt{5}}{2} \right)^{n+1} & \\
\end{flalign*}

\aufgabe

$ (log (n^2))^2 $ vor $ \sqrt{100n} $ vor $ n^{ln ln n} $ vor $ 2^n $

\begin{flalign*}
(log(n^2))^2 & \leq c \cdot \sqrt{100n} & f_4 \in O(f_2)\\
(log(n^2))^2 & \leq 10c \cdot \sqrt{n} & \\
2 \cdot log(n^2) \cdot \frac{2}{n} & \leq \frac{5c}{\sqrt{n}} & Ableitung \\
\frac{4 \cdot log(n^2)}{n} & \leq \frac{5c}{\sqrt{n}} & \\
\frac{8 \cdot log(n)}{n} & \leq \frac{5c}{\sqrt{n}} & \\
8 \cdot log(n) & \leq 5c \cdot \sqrt{n} & c = \frac{8}{5} \\
log(n) & \leq \sqrt{n} & \\
\end{flalign*}

\begin{flalign*}
\sqrt{100n} & \leq c \cdot n^{ln ln n} & f_2 \in O(f_3)\\
10 n^{\frac{1}{2}} & \leq c \cdot n^{ln ln n} & c = 10 \\
n^{\frac{1}{2}} & \leq n^{ln ln n} & \\
\frac{1}{2} & \leq ln ln n & \\
\end{flalign*}

\begin{flalign*}
n^{ln ln n} & \leq c \cdot 2^n & f_3 \in O(f_1)\\
ln (n^{ln ln n}) & \leq ln (c \cdot 2^n) & c = 1\\
ln (n^{ln ln n}) & \leq n \cdot ln(2) & \\
\frac{1}{n} + \frac{ln(ln(n))}{n} & \leq ln(2) & \text{Ableitung} \\
1 + ln(ln(n)) & \leq n \cdot ln(n) & \text{Multiplizieren mit n} \\
\frac{1}{n \cdot ln(n)} & \leq ln(2) & \text{Ableitung} \\
1 & \leq n \cdot ln(n) \cdot ln(2) & \\
0 & \leq ln(n) \cdot ln(2) + ln(2) & \text{Ableitung} \\
0 & \leq \frac{ln (2)}{n} & \\
0 & \leq ln(2) & \\
\end{flalign*}

\aufgabe

\begin{flalign*}
2^{100} \cdot n^2 & \leq c \cdot n^2 & 2^{100} \cdot n^2 \in O(n^2)\\
\frac{2^{100} \cdot n^2}{n^2} & \leq c & \\
2^{100} & \leq c & \\
\end{flalign*}

Dies gilt immer, da man lediglich $ c \geq 2^{100} $ wählen muss.

$\lim \limits_{n \to \infty} \frac{2^n}{e^n} = 
\lim \limits_{n to \infty} \left( \frac{2}{e} \right)^n = 0 $

Daraus folgt $2^n \in o(e^n)$, folglich ist auch $e^n \in \omega(2^n)$.

\end{document}