\documentclass[a4paper,12pt]{article}

\usepackage[german]{babel}
\usepackage{amsmath,a4}
\usepackage{amssymb}

\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\R}{{\mathbb R}}


\bibliographystyle{plain}

\begin{document}
\thispagestyle{empty}
\begin{center}
\begin{large}
{\bf \"Ubungen zu Lineare Algebra und Analytische Geometrie I \\
\vspace{0.1cm}
5. {\"U}bungsblatt f{\"u}r den 22.~November 2004}
\end{large}
\end{center}
\vspace{0.1cm}

\begin{enumerate}
\item
 \"Uberpr\"ufen Sie folgende Induktionsbeweise auf ihre Korrektheit:
\begin{enumerate}
\item Alle Pferde haben dieselbe Farbe.

 Wir zeigen: F\"ur jede Menge mit $n$ Pferden gilt: alle $n$ Pferde haben
 dieselbe Farbe. 

 \emph{Bew.} Induktionsanfang: Aussage gilt f\"ur $n = 1$.

 Induktionsschluss von $n$ auf $n+1$: Wir nummerieren die Pferde mit den Zahlen
 $1,\ldots,n+1$. Nach Induktionsannahme haben die $n$ Pferde $1,\ldots,n$ alle
 dieselbe Farbe; ebenso haben die $n$ Pferde $2,\ldots,n+1$ alle dieselbe
 Farbe.
 Somit haben alle $n+1$ Pferde dieselbe Farbe, n\"amlich die der Pferde
 $2,\ldots, n$.


\item $\sum_{i=1}^n i = \frac{n^2+n+1}{2}$ f\"ur alle $n\in\N$.

 \emph{Bew.} Induktionsschluss von $n$ auf $n+1$:\
 $\sum_{i=1}^{n+1} i = \frac{n^2+n+1}{2} + (n+1) = \frac{n^2+3n+3}{2} = \frac{(n+1)^2+(n+1)+1}{2}$, was zu zeigen war.

\end{enumerate}

\item
 Zeigen Sie mit Induktion:
\begin{enumerate}
\item $\sum_{i=1}^{n} i^2 = \frac{1}{6}n(n+1)(2n+1)$ f\"ur alle $n\in\N$. 
\item $(1+a)^n \geq 1+na$ f\"ur alle $a\in \R, a > -1$ und f\"ur alle $n\in\N$
 (Bernoulli'sche Ungleichung).
\end{enumerate}

\item
 Zeigen Sie mit Induktion, dass jede nat\"urliche Zahl eine Bin\"ardarstellung 
 hat, d.h.:
\[ \forall n\in\N_0 \exists k\in\N_0 \exists a_0,\ldots,a_k\in\{0,1\}:\ n = \sum_{i=0}^k a_i 2^i \]


\item
 Seien $n,k \in\N$ mit $k\leq n$, und sei $A = \{1,\ldots,n\}$.
 Zeigen Sie mit Induktion, dass $A$ genau $n\choose k$ Teilmengen
 mit genau $k$ Elementen hat.

 [${n\choose k} = \frac{n!}{k!(n-k)!}$ und $n!= n(n-1) \cdots 3\cdot 2\cdot 1$]


\item
 Verwenden Sie den erweiterten Euklidischen Algorithmus um jeweils den
 gr\"o{\ss}ten gemeinsamen Teiler folgender Zahlen zu bestimmen; geben Sie
 auch das kgV an:
\begin{enumerate}
\item $105, 378$
\item $34, 55$ 
\item $105, 175, 378$
\end{enumerate}     
 
\item 
 Finden Sie jeweils $3$ Paare ganzer Zahlen $(x,y)$ so, dass folgende
 Gleichungen gelten:
\begin{enumerate}
\item $36x+96y = 24$;
\item $36x+96y =-18$;
\item $34x-55y = 4$.
\end{enumerate}

\item
 \"Uberpr\"ufen Sie, ob folgende Relationen $R$ von $A$ nach $B$ funktional,
 reflexiv, symmetrisch, antisymmetrisch oder transitiv sind.
 Geben Sie die inversen Relationen an:
\begin{enumerate}
\item $A = \N, B = P(\N),\ aRb\ :\Leftrightarrow\ a\in b$; 
\item $A = B = [0,1],\ aRb\ :\Leftrightarrow\ a^2+b^2 = 1$;
\item $A = B = \Z,\ aRb\ :\Leftrightarrow\ 2|a+b$;
\item $A = B = \N\setminus 1,\ aRb\ :\Leftrightarrow\ $ggT(a,b) $>1$.
\end{enumerate}

\item
 Zeigen oder widerlegen Sie:
\begin{enumerate}
\item Jede transitive und symmetrische Relation auf einer Menge $A$ ist
      reflexiv.
\item Wenn eine Relation $R$ auf einer Menge $A$ sowohl \"Aquivalenz- 
      als auch Ordnungsrelation ist, dann gilt $R = \{(a,a)\ |\ a\in A\}$.
\end{enumerate}


\end{enumerate}     


\end{document}



