Hallo, Hallo,

ich hab leider noch einmal Stress mit einer Rekursionsaufgabe. Die kommt von Krämers Aufgaben mit Lösungen II. Aufgabe 9!

Finde eine explizite Formel für die Rekursion

u0 = 1, u1 = 7, un+2 - 6un+1 +9un = 2^n + n (n >= 0)

Schon der Ansatz der Lösung verwirrt mich.
Wieso wird daraus

(1 -6x +9x^2) ? Meiner Meinung nach hätte eher (x^2 - 6x +) sinn gemacht, aber nun denn.

(1 -6x +9x^2)(u0 + u1x + u2x^2+ …) <==>

u0 + (u1 - 6u0)x + (u2 - 6u1 + 9u0)x^2 + … + (un+2 - 6un+1+9un)x^n+2 + … <==>

So weit, so klar, nu aber:

1 + x +x^2(1 + (2^1 + 1)x + … + (2^n + n)x^n + …)

Wie kommt man denn darauf???

Danke für Eure Infos.

Viele Grüße,
KR

also so weit ich das verstehe hat er da das x und das x^2 ausgeklammert…

das macht für mich keinen Sinn…! Da fehlt irgendwas!!!

wieso? keinen sinn? naja dann hat er sicher noch für U0 1 eingesetzt dann kommt es doch hin oder? *scharfüberleg*

ich spreche davon, wie man auf

1 + x +x^2(1 + (2^1 + 1)x + … + (2^n + n)x^n + …)

kommt. ich hoffe du auch [img]http://www.fb18.de/gfx/9.gif[/img]

u0, u1, usw sind alle wie wegradiert, nur wieso? An x ausklammern kanns doch nicht liegen??? oder mach mir mal genau vor, wie du dann darauf kommst..
danke
kr

also zuersteinmal haben wir hier eine NHLR vorliegen und deshalb ist die Umforumg in(1-6x+9x^2) auch richtig. Bei einer HLR würdest du es so machen wie du es vorgeschlagen hast, mit einer hilfsgleichung, dann nullstellen etc. Warum das so ist haben wir eien STunde in der Vorlesung besprochen udn es steht auch im Biggs. Ich würde es gerne zusammenfassen aber so gut kann ich das dann doch nicht :)

Jetzt aber zu deiner eigentlichen Frage:
Wenn du diese gleichung hast…
u0 + (u1 - 6u0)x + (u2 - 6u1 + 9u0)x^2 + … + (un+2 - 6un+1+9un)x^n+2
musst zuerst für das U0 den wert einsetzen den wir oben bekommen haben. dann die erste Klammer ausrechen was (7-6*1) wäre also 1.
Damit haben wir schonmal 1+x (den anfang). Für die nächsten Koeffizienten gilt immer die Gleichung die wir am anfang bekommen haben: un+2 - 6un+1 +9un = 2^n + n
Damit wissen wir dass in der Gleichung die Formeln für die einzelnen Koeffizienten 2^n+n sind. (WEnn dud a nicht vertsnaden hast warum frag nach weils wichtig ist).
Daher kannst du die Potenzreihe so fortsetzen…
1 + x + x^2 + (2+1)x^3 + (2^2+2)x^4 +…+ (2^n+n)x^(n+2) +…

vor x^2 steht ne 1 da 2^0+0=1 ist.

Jetzt kannst du von dem teil ab x^2, x^2 ausklammern udn erhältst die folgende Potenzreihe…

1 + x + x^2(1 + (2^1 + 1)x + … + (2^n + n)x^n + …)

Warum man das macht? Weil du dadurch eine form bekommst die du meistens umformen kannst in (1-ax)^-m . Wie das geht steht auch im Biggs irgendwo bei HLR und NHLR.
Ich hoffe das war einigermaßen verständlich… Ist eins her umfangreiches Thema und ich treff mich gleich noch mit nem Kommilitonen zum Mathe lernen. Net viel zeit :)

Hallo Buck Naked,

