Hier eine Frage, die mit Hilfe der vollständigen Induktion gelöst / bewiesen werden soll:
„Die Fibonacci-Folge f0 , f1, f2, … ist schrittweise erklärt durch die Folgerungen f0 = 0 , f1 = 1 und fn+2 = fn + fn+1 für alle „n größer gleich 0“.
Sie beginnt also mit 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 usw.
Zeige durch vollständige Induktion:
a) f1 + f2 + …. + fn = fn+2 – 1
b) f1 + f3 + … + f2n-1 = f2n
c) f2 + f4 + …. + f2n = f2n+1 -1
Zeige durch vollständige Induktion nach m die Formel:
fn+m = fn-1 fm + fnfm+1 + fnfm+1 für alle „n größer gleich 1“ und „m größer gleich 0“
Schließe aus a), dass f2n = f2n+1 – f2n-1 und f3n = f3n+1 + f3n – f3n-1 gilt.
(Setze m = n bzw. m=2n)
Tordi
23. April 2003 um 15:03
2
Hallöchen,
hier eine Lösungsmöglichkeit zur Aufgabe 1 a
f(0):=0
f(1):=1
f(n+2):=f(n)+f(n+1)
berechne:
f(2)= f(0)+f(1)= 0+1= 1
f(3)= f(1)+f(2)= 1+1= 2
f(4)= f(2)+f(3)= 1+2= 3
zu zeigen: f(1)+f(2)+…+f(n) = f(n+2)-1
Beweis mittels vollst. Induktion:
Induktionsanfang:
n=2: linke Seite: f(1)+f(2)=1+f(0)+f(1)=1+0+1=2
rechte Seite: f(4) – 1= 3-1= 2
Somit ist rechte Seite gleich linke Seite. Also stimmt die Behauptung für n=2.
Induktionsvoraussetzung / -annahme
f(1)+f(2)+…+f(n)=f(n+2) – 1
Induktionsschluss: hier ist also zu zeigen, dass f(1)+f(2)+…+f(n+1)=f(n+3)-1
n=2, n–>n+1 :
linke Seite: f(1)+f(2)+…f(n+1) =[f(1)+f(2)+…+f(n)] + f(n+1) = [f(n+2) – 1] + f(n+1)
rechte Seite:
Somit ist rechte Seite gleich linke Seite und daraus folgt die Behauptung.
qed.
Mit dieser Ausführung müsstest du die anderen Aufgaben, durch Denkarbeit, auch gelöst bekommen. Ich will dir ja nicht die ganze Denkarbeit abnehmen. Viel Spaß noch bei den anderen Aufgaben.
Gruß
Tordi
a) f1 + f2 + …. + fn = fn+2 – 1
Ind. Anf.:
Ind. Schluss:
q.e.d.
Die anderen gehen im Prinzip genauso. Ansonnsten wär es ganz nett, wenn du dein Problem etwas genauer beschreiben könntest, dies ist schließlich kein Hausaufgaben-Service.