Ausrollen < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:15 Fr 01.02.2013 | | Autor: | bandchef |
| Aufgabe | Rollen sie diese Rekursionsformel aus:
$T(n) = [mm] 2T(n-1)+n^2$ [/mm] |
Hi Leute!
Ich hab ein Problem mit dem ausrollen einer Rekursionsformel:
$T(n) = [mm] 2T(n-1)+n^2=$
[/mm]
$ = [mm] 2(2T(n-1)+n^2\cdot (n-1))+n^2 [/mm] = $
$ = [mm] 2(2T(n-1)^2+n^2(n-1))-n^2$
[/mm]
Das Ergebnis ist aber laut meiner Lösung nicht richtig. Was mach ich falsch?
Kann mir jemand helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:47 Fr 01.02.2013 | | Autor: | meili |
Hallo,
> Rollen sie diese Rekursionsformel aus:
>
> [mm]T(n) = 2T(n-1)+n^2[/mm]
> Hi Leute!
>
> Ich hab ein Problem mit dem ausrollen einer
> Rekursionsformel:
>
> [mm]T(n) = 2T(n-1)+n^2=[/mm]
> [mm]= 2(2T(n-1)+n^2\cdot (n-1))+n^2 =[/mm]
Nach Rekursionsformel ist $T(n-1) = 2T(n-2) + [mm] (n-1)^2$.
[/mm]
Dies eingesetzt: $T(n) = 2(2T(n-2) + [mm] (n-1)^2) +n^2 [/mm] = $
[mm] $4T(n-2)+2(n-1)^2+n^2$
[/mm]
> [mm]= 2(2T(n-1)^2+n^2(n-1))-n^2[/mm]
>
> Das Ergebnis ist aber laut meiner Lösung nicht richtig.
> Was mach ich falsch?
Wo ist eine Multiplikation, und wo ist T angewendet auf eine Zahl?
>
> Kann mir jemand helfen?
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:54 Fr 01.02.2013 | | Autor: | bandchef |
Das hat mir weitergeholfen: $ T(n-1) = 2T(n-2) + [mm] (n-1)^2 [/mm] $
Der nächste Schritt sieht dann wohl so aus:
$T(n-2) = [mm] 2T(n-3)+(n-2)^2
[/mm]
Das in $ T(n) = 2(2T(n-2) + [mm] (n-1)^2) +n^2 [/mm] = $ eingesetzt ergibt:
$T(n) = [mm] 2(2(2T(n-3)+(n-2)^2)+(n-1)^2)+n^2$
[/mm]
Richtig?
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
