sirokrau
Inhaltsverzeichnis |
Übung 2
Aufgabe 1
\sum\limits_{k=1}^{n} F_{k} = F_{n+2} - 1Induktionsanfang (IA):
z.z. Für n = 1 gilt:
F_{1} = F_{1+2}-1
F_{1} = F_{3}-1 (F_{3} = 2)
1 = 2-1
1 = 1 \Rightarrow OK
Induktionsschritt (IS):
Wenn \sum\limits_{k=1}^{i} F_{k} = F_{i+2} - 1 (Induktionsvoraussetzung, kurz IV),
dann gilt auch: \sum\limits_{k=1}^{i+1} F_{k} = F_{i+3} - 1 (Induktionsbehauptung, kurz IB).
\sum\limits_{k=1}^{i+1} F_{k} = \sum\limits_{k=1}^{i} F_{k} + F_{i+1} \quad \stackrel{IV}{=} F_{i+2} -1 + F_{i+1} = F_{i+3} - 1 (Ergebnis = IB)
Übung 3
Aufzählbarkeit und Entscheidbarkeit (Aufgabe 5)
ÜA: Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist. Zeigen Sie, dass FIBS sogar entscheidbar ist.
f(n) = \begin{cases} g(n), & \text{wenn } g(n);\\ 4, & sonst. \end{cases} g(n) = \begin{cases} 0, & \text{wenn } n=0;\\ 1, & \text{wenn } n=1;\\ g(n-1) + g(n-2), & sonst. \end{cases}ÜA: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen QZ = \{n^2 |n \in \N\}.