Geschlossene Darstellung von rekursiven Folgen?
Hallo,
ich bräuchte Hilfe bei diesem Verfahren, da ich es leider überhaupt nicht verstehe. Ich habe folgendes Beispiel: x1=x2=1 und xn+1= xn + 2xn-1 für n größer gleich 2.
Ich Blicke da jetzt überhaupt nicht durch und weiß gar nicht, was ich da machen soll.
Danke im Voraus ;)
3 Antworten
weiß gar nicht, was ich da machen soll
Am besten ein dummes Gesicht :) Diese Jacobsthal-Folge hat's nämlich in sich! Zum Beispiel kannst Du damit bestimmen, wie viele Krawattenknoten Du mit n+2 Fädelungen binden kannst.
Eine geschlossene Darstellung ist z.B. xₙ = (2ⁿ - (-1)ⁿ)/3. Das kannst Du beweisen, indem Du es für x₁ und x₂ nachrechnest und dann die Formel in die Rekursionsgleichung einsetzt.
Frag mich aber nicht, wie man auf die geschlossene Form kommt. Bestimmt gibt's dafür einen eleganten Kniff. Aber eine Suche in der OEIS ist eben einfacher.
So kommt man ohne Internet auf die geschlossene Form:
xₙ₊₁= xₙ + 2xₙ₋₁ ⇔ (xₙ₊₁ + xₙ) = 2(xₙ + xₙ₋₁)
⇔ (xₙ₊₁ + xₙ) = 2ⁿ ⇔ xₙ₊₁ = 2ⁿ - xₙ
Nun hast Du nur noch n und n+1 in der Formel, und sie expandiert zu
xₙ₊₁ = 2ⁿ - 2ⁿ⁻¹ + 2ⁿ⁻² - ... ± 1
Das ist eine geometrische Reihe mit Faktor q=-2, und dafür kennt man ja die geschlossene Form c·(qⁿ-1)/(q-1).
Eine Methode:
- Einige Folgenglieder aufschreiben. Also 1, 1, 2, 3, 6, 11, usw. (Edit: Achtung, habe mich dabei verrechnet, die stimmen nicht)
- Eine Formel versuchen zu erraten
- Diese beweisen (z.B. durch vollständige Induktion)
Eine andere fällt mir gerade auch nicht ein.
Na, dann konstruieren wir doch mal aus x1 und x2 x3:
x3 = x2 + 2x1 = 1 + 2*1 = 3
und x4
x4 = x3 + 2x2 = 3 + 2*1 = 5
jetzt solltest du aber alleine weiter machen können, oder?
Auch wenn Du die ersten paar Zahlen hast, brauchst Du immer noch eine gute Idee, um daraus eine geschlossene Formel zu berechnen (oder erraten). Selbst bei der Fibonacci-Folge war das einmal eine Aufgabe im Bundeswettbewerb Mathematik (1983).
Bei der Jacobsthal-Folge ist die Sache nicht einfacher. Für eine Hausaufgabe finde ich das recht «sportlich».
Das mag schon sein. Aber dann soll der Fragesteller die Frage so spezifizieren, dass man versteht wo genau seine Probleme sind. Ich hatte hier auch schon Leute, die wußten eben überhaupt nicht was sie mit einer solchen Folge anfangen sollen und habe den Fragesteller in diese Kategorie einsortiert.
Hast ja Recht: „Ich verstehe überhaupt nicht, was ich machen soll“ liest man hier öfter. Und wenn Deine Einschätzung stimmt, ist meine eigene Antwort vermutlich einige Oktaven zu hoch geraten.
Nicht wirklich. Ich verstehe ja überhaupt nicht, was ich da machen soll.
was ich da machen soll
Du sollst eine Formel xₙ=... finden, in der auf der rechten Seite kein x vorkommt. Aber n darf natürlich enthalten sein.
Na ganz so einfach ist es doch nicht.