BuK/IIm11/Studenten/sirokrau

Wiki-Quelltext dieser Seite.

== Übung 2 ==

=== Aufgabe 1 ===

$$ \sum\limits_{k=1}^{n} F_{k} =  F_{n+2} - 1$$

Induktionsanfang (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)

<div align="right">$\square $</div>

== Ü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.

ÜA: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 |n \in \N\}.$