Rekursionsgleichung mit doppelter Nullstelle

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Rekursionsgleichung mit doppelter Nullstelle
Hallo zusammen,

es geht um die Aufgabe 1.3) aus der letzten Kompalg-Klausur.

Man soll folgende Rekursion lösen: S(n) = 6S(n-1) - 9S(n-2) mit S(1)=1 und S(2) = 4

Nun hat ja das char. Polynom x^2 - 6x + 9 die doppelte Nullstelle 3.

Dann gilt: S(n) = c13^n + c2n*3^n

Berechnen von c1,c2:

c1 = S(1)
3c1 + 3c2 = S(2)

=> c1 = 1 und c2 = 1/3

=> S(n) = 3^n + 1/3n3^n

Kann das jemand bestätigen? Passt das Ergebnis so?

Ich frage deshalb, weil mich die merkwürdigen Folien zum Fall mehrfacher Nullstellen etwas verwirrt haben und ich mir potenziell leicht zu erreichende Punkte nicht entgehen lassen möchte…

Schonmal Danke :wink:


sers
ich glaub deine konstanten sind falsch
also ich hab schnell mal gerechnet und c1=2/9 c2=1/9 raus
bei dir kommt ja auch bei s(1) = 4 raus

aber ansonsten denk ich das es genau so geht


2/9 und 1/9 hab ich auch.

S(n) = (2/9 + 1/9*n) *3^n = (2+n)*3^(n-2)

@aMw

dein Fehler ist beim einsetzen passiert.
S(n) = (a+b*n) * 3^n

damit ergibt sich für n = 1:
S(1) = (a+b)3 = 1
und für n = 2:
S(2) = (a+2
b) * 9 = 4


Oh stimmt, da hab ich mich vertan :wink:
Aber gut, dass es ansonsten passt.


Nur um die Sache noch ganz zur Lösung zu führen. Ergebnis hab ich ähnlich, nur auf vermutlich anderen Rechenweg gelöst.
Die explizite Lösung ist bei mir 2/3 * 3^n + 1/3 * n * 3^n. Ist ja das gleich nur ausmultipliziert.
Das asymptotische Verhalten wäre dann 1/3 * n * 3^n.

Richtig?


Ausmultipliziert kommt da aber leider nicht das gleiche raus.
Du hast dich wohl bei den Konstanten verrechnet:
S(n) = (a+b*n) * 3^n

damit ergibt sich für n = 1:
S(1) = (a+b)*3 = 1
a = (1 - 3b) / 3 (1)

und für n = 2:
S(2) = (a+2*b) * 9 = 4
a = (4 - 18b)/9 (2)

(1) und (2) gleichsetzen => b = 1/9 und a = 2/9

=> S(n) = (2/9 + 1/9n) 3^n
Und das asymptotische Verhalten wäre dann 1/9
n
3^n


Ok,
dass hab ich jetzt auch verstanden. Da war mein Rechenweg wohl bisschen falsch. Wir hatten in der Übung immer eine Matrix mit den EWs aufgestellt und so das GLS gelöst. Hab wohl die Matrix nicht richtig hingeschrieben.
Aber der andere Rechenweg ist wohl eh der einfachere.

Danke!


Das asymptotische Verhalten ist Teta(n*3^n)!!! Konstanten fliegen doch raus! (oder nicht?)


Das war gemeint als „verhält sich wie: ~n*3^n“ und da lässt man sie ja stehen, soweit ich weiß


Das ist (aus meiner Sicht) richtig und sogar notwendig, denn bei der asymptotischen Äquivalenz: a_n ~ b_n gilt ja (aber hier immer für n → unendlich):

lim (a_n / b_n) = 1

Wenn man bei b_n Konstanten hinzufügt/weglässt, ist der Grenzwert unter Umständen nicht mehr = 1.

Bsp.:
lim (n / n+1) = 1 ==> n ~ n + 1, („n ist asymptotisch äquivalent zu n+1“)
lim (n / 2(n+1) = 0.5 =/=> n ~ 2(n + 1), („n ist asymptotisch nicht äquivalent zu 2(n+1)“)


Auf Wikipedia steht was anderes:

0 < lim |a_n / b_n| < inf

Aber schaden tuts trotzdem nicht, die Konstante stehen zu lassen.


Naja hier werden bisschen verschiedene Dinge vermischt, auf der deutschen Wikipediaseite steht gar nichts zur asymptotischen Äquivalenz( f ~ g), die konsti4u und decyfer gemeint haben. Die findet man nur auf der englischen.
Es ist halt die Frage, was genau gemeint ist, asymptotische Äquivalenz oder “nur” groß Teta.


Na wunderbar… D.h. wenn man nix verschenken will, bleibt nur übrig morgen vor der Klausur zu fragen.


in der klausur steht eigentlich ziemlich groß und deutlich dort:

R(n) = großes Theta (…)


Ja stimmt, hab mir die Angabe nicht angeschaut, nur hier gelesen.

Falls das mal nicht dasteht, kann man ja einfach beides hinschreiben.


Ich denk, der Unterschied kommt schon aus der Formulierung:

asymptotisches Verhalten vs. asymptotische Äquivalenz
(nur weil sich etwas wie etwas anderes verhält, muss es dem nicht äquivalent sein)

Vielleicht interpretiere ich aber da auch zu viel hinein… :nuts:

Im Allgemeinen ist die Äquivalenz wohl genauer als das Verhalten (eben, weil Konstanten nicht weggelassen werden).
In der Klausur würde aber, so denke ich, schon explizit dortstehen, wenn wirklich die Äquivalenz gesucht ist (in der Art: “Gesucht ist eine Funktion g(n), so dass gilt f(n) ~ g(n)”), ansonsten reicht wohl, wie in den Hausaufgaben auch, das groß-Theta.


Bei ner zwei seiten diskussion über so ne belanglosigkeit kann man das wohl so sagen :stuck_out_tongue: