Übung 9

20. Dezember 2001 (Abgabe 14. Januar 2002)

Aufgabe 1 (4 Punkte)

Zeigen Sie durch Induktion, daß für die Summe von Quadratzahlen die folgende Gleichung gilt:

1²+2²+3²+...+n²=n(n+1)(2*n+1)/6

Aufgabe 2 (4 Punkte)

Zeigen Sie durch Induktion, daß folgende Gleichung für die Summe der Quadrate ungerader Zahlen gilt:

1²+3²+5²+...+(2*n-1)²=n(4*n²-1)/3

Aufgabe 3 (4 Punkte)

Eine explizite Methode zur Berechnung der n-ten Finonaccizahl ist (Formel von Binet):

F(n) = (rⁿ-sⁿ) / sqrt(5) mit r = (1+sqrt(5)) / 2, s = (1-sqrt(5)) / 2

Zeigen Sie dies durch Induktion.

Aufgabe 4 (3 Punkte)

Zeigen Sie durch Induktion (nur über die erste Variable), daß die Addition assoziativ ist. Verwenden Sie nur die durch Primitive Rekursion definierte Addition.

Aufgabe 5 (5 Punkte)

Wir haben schon viele Methoden zur Berechnung der Fibonaccizahlen kennengelernt. Die Berchnung über die Formel von Binet (Aufgabe 3 dieses Übungszettels) hat den Nachteil, daß man man die natürlichen Zahlen verläßt und die Berechnung mit reellen Zahlen durchführt. Die Aufgabe durch Verwendung eines Akkumulators (Aufgabe 3 der Klausur) benötigte zur Berechnung der n-ten Fibonaccizahl n Schritte. Über Matrixexponentiation geht es in log₂(n) Schritten!

( 1 1 )n ( 1 )
( 1 0 )  ( 0 )

Die zweite Komponente des Ergebnisses liefert die n-te Fibonaccizahl. Die Exponentiation einer Matrix wird genauso durchgeführt, wie die Exponentiation einer natürlichen Zahl.

Implementieren Sie das Verfahren in Haskell. Benuzten Sie für die Repräsentation der 2x2-Matrix ein 4-Tupel.