Fibonacci-Zahlen modulo 5 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:28 Fr 20.04.2012 | | Autor: | Malami |
| Aufgabe | Es sei [mm] F_{n} [/mm] eine Fibonacci-Folge, 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] gegeben ist.
Zeige [mm] F_{n} [/mm] = 2n * [mm] 3^{n} [/mm] mod 5 |
Ich bräuchte für diese Aufgabe einen kleinen Rechenanstoß, ich weiß nicht recht, wie ich die Aufgabe richtig angehen kann.
Ich wollte es mit Hilfe vollständiger Induktion lösen. Meine Überlegung:
1. Induktionaanfang [mm] F_{0} [/mm] = 0 = 2*0*1= 0 mod 5
bzw. [mm] F_{1} [/mm] = 1 = 2*1*3 mod 5 = 1 mod 5
2. Induktionsannahme wäre dann für ein n gelte
[mm] F_{n} [/mm] = [mm] 2n*3^{n}
[/mm]
3. Induktionsschritt:
[mm] F_{n+1}= F_{n} [/mm] + [mm] F_{n-1} [/mm] = 2 n * [mm] 3^{n} [/mm] mod 5 + [mm] F_{n-1}
[/mm]
Doch wie kann ich nun [mm] F_{n-1} [/mm] bestimmen? Oder kann ich die Aufgabe überhaupt nicht so lösen.
Vielen Dank schon mal für eure Zeit und Hilfe
|
|
| |
|
moin Malami,
Ändere mal deine Induktionsannahme so ab, dass da nicht "für ein $n [mm] \in \IN$ [/mm] steht sondern "für ein $n [mm] \in \IN$ [/mm] und für $n-1$" (hier natürlich: [mm] $n\geq [/mm] 2$ !). Überlege dir, wieso Induktion dann immer noch funktioniert und ersetze dann sowohl [mm] $F_n$ [/mm] als auch [mm] $F_{n-1}$ [/mm] so wie in der Voraussetzung gegeben.
Sollten sonst noch Fragen offen sein würde ich dir diesen Tread empfehlen, dort findest du vielleicht auch Antworten:
Link
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:12 Fr 20.04.2012 | | Autor: | Malami |
Vielen Dank für die schnelle Hilfe, dann funktioniert das natürlich
|
|
|
|
