Autor |
Beitrag |
Sharon (Sharon)
| Veröffentlicht am Mittwoch, den 24. Oktober, 2001 - 16:20: |
|
Hallo an euch Lieben! Bin gerade dabei einen Beweis fertig zu stellen, aber ich komme nicht weiter. Heir mein Problem: 1) Die Fibonacci Zahlen a(index)n sind induktiv definiert durch: a(index)0 := 1 , a(index)1 := 1 , a(index)n+1 := a(index)n-1 + a(index)n und das für alle n >= 1. Zu zeigen ist nun: n =< a(index)n =< 2(hoch)n für alle n aus N mit 0 Ich habe nun schon echt lange rumgetüfftelt, aber ich komme auf keinen grünen Zweig. Dankeschön |
matroid
| Veröffentlicht am Mittwoch, den 24. Oktober, 2001 - 19:47: |
|
Hi Sharon, erstens zu zeigen: n<=a(n) Induktionsanfang: n=0 => a(0)=1 >= 0, also richtig. Induktionsvoraussetzung a(n)>=n für alle n<=no, mit einem no>=0 Induktionsbehauptung: a(n+1)>=n+1 für n>0 Nach Rekursionsformel ist a(n+1)=a(n)+a(n-1) Und nach Induktionsvoraussetzung ist a(n)>=n und a(n-1)>=n-1 => a(n+1)>=n+n-1 Außerdem ist n>0. Also entweder n=1 oder n>=2 Wenn n>=2, dann ist n-1>=1 und folglich auch a(n+1)>=n+1. Aber wenn n=1, dann funktioniert diese Abschätzung nicht. Ist aber nicht so schlimm. Lediglich der Induktionsschluß funktioniert nur für n>1. Nehmen wir also a(2)>=2 mit in die Induktionsverankerung. a(2)=a(1)+a(0)=2 => a(2)>=2, also ok. Zweitens zu zeigen: a(n)<=2n Induktionsanfang n=0 => 1<=0, stimmt. Und nach der Erfahrung von eben auch noch die Verankerung für n=1 => 1<=2, stimmt auch. [Man muß hier 2 Werte in der Verankerung prüfen, weil die Rekursion 2 Glieder zurückgeht.] Induktionsvoraussetzung a(n)<=2n für alle n<=no, mit einem no>=1 a(n+1)=a(n)+a(n-1) <= 2n + 2n-1 <= 2n + 2n = 2n+1 Fertig. Gruß Matroid |
Sharon (Sharon)
| Veröffentlicht am Sonntag, den 28. Oktober, 2001 - 21:56: |
|
Vielen Dank Matroid. Ich denke ich habe es kapiert! Viel Spass noch ... |
shaggilla
| Veröffentlicht am Sonntag, den 11. November, 2001 - 18:52: |
|
bonjour mes amis. hmm ich hab nun hier ne aufgabe, mit der ich nicht viel anfangen kann. Es sei u(n) (für n Element der natürlichen Zahlen) die Folge der Fiboacci-Zahlen. Bestimme u(n)²-u(n-2)*u(n+2). für n>=3. |
P
| Veröffentlicht am Sonntag, den 11. November, 2001 - 22:10: |
|
Hallo shaggilla, Bitte für neue Fragen einen neuen Beitrag öffnen. |
|