Aufgabe 3:
Die Fibonaccizahlen sind induktiv definiert als \( F_{0}:=0, ~ F_{1}:=1 \) und \( F_{n+2}=F_{n}+F_{n+1} \) für \( n \in \mathbb{N}_{0} \)
Zeigen Sie für \( n \in \mathbb{N}_{0} \) :
a) \( \sum \limits_{k=0}^{n} F_{k}=F_{n+2}-1 \)
b) \( \sum \limits_{k=0}^{n} F_{k}^{2}=F_{n} F_{n+1} \)
Aufgabe 4
a) Überprüfen Sie folgende Abbildungen auf Injektivität, Surjektivität und Bijektivität:
(i) \( f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}, f(x)=x^{3} \)
(ii) \( f: \mathbb{N}_{0} \times \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}, f((x, y))=x+y \)
(iii) \( f: \mathbb{N}_{0} \times \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}, f((x, y))=2^{x}(2 y+1)-1 \)
b) Die Menge der ganzen Zahlen \( \{\ldots,-2,-1,0,1,2, \ldots\} \) bezeichnen wir mit \( \mathbb{Z} \).
(i) Gibt es eine Bijektion zwischen \( \mathbb{N} \) und \( \mathbb{Z} \) ? Falls ja, geben Sie eine solche Bijektion an.
(ii) Gibt es eine Bijektion zwischen \( \mathbb{N}^{2}=\mathbb{N} \times \mathbb{N} \) und \( \mathbb{Z} ? \) Falls ja, geben Sie eine solche Bijektion an.