Übung 9

19. Januar 2004 (Abgabe 28. Januar 2004)

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 (4 Punkte)

Zeigen Sie, dass für die Funktion

sumList [] = 0
sumList (b:y) = b + sumList y

a) sumList (x ++ y) = sumList x + sumList y

b) sumList (x ++ y) = sumList (y ++ x)

gelten.

Aufgabe 5 (2 Punkte)

Beweisen Sie, dass für die Funktion

double [] = []
double (b:y) = (2*b) : double y

double (x ++ y) = double x ++ double y

gilt.

Aufgabe 6 (4 Punkte)

Zeigen Sie, dass für die Funktion length für alle endlichen Listen x und y die Gleichung

a) length (x ++ y) = length x + length y

und für alle endlichen Listen x die Gleichung

b) length (double x) = length x

gilt.