1 Wie man eine geschlossene Darstellung der Fibonacci-Zahlen erh¨ alt Sei G(x) = n≥0 fn xn die erzeugende Funktion der Fibonacci-Zahlen. Um die geschlossene Darstellung dieser zu erhalten, ist fn zu bestimmen. F¨ ur alle n gilt die bekannte Rekursionsformel fn+2 = fn+1 + fn mit dem Rekursionsboden f0 = 0 und f1 = 1. Zuerst multipliziert man die Instanz der Rekursionsformel f¨ ur jedes n mit xn+2 und summiert dann alle Gleichungen auf. fn+2 xn+2 n≥0 fn+1 xn+2 + = n≥0 ⇔ ⇔ G(x) − f1 x − f0 G(x) − x ⇒ G(x) fn xn+2 n≥0 2 = x(G(x) − f0 ) + x G(x) = xG(x) + x2 G(x) x = 1 − x − x2 Die Nullstellen des Nenners sind die Zahlen des Goldenen Schnittes, n¨amlich man: G(x) = = x 1 − x − x2 A + 2√ x−1 −1+ 5 Die Partialbruchzerlegung liefert A = − √15 und B = √1 . 5 √ −1+ 5 2 und √ −1− 5 . 2 Damit erh¨alt B 2√ x −1− 5 −1 Also gilt: 1 1 1 1 G(x) = √ −√ 2√ 2√ 1 − x 1 − x 5 5 −1+ 5 −1− 5 Mit den bekannten Tatsachen u ¨ber die geometrische Reihe folgt: G(x) = = n≥0 n 2 √ x −1 + 5 1 √ 5 n≥0 1 √ 5 2 √ −1 + 5 Daher gilt: 1 fn = √ 5 2 √ −1 + 5 1 −√ 5 n≥0 n − n − 2 √ x −1 − 5 2 √ −1 − 5 2 √ −1 − 5 n n xn n Dieses Ergebnis l¨ asst sich leicht per Induktion beweisen. Das zugrunde liegende Verfahren kann man in Kapitel 8 des Buches “A walk through Combinatorics“ von Mikl´os B´ona, erschienen 2002 bei World Scientific, nachlesen. in LATEX gesetzt von Steffen Melang mail an: [email protected]