Rekursionssatz: Summation < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen SIe mit Hilfe des Rekursionssatzes: Die Anzahl der Möglichkeiten, die Zahl n als Summe von 1en und 2en zu schreiben, wobei es auf die Reihenfolge der Summation ankommt, ist genau F(n+1).
(Beispiel: Es gibt F(4) = 3 verschiedene Summen für n = 3: 1+1+1, 1+2, 2+1) |
Hallo zusammen,
diese Aufgabe kann ich leider nicht lösen. Angemerkt sei, dass F in der Aufgabe vorher definiert wurde, nämlich die Fibonacci-Zahlen. Allerdings ist nicht klar, ob sie darauf Bezug nimmt.
[mm] (F(n))_{n\in\IN} [/mm]
F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2), [mm] n\ge2
[/mm]
Ich habe es bis n=6 überprüft, und man kommt auf
F(2)=1, F(3)=1, F(4)=3, F(5)=5, F(6)=8, F(7)=13
Wie gehe ich nun vor?
Sei X Menge und S Selbstabbildung mit S: [mm] \IN \to \IN [/mm] \ {n}, n [mm] \in \IN.
[/mm]
Sei F: X [mm] \to [/mm] X mit F(n+1) = F(n) + F(n-1).
Nun definiere ich [mm] \phi: \IN \to [/mm] X mit
(0) F(3)=1, F(2)=1, F(4)=3
(1) [mm] \phi(4)=3 [/mm] mit 4 [mm] \in \IN
[/mm]
(2) [mm] \phi \circ [/mm] S = F [mm] \circ \phi
[/mm]
Das wäre ja jetzt nur das formalisiert, was mir die Aufgabe sagt und was ich vermute. Wie kann ich das nun zeigen?
Danke für Tipps :)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
moin Tee,
Ich frag mich grad wieso man da den Rekursionssatz brauchen sollte.^^
Ich würde es an deiner Stelle erstmal mit einer Induktion versuchen.
Damit ist das wenn man ein wenig nachdenkt gar nicht soo schwer zu beweisen.
Wenn du den Beweis hast dann kriegst du da sicher auch noch den Rekursionssatz irgendwo reingemogelt; und sonst hast du erstmal einen Beweis, der dir bei weiteren Überlegungen sicher weiterhelfen wird.
Vor allem wenn du im Induktionsschluss die Begründung hast, wieso es genau F(n) + F(n-1) Möglichkeiten gibt n+2 als so eine Summe darzustellen hast du den Hauptteil der Aufgabe geschafft, der Rest (Rekursionssatz, etc.) dürften dann nur noch Formalien sein.
lg
Schadow
|
|
|
| |
|
Danke, aber das hilft mir nun nicht viel weiter. Die Aufgabe verlangt es eben, den Rekursionssatz anzuwenden. Ich kann jetzt natürlich es mit Induktion versuchen, aber bei Induktionsschritt werde ich meine Theorie beweisen müssen. Und da bin ich ja nicht durchgestiegen, deswegen habe ich die Frage ja gestellt...
Stimmt es denn, dass es die Fibonacci-Folge ist? Ist das vllt. eine bekannte Aufgabe?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:28 So 30.10.2011 | | Autor: | abakus |
> Danke, aber das hilft mir nun nicht viel weiter. Die
> Aufgabe verlangt es eben, den Rekursionssatz anzuwenden.
> Ich kann jetzt natürlich es mit Induktion versuchen, aber
> bei Induktionsschritt werde ich meine Theorie beweisen
> müssen. Und da bin ich ja nicht durchgestiegen, deswegen
> habe ich die Frage ja gestellt...
>
> Stimmt es denn, dass es die Fibonacci-Folge ist? Ist das
> vllt. eine bekannte Aufgabe?
Nur mal so ein Tipp:
Die Zahl n+1 bekomme ich als Summe von Einsen und Zweien, wenn ich
- entweder zu einer schon vorhandenen Darstellung der Zahl n am Ende noch eine 1 addiere
- oder an eine schon vorhandene Darstellung für die Zahl n-1 am Ende noch den Summanden 2 anfüge.
Somit ist die Anzahl der möglichen Darstellungen der Zahl n+1 gleich der Summe der möglichen Darstellungen von n und n-1.
Gruß Abakus
|
|
|
|
