TU Wien:Algebra und Diskrete Mathematik VU (Panholzer)/Prüfung 2022-02-28

Angabe

Aufgabe 1 [8 Punkte]

Man erläutere das Prinzip der vollständigen Induktion an Hand eines Beweises der folgenden Identität, welche für alle natürlichen Zahlen $n\geq 1$ gezeigt werden soll (wobei ${\binom {n}{k}}={\frac {n!}{k!\cdot (n-k)!}}$ für $0\leq k\leq n$, den Binomialkoeffizienten bezeichne):

$1+{\frac {1}{2}}\cdot \sum _{k=1}^{n}{\frac {k\cdot 2^{k}}{\binom {k+2}{k}}}={\frac {2^{n+1}}{n+2}}$

Aufgabe 2 [8 Punkte = 2 * Anzahl korrekter Punkte]

Im folgenden betrachten wir ternäre Wörter endlicher Länge über dem Alphabet $A={0,1,2}$, also Wörter $w=x_{1}x_{2}...x_{n}$mit $x_{j}\in \{0,1,2\}$ für vorgegebenes $n\in N$.

1. Sei $A_{n}$ die Anzahl der ternären Wörter der Länge $n$, also $A_{n}=\ \mid \{w=x_{1}x_{2}...x_{n}$, mit $x_{j}\in A\}\mid$, für vorgegebenes $n\in N$.
2. Sei $B_{n}$ die Anzahl an ternären Wörtern der Länge $n$, in denen das Symbol 1 genau einmal enthalten ist, für die also gilt: $\mid \{j:x_{j}=1\}\mid$. Geben Sie $B_{n}$ für allgemeines $n\geq 1$ an. Zur Kontrolle: es gilt $B_{1}=1$, $B_{2}=4$.
3. Sei $C_{n}$ die Anzahl der ternären Wörter der Länge $n$, in denen je zwei aufeinanderfolgende Symbole verschieden sind (d.h., die keine Teilwörter 00, 11, oder 22 enthalten), für die also gilt: $x_{j}\neq x_{j+1}$, für $1\geq j\geq n-1$. Geben Sie $C_{n}$, für allgemeines $n\geq 1$, an. Zur Kontrolle: es gilt
   $$C_{1}=3,C_{2}=6$$
   Hinweis: Man überlege sich, wie viele Möglichkeiten es für das 1. Symbol $x_{1}$, dann für das 2. Symbol $x_{2}$, dann für das 3. Symbol $x_{3}$, etc. eines solchen Wortes gibt.
4. Sei $D_{n}$ die Anzahl der ternären Wörter der Länge $n$, in denen je zwei aufeinanderfolgende Symbole mindestens eine 0 enthalten, für die also gilt: $x_{j}\cdot x_{j+1}=0$, für $1\geq h\geq n-1$. Es lässt sich leicht zeigen, dass $D_{n}$ die folgende Differnezengleichung erfüllt (das brauchen Sie aber nicht beweisen, das dürfen Sie voraussetzen):
   $$D_{n}=D_{n-1}+2D_{n-2},n\geq 2,D_{0}=1,D_{1}=3$$
   Man löse diese Differenzengleichung und ermittle so eine allgemeine Formel für $D_{n},n\in N$. Zur Kontrolle: es gilt $D_{2}=5,D_{3}=11$.

Aufgabe 3 [8 Punkte]

Sei $f:\mathbb {R} ^{4}\rightarrow \mathbb {R} ^{3}$ eine lineare Abbildung mit folgender Abbildungsmatrix $A\in \mathbb {R} ^{3\times 3}$ bezüglich der kannonischen Basis, also $f({\vec {x}})=A\cdot {\vec {x}}:$

$A={\begin{pmatrix}1&2&3&4\\3&4&5&6\\5&6&7&8\end{pmatrix}}.$

1. Ermitteln Sie die Dimension des Kerns von $f$, also den Defekt $def(f)$, und bestimmen Sie weiters eine Basis $B$ des Kerns von $f$.
2. Ermitteln Sie den Rang $rg(f)=rg(A)$ von $f$, und bestimmen Sie weiters eine Basis $C$ des Bildraums $f(\mathbb {R^{4}} )$.

Aufgabe 4 [8 Punkte]

1. Man gebe eine exakte Definition der Restklasse ${\bar {z}}$ einer ganzen Zahl $z$ modulo $n\ \{n\in \mathbb {N} ,n\geq 2\}$.
2. Wie ist der Restklassenring $\mathbb {Z} _{n}$ definiert (Definition der Menge als auch der Rechenoperationen)?
3. Geben sie für $n=3$ die Operationstafeln für "$+$" und "$\cdot$" explizit an.
4. Warum ist für $n\not \in \mathbb {P}$, also $n$ nicht prim, der Restklassenring $\mathbb {Z} _{n}$ kein Körper? (Genaue Argumentation verlangt!)

Aufgabe 5 [8 Punkte]

Beantworten Sie die folgenden Fragen bzw. überprüfen Sie die nachstehenden Aussagen zu grundlegenden mathematischen Begriffen (bitte ankreuzen; es können keine, genau eine oder auch mehrere Antworten zutreffend sein; für jede vollständige richtige Antwort gibt es einen Punkt: es wurden für falsche Antworten KEINE Punkte abgezogen).

Wie lautet für die komplexe Zahl $z=1-i$ der Kehrwert ${\frac {1}{z}}$ in kartesischer Darstellung?

• ${\frac {1}{2}}-{\frac {1}{2}}i$
• ${\frac {1}{2}}+{\frac {1}{2}}i$
• $1-i$
• $1+i$

