Fibonacci < Matrizen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:32 Fr 21.05.2010 | | Autor: | Ayame |
| Aufgabe | Die Folge der Fibonacci-zahlen ist rekursiv definier durch
[mm] f_{0}=0
[/mm]
[mm] f_{1}=1
[/mm]
[mm] f_{n}=f_{n-1}+f_{n-2} [/mm] für n [mm] \ge2.
[/mm]
Sei A := [mm] \pmat{ 1 & 1 \\ 1 & 0 }.
[/mm]
1) Man beweise : [mm] A^{n}:= \pmat{ f_{n+1} & f_{n} \\ f_{n} & f_{n-1} }. [/mm] |
Ich habe es mit der vollständigen Induktion versucht zu beweisen.
n=2
[mm] \pmat{ f_{2+1} & f_{2} \\ f_{2} & f_{2-1} }= \pmat{ f_{3} & f_{2} \\ f_{2} & f_{1} }= \pmat{ 2 & 1 \\ 1 & 1}
[/mm]
[mm] A^{2}= \pmat{ 1 & 1 \\ 1 & 0} [/mm] * [mm] \pmat{ 1 & 1 \\ 1 & 0} [/mm] = [mm] \pmat{ 2 & 1 \\ 1 & 1}
[/mm]
n [mm] \to [/mm] n+1
[mm] A^{n+1} [/mm] = [mm] A^{n} [/mm] * [mm] A^{1} [/mm] = [mm] \pmat{ f_{n+1} & f_{n} \\ f_{n} & f_{n-1} } [/mm] * [mm] \pmat{ 1 & 1 \\ 1 & 0} [/mm] = [mm] \pmat{ f_{n+1} & f_{n} \\ f_{n} & f_{n-1} } [/mm] * [mm] \pmat{ f_{2} & f_{1} \\ f_{1} & f_{0} } [/mm] = [mm] \pmat{ (f_{n+1}*f_{2})+(f_{n}*f_{1}) & (f_{n+1}*f_{1})+(f_{n}*f_{0}) \\ (f_{n}*f_{2})+(f_{n-1}*f_{1}) & (f_{n}*f_{1})+(f_{n-1}*f_{0}) }
[/mm]
Hier komm ich nicht ganz weiter.
Mein Ziel ist ja : [mm] \pmat{ f_{n+2} & f_{n+1} \\ f_{n+1} & f_{n} }
[/mm]
Hätter jemand einen Tipp wie ich in der Matrix zusammenfassen muss ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:41 Fr 21.05.2010 | | Autor: | statler |
Hallo!
> Die Folge der Fibonacci-zahlen ist rekursiv definier durch
> [mm]f_{0}=0[/mm]
> [mm]f_{1}=1[/mm]
> [mm]f_{n}=f_{n-1}+f_{n-2}[/mm] für n [mm]\ge2.[/mm]
>
> Sei A := [mm]\pmat{ 1 & 1 \\ 1 & 0 }.[/mm]
>
> 1) Man beweise : [mm]A^{n}:= \pmat{ f_{n+1} & f_{n} \\ f_{n} & f_{n-1} }.[/mm]
>
> Ich habe es mit der vollständigen Induktion versucht zu
> beweisen.
>
> n=2
>
> [mm]\pmat{ f_{2+1} & f_{2} \\ f_{2} & f_{2-1} }= \pmat{ f_{3} & f_{2} \\ f_{2} & f_{1} }= \pmat{ 2 & 1 \\ 1 & 1}[/mm]
>
> [mm]A^{2}= \pmat{ 1 & 1 \\ 1 & 0}[/mm] * [mm]\pmat{ 1 & 1 \\ 1 & 0}[/mm] =
> [mm]\pmat{ 2 & 1 \\ 1 & 1}[/mm]
>
> n [mm]\to[/mm] n+1
>
> [mm]A^{n+1}[/mm] = [mm]A^{n}[/mm] * [mm]A^{1}[/mm] = [mm]\pmat{ f_{n+1} & f_{n} \\ f_{n} & f_{n-1} }[/mm]
> * [mm]\pmat{ 1 & 1 \\ 1 & 0}[/mm] = [mm]\pmat{ f_{n+1} & f_{n} \\ f_{n} & f_{n-1} }[/mm]
Rechne mal (ohne Einsetzen) mit
[mm] A^{n+1} [/mm] = [mm]A^{n}[/mm] * [mm]A^{1}[/mm] = [mm]\pmat{ f_{n+1} & f_{n} \\ f_{n} & f_{n-1} }[/mm] * [mm]\pmat{ 1 & 1 \\ 1 & 0}[/mm] = ?
und alles wird gut.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:57 Fr 21.05.2010 | | Autor: | Ayame |
Ah Danke. Hatte mal wieder ein Brett vorm Kopf :)
Bei den leichtesten Aufgaben bleibt man immer hängen.
Ein schönes Wochenende wünsch ich noch :)
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:32 Fr 21.05.2010 | | Autor: | Ayame |
| Aufgabe | ii) Besatimme eine Diagonalmatrix D und eine reguläre Matrix S mit [mm] D=S^{-1}AS
[/mm]
ii) Berechne [mm] A^{n} [/mm] mit Hilfe von ii) und gebe eine explizite Darstellung der n-ten Fibonacci-Zahl. |
ii) habe ich lösen können.
iii) ich verstehe nicht ganz wie expliziet das sein soll.
Ich dachte an [mm] A^{n} [/mm] = [mm] (SDS^{-1})^{n}= SD^{n}S^{-1}
[/mm]
aber ist das expliziet genug ??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:50 Fr 21.05.2010 | | Autor: | Marcel |
Hallo,
> ii) Besatimme eine Diagonalmatrix D und eine reguläre
> Matrix S mit [mm]D=S^{-1}AS[/mm]
>
> ii) Berechne [mm]A^{n}[/mm] mit Hilfe von ii) und gebe eine
> explizite Darstellung der n-ten Fibonacci-Zahl.
> ii) habe ich lösen können.
>
> iii) ich verstehe nicht ganz wie expliziet das sein soll.
>
> Ich dachte an [mm]A^{n}[/mm] = [mm](SDS^{-1})^{n}= SD^{n}S^{-1}[/mm]
> aber
> ist das expliziet genug ??
es geht darum, eine explizite Darstellung für [mm] $f_n$ [/mm] anzugeben. Dazu siehe ![[]](/images/popup.gif) Formel von Moivre-Binet, Wiki.
Diese Formel kann man induktiv beweisen, oder aber auch mithilfe von Matrizenrechnung (siehe Wiki-Link); letzteres war mir noch nicht bekannt, aber der Beweis bei Wiki dazu zeigt wohl, warum Deine Aufgabe so ist, wie sie ist. 
P.S.:
Anscheinend gibt es sogar noch mehrere Möglichkeiten,
[mm] $$f_n [/mm] = [mm] \frac{\varphi^n - \psi^n}{\varphi-\psi}, \qquad [/mm] n [mm] \in \mathbb [/mm] Z$$
mit
[mm] $$\varphi [/mm] := [mm] \frac{1+\sqrt 5}2 \text{ und } \psi [/mm] := 1 - [mm] \varphi [/mm] = [mm] \frac{1-\sqrt5}2$$
[/mm]
zu beweisen.
edit: Bzgl. Deiner Vorarbeit passt in dem Wiki-Link wohl Darstellung mit Matrizen, Wiki zu Deiner Aufgabe.
Beste Grüße,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:14 Fr 21.05.2010 | | Autor: | Ayame |
Wie ändert man hier denn den status :( ? ~~abgeschlossen ~~
Danke schön für die Tipps. Ich hab die Aufgabe auch schon fertig.
Danke
|
|
|
|
