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\ge 1$ gezeigt werden soll (wobei $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!\cdot (n-k)!}$ für $0\le k\le n$, den Binomialkoeffizienten bezeichne):

$1+\frac{1}{2}\cdot \sum _{k=1}^n\frac{k\cdot 2^k}{(\genfrac{}{}{0ex}{}{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\mathrm{...}{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\mathrm{...}{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\ge 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\ne x_{j+1}$, für $1\ge j\ge n-1$. Geben Sie $C_n$, für allgemeines $n\ge 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\ge h\ge 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\ge 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:{ℝ}^4\to {ℝ}^3$ eine lineare Abbildung mit folgender Abbildungsmatrix $A\in {ℝ}^{3\times 3}$ bezüglich der kannonischen Basis, also $f(\overrightarrow{x})=A\cdot \overrightarrow{x}:$

$A=\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 4& 5& 6\\ 5& 6& 7& 8\end{array}\right).$

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({ℝ}^{\mathrm{𝟜}})$.

Aufgabe 4 [8 Punkte]

1. Man gebe eine exakte Definition der Restklasse $\overline{z}$ einer ganzen Zahl $z$ modulo $n\{n\in \mathbb{N},n\ge 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\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$?

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

Lösung

Aufgabe 1

Induktionsvoraussetzung: $1+\frac{1}{2}\cdot \sum _{k=1}^n\frac{k\cdot 2^k}{(\genfrac{}{}{0ex}{}{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}{(\genfrac{}{}{0ex}{}{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}{(\genfrac{}{}{0ex}{}{k+2}{k})}=\frac{2^{n+2}}{n+3}$

Induktionsschritt: $n\to n+1$:

$$1+\frac{1}{2}\cdot \sum _{k=1}^{n+1}\frac{k\cdot 2^k}{(\genfrac{}{}{0ex}{}{k+2}{k})}=\frac{2^{n+2}}{n+3}$$$$1+\frac{1}{2}\cdot \sum _{k=1}^n\frac{k\cdot 2^k}{(\genfrac{}{}{0ex}{}{k+2}{k})}+\frac{1}{2}\cdot \frac{(n+1)\cdot 2^{n+1}}{(\genfrac{}{}{0ex}{}{n+3}{n+1})}=\frac{2^{n+2}}{n+3}\mid I.V.einsetzen(1+\mathrm{..})auchsubstituieren$$$$\frac{2^{n+1}}{n+2}+\frac{1}{2}\cdot \frac{(n+1)\cdot 2^{n+1}}{(\genfrac{}{}{0ex}{}{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\mid Indexverschiebungumn+2$$$$D_{n+2}-D_{n+1}-2D_n=0$$$${\lambda }^{n+2}-{\lambda }^{n+1}-2{\lambda }^n=0\mid \cdot \frac{1}{{\lambda }^n}$$$${\lambda }^2-{\lambda }^1-2{\lambda }^0=0\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$$