Chr.Nelius: Lineare Algebra I (WS 2004/05) 3

\underline{(10.22) SATZ:} Rekursive Definition Ein Ausdruck E(n) ist für alle natürlichen Zahlen n ∈ IN eindeutig definiert, wenn man

i) E(0) festlegt, ii) eine Vorschrift angibt, nach der man für alle n ∈ IN den Ausdruck E(n + 1) aus E(n) bestimmen kann.

\underline{(10.23) BEISPIELE:} a) Die \underline{n–te Potenz} x^{n} einer reellen Zahl x (n ∈ IN) x^{0} := 1 , x^{n+1} := x^{n} · x

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

c) \underline{Die Summe von endlich vielen reellen Zahlen} Sei (x_{1}, x_{2}, x_{3}, …) eine Folge reeller Zahlen. Die Summe S_{n} der ersten n Folgenglieder ist definiert durch S_{0} := 0 , S_{n+1} := S_{n} + x_{n+1} (n ∈ IN).

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

Entsprechend kann man die Summe von endlich vielen Vektoren in einem Vektorraum definieren.

d) \underline{Das Produkt von endlich vielen reellen Zahlen} Sei (x_{1}, x_{2}, x_{3}, …) eine Folge reeller Zahlen. Das Produkt P_{n} der ersten n Folgenglieder ist definiert durch P_{0} := 1 , P_{n+1} := P_{n} · x_{n+1} (n ∈ IN).

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

Der Satz (10.22) läßt sich auch noch so verallgemeinern, daß Definitionen folgender Art möglich sind:

e) \underline{Die Fibonacci–Zahlen} Die n–te Fibonacci–Zahl F_{n} (n ∈ IN) 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 n–te Fibonacci–Zahl ist:

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. Beweisen läßt sie sich leicht mit Hilfe vollständiger Induktion.