Fibonaccifolge < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:26 Di 17.04.2012 | | Autor: | teo |
| Aufgabe | Sei [mm] F_{n} [/mm] die Fibonaccifolge, die durch
[mm] F_{0} [/mm] = 0, [mm] F_{1} [/mm] = 1, [mm] F_{n} [/mm] = [mm] F_{n-1} [/mm] + [mm] F_{n-2} [/mm] für n [mm] \ge [/mm] 2
definiert ist.
a) Zeigen Sie: [mm] F_{n} \equiv 2n3^{n} [/mm] (mod 5)
b) Ist [mm] F_{2011} [/mm] + 1 durch 5 teilbar? Begründen Sie Ihre Antwort |
Hallo,
ich habe leider keine Ahnung wie ich an diese Aufgabe herangehen soll und wie man Aufgaben diesen Typs generell angeht.
Vielleicht kann mir ja jemand helfen.
Vielen Dank
|
|
| |
|
Zu a)
Da [mm] F_n [/mm] rekursiv definiert ist, liegt es nahe, den Beweis durch vollständige Induktion zu führen. Du zeigtst zuerst, dass die Beh. für [mm] F_0 [/mm] und [mm] F_1 [/mm] gilt. Dann nimmst du an, dass sie für alle k<n gilt, also auch für [mm] F_{n-1} [/mm] und [mm] F_{n-2}. [/mm] Nun zeigst du, dass sie dann für [mm] F_n, [/mm] also [mm] F_{n-1} [/mm] + [mm] F_{n-2} [/mm] gilt (deshalb musst du den Induktionsanfang für die beiden ersten und nicht nur für das erste Glied machen, weil du für die Bildung von [mm] F_n [/mm] immer 2 aufeinanderfolgende Glieder brauchst).
zu b)
Schreibe [mm] F_{2011} [/mm] als [mm] 2*2011*3^{2011} [/mm] mod 5 und vereinfache durch mod-Rechnung so lange, bist du herausbekommst, dass man dafür auch -1 mod 5 schreiben kann. (Tipp: [mm] 3^2=9^2=(-1)^mod [/mm] 5, d.h. jeder Faktor [mm] 3^2 [/mm] kann bei mod 5 als -1 verrechnet werden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:47 Mi 18.04.2012 | | Autor: | teo |
Stimmt die Lösung?
Also Induktionsanfang lass ich weg ist klar und es muss auch besser aufgeschrieben werden aber die Rechnung:
[mm] F_{n} [/mm] = [mm] F_{n-1} [/mm] + [mm] F_{n-2} [/mm] also:
[mm] F_{n} \equiv 2(n-1)3^{n-1} [/mm] + [mm] 2(n-2)3^{n-2}(mod [/mm] 5)
[mm] \gdw F_{n} \equiv 3^{n-2}(2(n-1)3 [/mm] + 2(n-2)) (mod5)
[mm] \gdw F_{n} \equiv 3^{n-2}(8n [/mm] - 10) (mod 5=
[mm] \gdw F_{n} \equiv [/mm] 3^(n-2)18n (mod 5)
[mm] \gdw F_{n} \equiv 2n3^{n} [/mm] (mod5)
Danke
|
|
|
| |
|
> Stimmt die Lösung?
>
> Also Induktionsanfang lass ich weg ist klar und es muss
> auch besser aufgeschrieben werden aber die Rechnung:
>
> [mm]F_{n}[/mm] = [mm]F_{n-1}[/mm] + [mm]F_{n-2}[/mm] also:
>
> [mm]F_{n} \equiv 2(n-1)3^{n-1}[/mm] + [mm]2(n-2)3^{n-2}(mod[/mm] 5)
> [mm]\gdw F_{n} \equiv 3^{n-2}(2(n-1)3[/mm] + 2(n-2)) (mod5)
> [mm]\gdw F_{n} \equiv 3^{n-2}(8n - 10) (mod 5=)[/mm]
Hier vielleicht noch als Zwischenschritt:
[mm]\gdw F_{n} \equiv 3^{n-2}((2*5+8)n - (2*5)) (mod 5=)[/mm]
> [mm]\gdw F_{n} \equiv[/mm] 3^(n-2)18n (mod 5)
> [mm]\gdw F_{n} \equiv 2n3^{n}[/mm] (mod5)
>
> Danke
![[ok]](/images/smileys/ok.gif "[ok]")
|
|
|
|
