infostudium.de

von **bugs** » 20.02.07 02:50

Nachdem ich jetzt auch das Lösungsblatt für die linearen Rekursionen gefunden habe, habe ich mal die 2. a) nachgerechnet.

$f(n+2) - f(n) + b(n) = 0$

wobei $b(n) = 1$ oder $b(n) = n$ oder $b(n) = 2^n$ sein soll mit Startwerten $f(0) = f(1) = 0$ und $f(0) = f(1) = 1$ (es gibt also 6 verschiedene Aufgaben.

So wie ich das verstanden habe, bleibt aber die Form für den homogenen Teil doch immer gleich, also mein Ansatz:

charakteristisches Polynom: $x^2 - 1$
Nullstellen: $1,-1$

$f_h(n) = a \cdot 1^n + b \cdot (-1)^n$

Dazu kommt doch dann die partikuläre hinzu ( $f_p(n)$ ), die ja vom inhomogenen Teil abhängt (hier also $1,n$ oder $2^n$

Dafür habe ich mir folgende Ansätze überlegt:

$b_1(n) = 1 = (1 \cdot n^0) \cdot 1^n$
also ein Polynom 0. Grades, da aber $1^n$ schon im homogenen Teil vorkommt, den Grad erhöhen mit max(0+1,1) = 1
also $f_{p1}(n) = (c +d \cdot n) \cdot 1^n$
Hierbei kann ich dann jedoch c wegfallen lassen, da es schon im homogenen Teil dieser Nullstelle vorkommt.
neu: $f_{p1}(n) = (d \cdot n) \cdot 1^n$

$b_2(n) = n = (1 \cdot n^1 + 0 \cdot n^0) \cdot 1^n$
diesmal ein Polynom 1. Grades, aber wieder um eins erhöhen, da Nullstelle im homogenen Teil vorkommt
$f_{p2}(n) = (c + d \cdot n + e \cdot n^2) \cdot 1^n$
und wieder kann c meiner Meinung nach wegfallen:
neu: $f_{p2}(n) = (d \cdot n + e \cdot n^2) \cdot 1^n$

für $b_3(n) = 2^n$ habe ich noch nichts überegt ...
da ich rgendwie jetzt schon nicht ganz die Polynome habe, die eigentlich rauskommen sollten (laut Musterlösung)

Die Lösungen für $b_1(n) = 1$ sind ja noch in Ordnung:
mein Ansatz:
$f_1(n) = a + b \cdot (-1)^n + d \cdot n$
Lösung für f(0)=f(1)=0: $f_1(n) = -\frac{1}{4} + \frac{1}{4} \cdot (-1)^n +\frac{1}{2} \cdot n$
Lösung für f(0)=f(1)=1: $f_1(n) = \frac{3}{4} + \frac{1}{4} \cdot (-1)^n +\frac{1}{2} \cdot n$

aber für $b_2(n) = n$ habe ich nicht die richtige Anzahl von n in meinem Ansatz:
$f_2(n) = a + b \cdot (-1)^n + c \cdot n + d \cdot n^2$ (irgendwie fehlt bei dem b noch ein n ...)
Lösung für f(0)=f(1)=0: $f_2(n) = -\frac{1}{4} \cdot n + \frac{1}{4} \cdot n \cdot (-1)^n + \frac{1}{2} \cdot n^2$
Lösung für f(0)=f(1)=1: $f_2(n) = 1 -\frac{1}{4} \cdot n + \frac{1}{4} \cdot n \cdot (-1)^n + \frac{1}{2} \cdot n^2$

Muss ich den Ansatz anders wählen oder was habe ich hier falsch gemacht? Wie komme ich im homogenen Teil auf die n (wobei ich ja dachte das sich dieser gar nicht ändert, egal wie der inhomogene Teil aussieht)

(zur Vollständigkeit auch noch die Lösungen für $b_3(n) = 2^n$ :
Lösung für f(0)=f(1)=0: $f(n) = -\frac{1}{4} \cdot 2^n + \frac{1}{4} \cdot 2^n \cdot (-1)^n + 2^{-1+n} \cdot n$
Lösung für f(0)=f(1)=1: $f(n) = 1 -\frac{1}{4} \cdot 2^n + \frac{1}{4} \cdot 2^n \cdot (-1)^n + 2^{-1+n} \cdot n$
hier ist auch ein $2^n$ beim Koeffizienten b, was ich mir nicht erklären kann .... (auffällig ist nur, dass diese "hinzugekommenen" Faktoren mit dem inhomogenen Teil übereinstimmen ...)

von kb » 20.02.07 10:43

du hast bis dahin alles richtig gemacht.

wie schon öfter erwähnt sind einige Musterlösungen fehlerhaft, was mich tierisch aufregt. Die Musterlösung zu b(n)=n ist z.B. falsch! (kannst du einfach durch ausrechnen von f(2) sehen. In der Musterlösung n=2 und in der Rekursion n=0 einsetzen).

für b(n)=n² hab ichs noch nicht ausgerechnet, würde mich aber nicht wundern, wenns auch falsch wäre

ich saß selbst ne halbe Stunde daran, alles penibel nachzurechnen, aber als ich keinen Fehler bei mir gefunden hab, hab ich Proben genommen und siehe da, Musterlösung falsch -_-

von **CrazyPumuckl** » 20.02.07 10:47

Also im Moment frage ich mich, ob die Lösungen vom Torsten denn überhaupt stimmen. Er gibt z.B. an, dass für f(0)=f(1)=0, b(n) = n gelten soll: $f(n)=\frac{1}{4}n(-1+(-1)^n+2n)$ .
Wenn man mal f(3) über die Rekursion berechnet, muss ja folgendes gelten:
$f(1+2)-f(1)+1 = 0$ .
(habe also n=1 gesetzt). Dann kann man ja auflösen:
$f(3) -f(1) + 1 = 0 <=> f(3)+1=0 <=> f(3) = -1\ (?!)$ .
Wenn man jetzt aber mal mit der geschlossenen Formel f(3) berechnen möchte komme ich auf: $1/4*3*(-1+(-1)+6) = 3$ . Versteh ich die Rekursion nicht, oder woran hakt es bei mir?

von **CrazyPumuckl** » 20.02.07 10:48

Upps, ich habe wohl gerade zu der Zeit getippt als kb auch gepostet hat - hat sich damit erledigt

von **CrazyPumuckl** » 20.02.07 11:26

@bugs: Könntest Du mal genau posten, wie Du jetzt den Fall b(n)=n gelöst hast? Wie genau macht man jetzt weiter wenn man f_p(n) hat?

von **bugs** » 20.02.07 13:26

ok sehr spaßig der Lehrstuhl...

dann hab ich aber noch ein Problem mit dem Koeffizienten-Vergleich
bei $b_1(n) = 1$ hatte ich ja für $f_{p1}(n) = d \cdot n$

wenn ich das jetzt in die ursprüngliche Gleichung einsetze:

$f_{p1}(n+2) - f_{p1}(n) + 1 = 0 \\ \Leftrightarrow d \cdot (n+2) - d \cdot n + 1 = 0 \\ \Leftrightarrow d \cdot n + 2 \cdot d - d \cdot n + 1 = 0 \\ \Leftrightarrow 2 \cdot d + 1 = 0 \\ \Leftrightarrow d = -\frac{1}{2}$

So habe ich ja für beide Fälle (f(0)=f(1)=0 und f(0)=f(1)=1) für d das gleiche raus.

Ich dachte, man könnte das aber auch über einsetzen der Startwerte berechnen (wie beim homogenen Teil). Dann bekomme ich aber für beide Fälle unterschiedliche Lösungen (da ich nach Einsetzen eh keine Abhängigkeit von n habe (siehe oben):
f(0)=f(1)=0: $2d + 1 = 0 \Rightarrow d= -\frac{1}{2}$
f(0)=f(1)=1: $2d + 1 = 1 \Rightarrow d= 0$
und komme dann aber später beim ausrechnen von a und b auch nicht wirklich weiter. Wieso darf man das denn so nicht machen? (in der Diskussionsstunde hatte der Tutor sowas vorgerechnet)

ok, aber weiter mit $d = -\frac{1}{2}$
dann erhalte ich für a und b (für f(0)=f(1)=0):
$f_1(n) = a + b \cdot (-1)^n -\frac{1}{2} \cdot n \\ f_1(0) = a + b \cdot (-1)^0 -\frac{1}{2} \cdot 0 = 0 \\ f_1(1) = a + b \cdot (-1)^1 -\frac{1}{2} \cdot 1 = 0 \\ \Rightarrow a = \frac{1}{4}, b = -\frac{1}{4} \\ \Rightarrow f_1(n) = \frac{1}{4} - \frac{1}{4} \cdot (-1)^n - \frac{1}{2} \cdot n$

für f(0)=f(1)=1 habe ich folgende Lösung:
$f_1(n) = \frac{5}{4} - \frac{1}{4} \cdot (-1)^n - \frac{1}{2} \cdot n$

jetzt zu $b_2(n) = n$ :
Ansatz: $f_{p2}(n) = c \cdot n + d \cdot n^2$
Einsetzen in Ursprungsgleichung:
$f_{p2}(n+2) = f_{p2}(n) - n \\ \Leftrightarrow c \cdot (n+2) + d \cdot (n \cdot 2)^2 = c \cdot n + d \cdot n^2 - n \\ \Leftrightarrow c \cdot n + 2 \cdot c + d \cdot n^2 + 4 \cdot d \cdot n + 4 \cdot d = c \cdot n + d \cdot n^2 - n \\ \Leftrightarrow 2 \cdot c + 4\cdot d\cdot n + 4 \cdot d = -n \\ \Leftrightarrow (2 \cdot c + 4\cdot d) + (4 \cdot d +1) \cdot n = 0$
über KV komme ich dann auf:
$c = \frac{1}{2}, d= -\frac{1}{4} \\ \Rightarrow f_{p2}(n) = \frac{1}{2} \cdot n - \frac{1}{4} n^2$

damit ist $f_2(n) = a + b \cdot (-1)^n + \frac{1}{2} \cdot n - \frac{1}{4} \cdot n^2$
jetzt wieder a und b über Startwerte bestimmen
für f(0)=f(1)=0:
$f_2(0) = a + b \cdot (-1)^0 + \frac{1}{2} \cdot 0 - \frac{1}{4} 0^2 = 0\\ f_2(1) = a + b \cdot (-1)^1 + \frac{1}{2} \cdot 1 - \frac{1}{4} 1^2 = 0 \\ \Rightarrow a = -\frac{1}{8}, b = \frac{1}{8} \\ \Rightarrow f_2(n) = -\frac{1}{8} + \frac{1}{8} (-1)^n + \frac{1}{2} \cdot n - \frac{1}{4} \cdot n^2$

meine Lösung für f(0)=f(1)=1:
$a= \frac{9}{8}, b= -\frac{1}{8} \\ \Rightarrow f_2(n) = \frac{9}{8} -\frac{1}{8} \cdot (-1)^n + \frac{1}{2} \cdot n - \frac{1}{4} \cdot n^2$

keine Garantie auf Richtigkeit oder Tippfehler, habe nur mal n=4 eingesetzt und das stimmte zumindest mit der Rekursion überein ...

vielleicht hat ja auch jemand die Lösungen für $b(n) = 2^n$ ?

edit:
ich habe für $b_3(n) = 2^n$ folgenden Ansatz gewählt:
$2^n = (1 \cdot n^0) \cdot 2^n\\ \Rightarrow f_{p3}(n) = c \cdot 2^n$ (Pol. 0. Grades, Nullstelle kommt nicht in homogenem Teil vor)

dann komme ich auf die folgenden Lösungen:
für f(0)=f(1)=0:
$f_3(n) = -\frac{1}{6} + \frac{1}{2} \cdot (-1)^n + \frac{1}{3} \cdot 2^n$
für f(0)=f(1)=1:
$f_3(n) = \frac{1}{2} + \frac{1}{6} \cdot (-1)^n + \frac{1}{3} \cdot 2^n$

ich habe das wohl jetzt nicht mehr überprüft ...

von **CrazyPumuckl** » 20.02.07 14:27

Lösungen zu $f_3(n)$ müssen lauten:

$f(0)=f(1)=0:\ f(n)=\frac{1}{2}-\frac{1}{6}\cdot(-1)^n-\frac{1}{3}\cdot2^n$

und

$f(0)=f(1)=1:\ f(n)=\frac{3}{2}-\frac{1}{6}\cdot(-1)^n-\frac{1}{3}\cdot2^n$

von **Mexus** » 21.02.07 18:38

bugs hat geschrieben:Die Lösungen für $b_1(n) = 1$ sind ja noch in Ordnung:
mein Ansatz:
$f_1(n) = a + b \cdot (-1)^n + d \cdot n$
Lösung für f(0)=f(1)=0: $f_1(n) = -\frac{1}{4} + \frac{1}{4} \cdot (-1)^n +\frac{1}{2} \cdot n$

Ich glaub, ich stehe grade total auf dem Schlauch, aber wie kommst du auf $d= \frac{1}{2}$ bei deiner Lösung?
Wenn ich die Anfangswerte $f(0) = f(1) = 1$ einsetze, bekomme ich ja folgendes raus: $0 = a +b$ und $0 = a - b + d$ .
Darf ich $d$ dann nicht frei wählen? Wieso muss es grade $d= \frac{1}{2}$ sein?

von kb » 21.02.07 18:51

das $d\cdot n$ ist der Ansatz für die Inhomogene Lösung. Also $f_p(n)=dn$
bevor du jetzt die Werte einsetzt, musst du d bestimmen! Das geht, indem du $f_p(n)$ in die Rekursion einsetzt.
Also
$f_p(n+2) - f_p(n) + 1 = 0 \\ \Rightarrow d(n+2) - dn + 1 = 0 \\ \Rightarrow d = - \frac{1}{2}$

von **CrazyPumuckl** » 21.02.07 18:52

Du musst den Ansatz d*n in die Rekursionsgleichnung einsetzen:

=> d*(n+2)-d*n+1 = 0, <=> 2d+1=0 <=> d=-1/2

von **Mexus** » 21.02.07 19:17

Ah, vielen Dank, jetzt ist mir ein Licht aufgegangen!

von **bugs** » 21.02.07 22:38

die Lösungen von CrazyPumuckl sind richtig, ich habe mich bei dem Vorzeichen von 1/3 vertan ....

von **Mexus** » 21.02.07 23:41

Mir ist grade was ausgefallen: $b_3(n)= n^2$ laut Aufgabenstellung und nicht $b_3(n)= 2^n$ , hab ich was übersehen oder wieso rechnet ihr die ganze Zeit mit $2^n$ ?

Habe da als Ansatz für $f_{p3}(n)= c \cdot n^3 + d \cdot n^2$ .
Aber danach verhaspel ich mich irgendwo beim Einsetzen. $f_{p3}(n)$ müsste so aber noch richtig sein, oder?

von kb » 22.02.07 00:19

$n^n$ ist richtig, ich weiß auch nicht warum hier $2^n$ steht. Ich habs aber noch nicht gerechnet, darum hier nicht nachgerechnet, und so ists mir auch nicht aufgefallen ^^
Dein Ansatz ist allerdings falsch.
$n^2$ hat Grad 2, aber da 1 eine Nullstelle ist, wird der Grad um 1 erhöht, also Grad 3. Im Homogenen Teil hat das entsprechende Polynom Grad 0, also kann hier der "Grad 0 Teil" weggelassen werden. Der Ansatz lautet dann
$f_p(n)=c\cdot n^3 + d\cdot n^2 + e\cdot n$

von **bugs** » 22.02.07 01:21

ok, ich bin schuld, hab irgendwie immer $2^n$ gelesen in der aufgabenstellung ... (liegt auch vielleicht daran, dass in der falschen lösung andauernd $2^n$ stand bei der dritten version

ich habe das dann auch mal nachgerechnet und für c,d,e folgende Werte:
$c = -\frac{1}{3}\\ d = \frac{1}{2} \\ e = -\frac{1}{6} \\ \Rightarrow f(n) = a + b(-1)^n -\frac{1}{3}n + \frac{1}{2} n^2 -\frac{1}{6} n^3$

Leider bekomme ich danach für a = b = 0 (in beiden Fällen), aber das kommt dann nicht so ganz hin oder? Vielleicht habe ich mich ja auch bei c,d,e verrechnet ...

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] Übung 6, schriftlich, A2 a)

Übung 6, schriftlich, A2 a)

Re: Übung 6, schriftlich, A2 a)