Fibonacci-Zahlen Beweis < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 2) Fibonacci-Zahlen.
Die Fibonacci-Zahlen [mm] f_{k} [/mm] sind fur k [mm] \in N_{0} [/mm] durch
[mm] f_{0} [/mm] = 0; [mm] f_{1} [/mm] = 1 und [mm] f_{k+2} [/mm] = [mm] f_{k} [/mm] + [mm] f_{k+1}
[/mm]
de finiert.
(ii) Zeigen Sie: Fur k [mm] \ge [/mm] 5 gilt [mm] f_{k} [/mm] = [mm] 5f_{k-4}+3f_{k-5}
[/mm]
(iii) Beweisen Sie mit Hilfe von (ii), dass fur k [mm] \in [/mm] N [mm] f_{5k} [/mm] durch 5 teilbar ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Mahlzeit, gerade mal die zweite Woche an der Uni bin ich mit meinem Latein schon am Ende und bevor ich weiter zurückfalle, wollte ich euch mal um eure Hilfe bitten. Und zwar hänge ich bei Teil (ii) und folglich auch an (iii).
Zu (ii) dache ich mir, das man den Teil durch die vollständige Induktion zeigen kann. Sprich anfangen mit dem Induktionsanfang k=5, [mm] f_{5} [/mm] = [mm] 5f_{5-4}+3f_{5-5}=5f_{1}+3f_{0}=5.
[/mm]
2. Induktionsschritt
[mm] f_{k+1}=5f_{k-3}+3f_{k-4}, [/mm] so nun die Frage wie gehts weiter ?
|
|
| |
|
> 2) Fibonacci-Zahlen.
> Die Fibonacci-Zahlen [mm]f_{k}[/mm] sind fur k [mm]\in N_{0}[/mm] durch
> [mm]f_{0}[/mm] = 0; [mm]f_{1}[/mm] = 1 und [mm]f_{k+2}[/mm] = [mm]f_{k}[/mm] + [mm]f_{k+1}[/mm]
> de finiert.
>
> (ii) Zeigen Sie: Fur k [mm]\ge[/mm] 5 gilt [mm]f_{k}[/mm] =
> [mm]5f_{k-4}+3f_{k-5}[/mm]
> (iii) Beweisen Sie mit Hilfe von (ii), dass fur k [mm]\in[/mm] N
> [mm]f_{5k}[/mm] durch 5 teilbar ist.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Mahlzeit, gerade mal die zweite Woche an der Uni bin ich
> mit meinem Latein schon am Ende und bevor ich weiter
> zurückfalle, wollte ich euch mal um eure Hilfe bitten. Und
> zwar hänge ich bei Teil (ii) und folglich auch an (iii).
>
> Zu (ii) dache ich mir, das man den Teil durch die
> vollständige Induktion zeigen kann. Sprich anfangen mit
> dem Induktionsanfang k=5, [mm]f_{5}[/mm] =
> [mm]5f_{5-4}+3f_{5-5}=5f_{1}+3f_{0}=8.[/mm]
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Gerade, wenn einem die Induktion noch sehr fremd ist, sollte man alles sehr ausführlich aufschreiben.
Den Induktionsanfang für k=5 hast Du.
Es folgt die
Induktionsannahme:
Angenommen, es gilt [mm] f_k=$5f_{k-4}+3f_{k-5}$ [/mm] für ein [mm] k\ge [/mm] 5.
Im Induktionsschritt ist nun zu zeigen, daß die Aussage dann auch für k+1 gilt.
Induktionsschritt:
zu zeigen: dann gilt auch
> [mm]f_{k+1}=5f_{k-3}+3f_{k-4},[/mm] so nun die Frage wie gehts
> weiter ?
Du hast doch noch gar nicht begonnen...
Jetzt erst geht's richtig los.
Beweis:
Es ist [mm] f_{k+1}= [/mm] ...Du mußt hier jetzt so geschickt umformen und irgendwo die Induktionsvoraussetzung einbringen, so daß Du am Ende eine Gleichungskette
[mm] f_{k+1}= ...=...=...=...=...=$5f_{k-3}+3f_{k-4}$
[/mm]
dastehen hast.
Was hast Du denn diesbezüglich schon versucht?
Ich kann das vielleicht auch nicht sofort aus dem Ärmel schütteln.
Ich würde jetzt Papier und Stift suchen und ein Weilchen probieren.
Wenn man Mathe studiert, dann muß man viele Weilchen probieren, viel Papier mit Dingen beschreiben, die in Sackgassen führen - und wenn's gut läuft, hat man am Ende die Lösung.
Die Zeit, die Sackgassen, das Papier sind keine Verschwendung. Man übt, dreht und wendet die Dinge, nimmt sie in die Hand, lutscht mal dran, und lernt, wie man damit umgeht.
Aber machen wir mal weiter.
Ein naheliegender Beginn wäre
[mm] f_{k+1}=f_{k-1}+f_k,
[/mm]
und nun könnte man für [mm] f_k [/mm] die Induktionsvoraussetzung einsetzen.
Aber die Sache ist so noch nicht so ganz befriedigend...
Schön wär's, könnte man die zu beweisende Behauptung auch für [mm] f_{k-1} [/mm] verwenden.
Wenn Du das tust, was bekommst Du dann nämlich?
Problem: Du hast nicht nur das Element direkt vor k+1 verwendet, sondern auch noch das davor, ich meine damit: die Induktionsannahme für k und für k-1 genutzt.
Um dies ungestraft tun zu dürfen, muß der Beginn des Beweise noch etwas erweitert werden:
1. Zeige, daß die Behauptung auch für k=6 gilt.
2. Nimm in der Induktionsannahme an, daß die Behauptung für ein [mm] k\ge [/mm] 5 und für die darauffolgende Zahl k+1 gilt.
Versuch mal und zeig uns bei Rückfragen, was Du tust.
Gruß v. Angela
|
|
|
| |
|
So ich stecke wieder fest, allerdings möchte ich mal den Status Quo darlegen.
Und zwar:
1. Induktionsanfang
Da laut Definition [mm] f_{k+2}=f_{k}+f_{k+1} [/mm] zwei vorherige Glieder benutzt werden, muss im Induktionsanfang die Behauptung für zwei Startwerte nachgewiesen werden.
k=5
[mm] 5f_{5-4}+3f_{5-5}=5f_{1}+3f_{0}=5
[/mm]
k=6
[mm] 5f_{6-4}+3f_{6-5}=5f_{2}+3f_{1}=8
[/mm]
2. Induktionsschritt
Voraussetzung
[mm] f_{k}= 5f_{k-4}+3f_{k-5}
[/mm]
[mm] f_{k+1}= 5f_{k-3}+3f_{k-4}
[/mm]
Zu Zeigen: [mm] f_{k+2}= 5f_{k-2}+3f_{k-3} [/mm]
Beweis: [mm] f_{k+2}=f_{k}+f_{k+1}
[/mm]
nach Voraussetzung: [mm] f_{k+2}=5f_{k-4}+3f_{k-5} [/mm] + [mm] 5f_{k-3}+3f_{k-4}
[/mm]
Das Problem das ich nun hab, liegt darin, dass ich nun nicht weiß wie man weiter umformen soll. Könnt ihr mir vielleich einen Tipp geben ?
LG
|
|
|
| |
|
> So ich stecke wieder fest, allerdings möchte ich mal den
> Status Quo darlegen.
> Und zwar:
>
> 1. Induktionsanfang
>
> Da laut Definition [mm]f_{k+2}=f_{k}+f_{k+1}[/mm] zwei vorherige
> Glieder benutzt werden, muss im Induktionsanfang die
> Behauptung für zwei Startwerte nachgewiesen werden.
>
> k=5
> [mm]5f_{5-4}+3f_{5-5}=5f_{1}+3f_{0}=5[/mm]
>
> k=6
> [mm]5f_{6-4}+3f_{6-5}=5f_{2}+3f_{1}=8[/mm]
>
> 2. Induktionsschritt
>
> Voraussetzung
>
> [mm]f_{k}= 5f_{k-4}+3f_{k-5}[/mm]
> [mm]f_{k+1}= 5f_{k-3}+3f_{k-4}[/mm]
>
> Zu Zeigen: [mm]f_{k+2}= 5f_{k-2}+3f_{k-3}[/mm]
>
> Beweis: [mm]f_{k+2}=f_{k}+f_{k+1}[/mm]
>
> nach Voraussetzung: [mm]f_{k+2}=5f_{k-4}+3f_{k-5}[/mm] +
> [mm]5f_{k-3}+3f_{k-4}[/mm]
Hallo,
...= 5*(...+...)+ 3*(...+...)= 5*...+3*...
In den Klammern verwende die Def. der Fibonacci-zahlen.
Gruß v. Angela
>
> Das Problem das ich nun hab, liegt darin, dass ich nun
> nicht weiß wie man weiter umformen soll. Könnt ihr mir
> vielleich einen Tipp geben ?
>
> LG
|
|
|
| |
|
Super, hab es nun raus. VIELEN DANK. Noch eine Frage zu 2iii)
Rein vom Rechenweg, ist dieser genau so aufgebaut, wie der von von 2ii),so dass ich für den Induktionsanfang k=5 und k=6 wähle und dann die Teilbarkeit durch 5 aufzeige und dann darauf aufbauend die Teilbarkeit von [mm] f_{5k+2} [/mm] ?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:03 Di 19.10.2010 | | Autor: | Loddar |
Hallo Tyler!
Du brauchst hier lediglich den Induktionsanfang für [mm]k \ = \ 1[/mm] machen, da der Induktionsanfang dann sofort [mm]f_{5*1} \ = \ f_5[/mm] ergibt.
Im Induktionsschritt musst Du beginnen mit:
[mm]f_{5*(k+1)} \ = \ f_{5k+5} \ = \ 5*f_{5k+5-4}+3*f_{5k-5} \ = \ ...[/mm]
Gruß
Loddar
|
|
|
|
