Rekursionsgleichung

09.06.2013, 20:12

Chris7

Rekursionsgleichung

Meine Frage:
Hallo Leute,

Ich habe folgende Frage die mir ein wenig Kopfzerbrechen bereitet:

Gegeben sei die Folge <an> n>=0, wobei "an" die Anzahl der Möglichkeiten bezeichnet, ein Rechteck vom Format 1xn mit Steinen vom Format 1x1 bzw. 1x2 lückenlos zu belegen. Stellen Sie für "an" eine Rekursion auf (Hinweis: Betrachten Sie dazu die Differenz a(n)-a(n-1) !) und lösen Sie diese.

Bis dato habe ich folgenden Ansatz:

Meine Ideen:
a(n+2)-a(n+1)=a(n)
a(n+2)-a(n+1)-a(n)=0

Habe anschließend die Charakteristische Gleichung aufgestellt: q^2 - q - 1 = 0

=> Danach mithilfe der Großen Lösungsformel, die Nullstellen:

q1= (1+sqrt(5))/2
q2= (1-sqrt(5)/2

berechnet.

=> Anschließend habe ich die Rekursionsgleichung für a(n) aufgestellt:

a(n)= A *((1+sqrt(5))/2)^n + B * ((1+sqrt(5))/2)^n

Nun muss ich die Konstanten A und B mittels der Anfangswertaufgabe bestimmten.

Meine Frage nun, stimmen meine Rechenschritte bis dato? und wie gehe ich die Anfangswertaufgabe an?

Könnte das so klappen? a(0) = 1 => 1 = A + B
a(1) = 2 => 2= A *((1+sqrt(5))/2)^1 + B * ((1+sqrt(5))/2)^1

Bitte um schnelle Hilfe, ist dringend smile

Danke!

10.06.2013, 22:46

CaptainAwesome

Auf diesen Beitrag antworten »

RE: Rekursionsgleichung
Kennt sich keiner bei diesem Thema aus?

10.06.2013, 23:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Chris7
wobei "an" die Anzahl der Möglichkeiten bezeichnet, ein Rechteck vom Format 1xn mit Steinen vom Format 1x1 bzw. 1x2 lückenlos zu belegen.

Wie kommst du angesichts dieser Definition von $\begin{eqnarray*} a_n \end{eqnarray*}$ auf die beiden Werte

Zitat:

Original von Chris7
a(0) = 1
a(1) = 2

Passender wäre ja wohl $\begin{eqnarray*} a_1=1,a_2=2 \end{eqnarray*}$ , nicht wahr?

Ansonsten kann man nur sagen: Fibonacci-Folge.

Zitat:

Original von CaptainAwesome
Kennt sich keiner bei diesem Thema aus?

Das wird wohl eine mindestens zweistellige Anzahl aktiver Boardnutzer sein, die sich mit der Fibonacci-Folge auf ordentlichem Niveau auskennt. Deswegen kann ich mich jetzt auch in die Nacht verabschieden. Wink

11.06.2013, 03:40

Chris7

Auf diesen Beitrag antworten »

Hallo HAL 9000,

Mein Problem beschränkt sich jetzt nur noch auf die Bestimmung der Koeffizienten A und B,
wenn ich a(1)=1 und a(2)=2 setze wären dann die folgenden zwei Gleichungen, die ich aufstelle um einen Koeffizientenvergleich beginnen zu können, korrekt?

a(1)=1 => 1 = A *((1+sqrt(5))/2)^1 + B * ((1+sqrt(5))/2)^1

=> zusammengefasst: 1= A *q1^1 + B *q2^1

a(2)=2 => 2 = A *((1+sqrt(5))/2)^2 + B * ((1+sqrt(5))/2)^2

=> zusammengefasst: 2= A *q1^2 + B *q2^2

kannst du mir sagen ob meine Überlegung richtig ist? Oder gehe ich es komplett falsch an.

11.06.2013, 08:29

Grautvornix

Auf diesen Beitrag antworten »

Zitat:

Original von Chris7
...kannst du mir sagen ob meine Überlegung richtig ist? Oder gehe ich es komplett falsch an.

Dein Ansatz stimmt nicht ganz. Du unterschlägst das $\begin{eqnarray*} q_2 \end{eqnarray*}$ .

Setze also an mit

$\begin{eqnarray*} a_n=A\cdot q_1^n+B\cdot q_2^n \end{eqnarray*}$

und den Anfangswerten

$\begin{eqnarray*} a_1=1,~a_2=2. \end{eqnarray*}$

11.06.2013, 21:11

Chris7

Auf diesen Beitrag antworten »

Perfekt, jetzt hats klappt smile

Bekomme folgendes heraus:

q1= (1+sqrt(5))/2

q1= (1-sqrt(5))/2

A= (1+sqrt(5))/(2*sqrt(5))

B=(3-sqrt(5))/(5-sqrt(5))

Danke für eure Hilfe!!

12.06.2013, 09:23

Grautvornix

Auf diesen Beitrag antworten »

Zitat:

Original von Chris7
Perfekt, jetzt hats klappt smile

Bekomme folgendes heraus:

$\begin{eqnarray*} q_1 = \frac{1+\sqrt{5}}2 \end{eqnarray*}$

$\begin{eqnarray*} q_2 = \frac{1- \sqrt{5}}2 \end{eqnarray*}$

$\begin{eqnarray*} A = \frac{1+\sqrt{5}}{2\sqrt{5}}=\frac{q_1}{\sqrt{5}} \end{eqnarray*}$

$\begin{eqnarray*} B=\frac{3-\sqrt{5}}{5-\sqrt{5}} \end{eqnarray*}$

Danke für eure Hilfe!!

Speziell mit dem für $\begin{eqnarray*} B \end{eqnarray*}$ angegebenen Wert hat das sicher nicht geklappt!
Rechne noch mal genau nach!

(q_1, q_2 und A stimmen übrigens!)

Neue Frage »

Antworten »

Rekursionsgleichung

Verwandte Themen