Welche der nachfolgend in Polarkoordinaten angegebenen komplexen Zahlen $w$ erfüllen die Gleichung $w^{2}=1$?

• $\left[1,{\frac {\pi }{2}}\right]$
• $\left[1,\pi \right]$
• $\left[1,{\frac {3\pi }{2}}\right]$
• $\left[1,0\right]$

Lösung

Aufgabe 1

Induktionsvoraussetzung: $1+{\frac {1}{2}}\cdot \sum _{k=1}^{n}{\frac {k\cdot 2^{k}}{\binom {k+2}{k}}}={\frac {2^{n+1}}{n+2}}$

Induktionsanfang: $n=1$: $1+{\frac {1}{2}}\cdot \sum _{k=1}^{1}{\frac {k\cdot 2^{k}}{\binom {k+2}{k}}}=1+{\frac {1}{2}}\cdot {\frac {2}{3}}={\frac {4}{3}}={\frac {2^{2}}{3}}={\frac {4}{3}}$
Induktionsbedingung: $1+{\frac {1}{2}}\cdot \sum _{k=1}^{n+1}{\frac {k\cdot 2^{k}}{\binom {k+2}{k}}}={\frac {2^{n+2}}{n+3}}$

Induktionsschritt: $n\rightarrow n+1$:

$$1+{\frac {1}{2}}\cdot \sum _{k=1}^{n+1}{\frac {k\cdot 2^{k}}{\binom {k+2}{k}}}={\frac {2^{n+2}}{n+3}}$$

$$1+{\frac {1}{2}}\cdot \sum _{k=1}^{n}{\frac {k\cdot 2^{k}}{\binom {k+2}{k}}}+{\frac {1}{2}}\cdot {\frac {(n+1)\cdot 2^{n+1}}{\binom {n+3}{n+1}}}={\frac {2^{n+2}}{n+3}}\quad \mid I.V.einsetzen\ (1+..)\ auch\ substituieren$$

$${\frac {2^{n+1}}{n+2}}+{\frac {1}{2}}\cdot {\frac {(n+1)\cdot 2^{n+1}}{\binom {n+3}{n+1}}}={\frac {2^{n+2}}{n+3}}$$

$${\frac {2^{n+1}}{n+2}}+{\frac {1}{2}}\cdot {\frac {(n+1)\cdot 2^{n+1}}{\frac {(n+3)!}{(n+1)!\cdot 2!}}}={\frac {2^{n+2}}{n+3}}$$

$${\frac {2^{n+1}}{n+2}}+{\frac {1}{2}}\cdot {\frac {(n+1)\cdot (n+1)!\cdot 2^{n+2}}{(n+3)!}}={\frac {2^{n+2}}{n+3}}$$

$${\frac {2^{n+1}}{n+2}}+{\frac {(n+1)(n+1)!\cdot 2^{n+1}}{(n+3)(n+2)(n+1)!}}={\frac {2^{n+2}}{n+3}}$$

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

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

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

$${\frac {2\cdot (n+2)\cdot 2^{n+1}}{n+2}}=2^{n+2}$$

$$2^{n+2}=2^{n+2}$$

Aufgabe 2

1. $A_{n}=3^{n}$
2. $B_{n}=n\cdot 2^{n-1}$
3. $C_{n}=3\cdot 2^{n-1}$
4. $D_{n}={\frac {4}{3}}\cdot 2^{n}-{\frac {1}{3}}\cdot (-1)^{n}$

Lösungsvorschlag zu $D_{n}$:

$$D_{n}=D_{n-1}+2D_{n-2}$$

$$D_{n}-D_{n-1}-2D_{n-2}=0\quad \mid Indexverschiebung\ um\ n+2$$

$$D_{n+2}-D_{n+1}-2D_{n}=0$$

$$\lambda ^{n+2}-\lambda ^{n+1}-2\lambda ^{n}=0\quad \mid \cdot {\frac {1}{\lambda ^{n}}}$$

$$\lambda ^{2}-\lambda ^{1}-2\lambda ^{0}=0\quad \mid pq-Formel$$

$$\lambda _{1,2}=+{\frac {1}{2}}\pm {\sqrt {{\frac {1}{4}}+2}}$$

$$\lambda _{1,2}={\frac {1}{2}}\pm {\sqrt {\frac {9}{4}}}={\frac {1}{2}}\pm {\frac {3}{2}}$$

$$\lambda _{1}=2,\lambda _{2}=-1$$

$$D_{n}=C_{1}\cdot \lambda _{1}^{n}+C_{2}\cdot \lambda _{2}^{n}=C_{1}\cdot 2^{n}+C_{2}\cdot (-1)^{n}$$

$$n=0:D_{0}=C_{1}\cdot \lambda _{1}^{n}+C_{2}\cdot \lambda _{2}^{n}$$

$$n=1:D_{1}=C_{1}\cdot \lambda _{1}^{n}+C_{2}\cdot \lambda _{2}^{n}$$

$$1=C_{1}\cdot 2^{0}+C_{2}\cdot (-1)^{0}$$

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

$$1=C_{1}+C_{2}\Rightarrow C_{2}=1-C_{1}$$

$$3=2C_{1}-C_{2}$$

$$3=2C_{1}-1+C_{1}\Rightarrow 4=3C_{1}\Rightarrow C_{1}={\frac {4}{3}}$$

$$C_{2}=1-C_{1}=1-{\frac {4}{3}}=-{\frac {4}{3}}$$

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