Vorlesung ALP I - Übung 919500 V Algorithmen und Programmieren I
Wintersemester 2003/2004

Rojas
Gloye

Ü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: 

12+22+32+...+n2=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: 
12+32+52+...+(2*n-1)2=n(4*n2-1)/3 

Aufgabe 3 (4 Punkte)

Eine explizite Methode zur Berechnung der n-ten Finonaccizahl ist (Formel von 
Binet): 
F(n) = (rn-sn) / 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
für alle endlichen Listen x und y die Gleichungen 

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

und 

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
für alle endlichen Listen x und y die Gleichung 
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. 

letzte Änderung am 19. Januar 2004 (Alexander Gloye)