danke für deine umfangreiche Antwort. Hab das aber noch nit alles verstanden. Ich hab mal in deinen Text reinkommentiert..

—

Für die nächsten Koeffizienten gilt immer die Gleichung die wir am anfang bekommen haben: un+2 - 6un+1 +9un = 2^n + n
Damit wissen wir dass in der Gleichung die Formeln für die einzelnen Koeffizienten 2^n+n sind. (WEnn dud a nicht vertsnaden hast warum frag nach weils wichtig ist).
Daher kannst du die Potenzreihe so fortsetzen…
1 + x + x^2 + (2+1)x^3 + (2^2+2)x^4 +…+ (2^n+n)x^(n+2) +…

—

Genau da sitzt mein Problem. Der Anfang ist klar, aber wie rechnen ich konkret das für das x^2 aus???

x^2(1 + (2^1 + 1)x + … + …

das ist für mich konfus [img]http://www.fb18.de/gfx/26.gif[/img]

danke dir

kr

ja ok das ist vielleicht nicht so ganz eindeutig.

wir haben die gleichung un+2 - 6un+1 +9un = 2^n + n (n >= 0)
sprich wir dürfen sie erst anwenden wenn n>= 0 ist.

nun betrachten wir den Term um x^2 der wiefolgt aussieht:
(u2 - 6u1 + 9u0)x^2

er hat also die gleiche Form wie oben unsere Rekursionsgleichung, sprich der Wert in der Klammer (der Koeffizient von x^2) wird gleich dem Wert unserer Rekrusionsgleichung sein, nämlich 2^n+n sein. Jetzt muss man nur noch wissen was n ist. Anfangs macht man immer den fehler und setzt in diesem fall n=2 da wir ja den Koeffizienten von x^2 berechnen wollen. Das ist aber falsch, es gilt n=0 wie man eiegntlich aus der Rekursionsformel erkennen müsste. Warum?

die formel lautet (wiederholung)
un+2 - 6un+1 +9un = 2^n + n
was nichts anderes ist als U2-6U1+9U0 = 2^0+0

ich hoffe das ist dir klar? einfach für n=0 gesetzt. Und genau das wir rausbekommen haben ist der koeffizient für x^2, nämlich 2^0+0 x^2 = 1x^2 = x^2
analog das ganze für x^3, nur dass dann n=1 ist. Für die Koeffizienten von x und dem Konstanten Term können wir diese Gleichung nicht anwenden, da es erst ab n>=0 gilt. Daher sind uns auch immer schon Werte gegeben, in diesem Fall U0 und U1. Wenn die Rekursionsformel noch einen grad mehr hat, also mit Un+3 anfängt brauchen wir auch noch eine Zahl mehr, also U2, da wir erst für den Koeffizienten von x^3 die Formel anwenden können

hehe..ich glaub ich ralle es langsam… aber wirklich ganz langsam. nochmals tausend dank für deine erklärung :-)
was wäre ich ohne die netten leute aus diesem forum ;-)
viele grüße
kr

einfach mal n paar andere übungsaufgaben machen und nachfragen wenn was nicht klappt. irgendwann steigt man schon hinter die methodik

schönen sonntag wünsch ich noch :)

wünsch ich dir auch [img]http://www.fb18.de/gfx/28.gif[/img]
sind im biggs noch aufgaben mit lösungen dazu?
hast du eine Seite, ich hab ehrlich gesagt nichts dazu gefunden
ciao
kr

sorry war bis eben weg lernen und meinen Biggs habe ich im Auto gelassen. Du musst mal im Kapitel Generating Functions nachgucken, der letze Teil dort. NHLR - non homogenious linear recursion oder so. Da wird so ein Beispiel gerechnet. Davor auch ein beispiel zur HLR, die einfacher zu läösen ist mit der Hilfsgleichung. Im Biggs Revised Edtion ist es irgendwo auf Seite 410 glaube ich oder noch n paar Seiten weiter hinten