Rekursionsgleichung lösen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei folgende Rekursionsgleichung:
R(n) = [mm] 3\*R(n/3)+3,5\*n,
[/mm]
für [mm] n=3^k, [/mm] k [mm] \ge [/mm] 1, und R(1)=0.
1. Lösen Sie diese Rekursionsgleichung, d.h. bestimmen Sie eine geschlossene Form für R(n).
2. Beweisen Sie die Korrektheit Ihrer Lösung. |
Hallo Matheraum ;),
Ich soll diese Aufgabe lösen und hab mir auch schon Gedanken darüber gemacht und einiges gerechnet, aber noch kein Endergebnis bekommen, weil ich dann festhäng. Vllt könnt ihr mir helfen.
So sieht das aus was ich bisher gerechnet habe:
R(n) = [mm] 3\*R(n/3)+3,5\*n
[/mm]
1.Schritt:
[mm] R(3^k)=3\*R(3^k/3)+3,5\*3^k=3\*R(3^{k-1})+3,5\* 3^k
[/mm]
2.Schritt:
[mm] R(3^{k-1})=3\*(3\*R(3^{k-1}/3)+3,5\*3^{k-1})+3,5\*3^k= 3\*(3\*R(3^{k-2})+3,5\*3^{k-1})+3,5\*3^k
[/mm]
3.Schritt:
[mm] R(3^{k-2})=3\*(3\*(3\* R(3^{k-2}/3)+3,5\*3^{k-2})+3,5\*3^{k-1})+3,5\*3^k= 3\*(3\*(3\* R(3^{k-3})+3,5\*3^{k-2})+3,5\*3^{k-1})+3,5\*3^k
[/mm]
[mm] \vdots
[/mm]
ist das erstmal richtig bis hierher?
Da man jetzt schon ganz gut die Regel sieht wie die Gleichung aufgebaut wird habe ich versucht diese verallgemeinert aufzustellen. Allerdings hänge ich da am hinteren Teil davon, da da ja die 3 rausgezogen werden muss. Ich habe eine andere Beispielaufgabe, aus der mir allerdings nicht klar wird, was da gerechnet wird. Kann mir das jemand erklären?
Der vordere Teil müsste so aussehen, wenn ich mich nicht vertan habe:
[mm] 3^i\*R(3^{k-i})+3,5\*\ldots
[/mm]
Wäre schön, wenn mir jemand helfen kann und vielen Dank schon einmal im vorraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:57 Fr 29.10.2010 | | Autor: | leduart |
Hallo
erst mal ist es richtig, ausser deinen gleichzeichen! vorn steht doch immer
[mm] R(3^k) [/mm] und du setzt nur die jeweils kleineren ein.
das hintere ist 3.5* geometrische Reihe allerdings bis du bei k=1 bist von 1 und nicht von 0 an.
ich nehm an du hast [mm] k\ge1 [/mm] und nicht wie geschrieben [mm] k\le [/mm] 1?
Gruss leduart
|
|
|
| |
|
Ich habe mich in der Aufgabenstellung verschrieben. Also in der Aufgabenstellung steht [mm] k\ge1.
[/mm]
kannst du mir das mit der Geometrischen Reihe etwas genauer erklären?
So in etwa? aber ich glaube da fehlt die rausgezogene 3 noch.
[mm] 3^i*R(3^{k-i})+3,5*\summe_{i=0}^{k}3^{k-i}[/mm]
|
|
|
| |
|
Hallo Cherrykiss,
> Ich habe mich in der Aufgabenstellung verschrieben. Also in
> der Aufgabenstellung steht [mm]k\ge1.[/mm]
>
> kannst du mir das mit der Geometrischen Reihe etwas genauer
> erklären?
Es gilt:
[mm]R\left(3^{k}\right)=R\left(3^{k-1}\right)+3,5*3^{k}[/mm]
mit [mm]R\left(3^{0}\right)=R\left(1\right)=0[/mm]
Demnach ergibt sich:
[mm]R\left(3^{1}\right)=R\left(3^{1-1}\right)+3,5*3^{1}=R\left(3^{0}\right)+3,5*3^{1}=R\left(1\right)+3,5*3^{1}[/mm]
[mm]R\left(3^{2}\right)=R\left(3^{2-1}\right)+3,5*3^{2}=R\left(3^{1}\right)+3,5*3^{1}=R\left(1\right)+3,5*3^{1}+3,5*3^{2}[/mm]
Damit kannst Du [mm]R\left(3^{k}\right)[/mm] angeben.
>
> So in etwa? aber ich glaube da fehlt die rausgezogene 3
> noch.
>
> [mm]3^i*R(3^{k-i})+3,5*\summe_{i=0}^{k}3^{k-i}[/mm]
Gruss
MathePower
|
|
|
| |
|
Eine doofe Frage vllt, aber fehlen da nicht die ganzen 3en vor dem R()part?
|
|
|
| |
|
Hallo Cherrykiss,
> Eine doofe Frage vllt, aber fehlen da nicht die ganzen 3en
> vor dem R()part?
Ok, die muss ich wohl übersehen haben.
Dann sieht das so aus:
Es gilt:
[mm] R\left(3^{k}\right)=3*R\left(3^{k-1}\right)+3,5\cdot{}3^{k} [/mm]
mit [mm] R\left(3^{0}\right)=R\left(1\right)=0 [/mm]
Demnach ergibt sich:
[mm] R\left(3^{1}\right)=3*R\left(3^{1-1}\right)+3,5\cdot{}3^{1}=3*R\left(3^{0}\right)+3,5\cdot{}3^{1}=3*R\left(1\right)+3,5\cdot{}3^{1} [/mm]
[mm] R\left(3^{2}\right)=3*R\left(3^{2-1}\right)+3,5\cdot{}3^{2}=3*R\left(3^{1}\right)+3,5\cdot{}3^{1}=3*\left(3*R\left(1\right)+3,5\cdot{}3^{1}\right)+3,5\cdot{}3^{2} [/mm]
Gruss
MathePower
|
|
|
| |
|
Wenn ich das jetzt richtig sehe, komme ich wieder dort raus, wo ich am Anfang war. Und zwar dass ich die Gleichung mit der Summenformel bilden muss.
ich hab dann zwar vorne aus dem R()teil das k raus aber hinten mit dem 3,5*teil ist es trotzdem eine Summe. und deren Bildung hat mir vorhin schon Probleme bereitet.
Überseh ich da irgendwo etwas?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:05 Fr 29.10.2010 | | Autor: | leduart |
Hallo
das ist doch fast die geometische Reihe, deren Summe kennst du doch
schreib die Summe noch mal hin, welkes ist das höchst k, welches das niedrigste?
Gruss leduart
|
|
|
| |
|
genau das möchte ich tun, aber ich weiß nicht wie ich die Summe aufstellen soll. da muss ich doch die 3 mit reinziehen von den klammern und da weis ich nicht wie das geht. das ist mein Problem, was ich relativ zum Anfang auch schon hatte.
den [mm] 3^i\*R(1)+3,5\*\summe_{i=1}^{k} 3^i
[/mm]
ist meiner Meinung nach nicht richtig. Da fehlen die 3er.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:37 Fr 29.10.2010 | | Autor: | leduart |
Hallo
"die 3 er hast du doch vorn als [mm] 3^k [/mm] hinten steht doch nur 3.5* der Summe
Schreib es einfach mal für k=3 oder 4 auf. und lös das Summenzeichen auf.
[mm] 3^i [/mm] vorne ist es natürlich nicht.
wenn du $ [mm] \summe_{i=1}^{k} 3^i [/mm] $ ausrechnen kannst wo liegt dann noch die Schwierigkeit besser ists du schreibst $ [mm] 3.5*(\summe_{i=1}^{k} 3^i) [/mm] $
vielleicht siehst du dann dass es richtig ist?
Gruss leduart
|
|
|
|
