Analyse durch Rekursionsgleichung

Question

Aufgabe:

Lösen Sie die folgende Rekursionsgleichung durch iteratives Einsetzen. Verwenden Sie zum Lösen der Gleichung keine Abschätzung, d.h. Iösen Sie die Gleichung vollständig auf. Geben Sie anschließend eine Abschätzung durch die \( \mathcal{O} \)-Notation an.

\( \begin{array}{l} T(0)=0 \\ T(n)=T(n-1)+n^{2} \end{array} \)

Folgende Formel dürfen Sie ohne Beweis verwenden:

\( \sum \limits_{j=0}^{n} j^{2}=\frac{1}{6} n(n+1)(2 n+1) \)

Problem/Ansatz:

Verstehe nicht ganz was getan werden soll, beziehungsweise zu welchem Ergebnis man genau kommen soll. Ich habe für n 1, 2, 3, 4 .... n eingesetzt und versucht T(n) zu bestimmen. Ist das überhaupt der richtige Ansatz?

Answer 1

Du kannst die Rekursion durch eine Teleskopsumme auflösen:

$$T(n) = (T(n) - T(n-1)) + (T(n-1) - T(n-2)) + \cdots + (T(1) - T(0)) + T(0)$$

Also mit \(T(0)=0\) hast du mit der gegebenen Formel

$$T(n) = \sum_{k=1}^n(T(k)-T(k-1)) = \sum_{k=1}^nk^2 = \frac 16 n(n+1)(2n+1)$$