| Autor |
Beitrag |
    
milena
| | Veröffentlicht am Dienstag, den 06. März, 2001 - 22:35: | 
|
Wie zeige ich,
a) ...,dass die Fibonacci-Folge
(yn)=(1,1,2,3,5,8,13,...) monoton wachsend ist
b) ..., dass für sie 2y(n-2) < yn < 2y(n-1) gilt
c) ..., dass sich daraus dann ergibt:
yn < 2^(n-1) und y2m > 2^m ,
also yn > 2^((n-1)/2)
Es wäre super cool, wenn mir möglichst schnell jemand helfen könnte... 1000dank!! milena |
revo
| | Veröffentlicht am Mittwoch, den 07. März, 2001 - 10:25: |
|
yn=y(n-1)+y(n-2) y0=0 y1=1
a) zu zeigen ist yn <= y(n+1) (kleiner,gleich)
zwei möglichkeiten:
1. einfach argumentieren, daß Folge eine folge natürlicher zahlen ist, und sich y(n+1) ergibt, indem ich zu yn eine ander zahl aus der folge addiere. wenn ich zu einer zahl eine natürliche zahl hinzuaddiere, ist die summe natürlich größer.
2. vollständige induktion: (hier nur angedeutet)
anfang: y0<y1=y2<y3<y4
voraussetzung: yn <= y(n+1)
und y(n-1) <= yn für n>=2 mit yn=y(n-1)+y(n-2)
Behauptung: y(n+1)<=y(n+2)
| beweis: | y(n+1)=y(n)+y(n-1) | | y(n+2)=y(n+1)+yn | | (abschätzung: ) | yn + y(n-1)<= yn + yn | | y(n+1)+ yn>=yn + yn |
(nach voraussetzung)
y(n+1) <= 2*yn = 2*yn <= y(n+2) W.z.B.w. |
revo
| | Veröffentlicht am Mittwoch, den 07. März, 2001 - 10:56: |
|
b) funktioniert auch über vollständige induktion mit einer abschätzung. am besten ist, wenn man die aussagen trennt in:
yn > 2 * y(n-2)
yn < 2 * y(n-1)
probier es einfach selber mal und schick mir eine e-mail, wenn du die lösung brauchst
PS: c) probiere ich gleich |
revo
| | Veröffentlicht am Mittwoch, den 07. März, 2001 - 13:58: |
|
also zu c)
yn<2^(n-1)
für n=1 ist yn=1 und zn=2^(n-1)=1. wenn das n nun größer wird verdoppelt sich zn [z(n+1)=2^n=2^(n-1)*2=zn*2]. yn verdoppelt sich nicht wenn ich das n um eins vergrößere [y(n+1)=yn+y(n-1)<yn+yn=2*yn weil yn>y(n-1) für n>2 - siehe a)] somit kann man die obige abschätzung machen. (kanst du ja noch mit induktion beweisen)
bei dem rest bin ich nicht sicher was du meinst.
y2m > 2^m und 2m=n ergibt sich yn > 2^(n/2) und nicht yn > 2^((n-1)/2) |
|
