Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 4.12.2000

\underline{(6.9) SATZ:} Rekursive Definition einer Abbildung Es sei M eine Menge. Eine Abbildung f : IN_{0} ⟶ M ist eindeutig definiert, wenn man

i) f(0) festlegt, ii) eine Vorschrift angibt, nach der man für alle n ∈ IN_{0} den Funktionswert f(n + 1) aus den Funktionswerten f(0), f(1), f(2), …, f(n) bestimmen kann.

\underline{(6.10) BEISPIELE:} a) Die \underline{n–te Potenz} einer reellen Zahl x (n ∈ IN_{0}) p_{x} : IN_{0} ⟶ IR , p_{x}(0) := 1 , p_{x}(n + 1) := p_{x}(n) · x Bezeichnung: p_{x}(n) =: x^{n} .

b) Die \underline{Fakultät} einer natürlichen Zahl: f : IN_{0} ⟶ IN , f(0) := 1 , f(n + 1) := f(n) · (n + 1) Bezeichnung: f(n) =: n! (lies n Fakultät)

c) \underline{Die Summe von endlich vielen reellen Zahlen} Sei (x_{1}, x_{2}, …, x_{n}) (n ∈ IN) eine endliche Folge reeller Zahlen (oder auch ein n–Tupel aus IR^{n}). Die Summe S_{n} aller Folgenglieder ist definiert durch S_{0} := 0 , S_{n} := S_{n−1} + x_{n} (n ∈ IN).

Bezeichnung: S_{n} =: ∑_{k=1}^{n} x_{k}

d) \underline{Das Produkt von endlich vielen reellen Zahlen} Sei (x_{1}, x_{2}, …, x_{n}) (n ∈ IN) eine endliche Folge reeller Zahlen (oder auch ein n–Tupel aus IR^{n}). Das Produkt P_{n} aller Folgenglieder ist definiert durch P_{0} := 1 , P_{n} := P_{n−1} · x_{n} (n ∈ IN).

Bezeichnung: P_{n} =: ∏_{k=1}^{n} x_{k}

e) \underline{Die Fibonacci–Zahlen} Die n–te Fibonacci–Zahl (n ∈ IN_{0}) ist rekursiv definiert durch F_{0} := 0 , F_{1} := 1 , F_{n+1} := F_{n} + F_{n−1} (n ∈ IN).

Eine explizite Formel für die Fibonacci–Zahlen:

F_{n} = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})^{n})

Man kann diese Formel über die “erzeugende Funktion“ der Fibonacci–Zahlen finden. Wenn das Ergebnis bekannt ist, läßt es sich auch mit vollständiger Induktion nachweisen.