Rekursionsgleichung mit Wurzel

Question

Aufgabe:

Bestimme eine Lösung der folgenden Rekursionsgleichung in Θ-Notation. Du kannst davon ausgehen, dass n eine Potenz von 9 ist.

T (0) = 3,   T (n) = T (n - 3) + $\sqrt{n}$

Problem/Ansatz:

Mein Ansatz wäre, jetzt, da n eine Potenz von 9 ist, 9 einzusetzen und zu gucken, was die Rekursionsgleichung berechnet

T (n) = T (n − 3) + $\sqrt{n}$

T (n) = T (n − 6) + $\sqrt{n-3}$+ $\sqrt{n}$

T (n) = T (n − 9) + $\sqrt{n-6}$+ $\sqrt{n-3}$ + $\sqrt{n}$

Für n = 9 eingesetzt ergebe sich

T (n) = T (9 − 9) + $\sqrt{9-6}$+ $\sqrt{9-3}$ + $\sqrt{9}$

T (0) = T (0) + $\sqrt{3}$+ $\sqrt{6}$ + $\sqrt{9}$

Da laut Basisfall T (0) = 3 gilt, gilt also:

T (0) = 3 + $\sqrt{3}$+ $\sqrt{6}$ + $\sqrt{9}$

Ergäbe also 10,1815, bzw. als allgemeine Gleichung aufgeschrieben

3 + $\sum\limits_{i=0}^{n}{3^{n}}$

Die Musterlösung sagt jedoch, dass die Lösung

Θ (n $\sqrt{n}$

wäre. Aber das wäre ja in diesem Fall (n = 9) dann 9*3 = 27. Und nicht 10,1815.

Kann mir jemand bitte kurz sagen, wo ich den Fehler gemacht habe?

LG

Answer 1

ermittle doch einfach die ersten Werte:

T(0)=3

T(3)=T(0)+sqrt(3)=3+sqrt(3)

T(6)=T(3)+sqrt(6)=3+sqrt(3)+sqrt(6)

T(9)=T(6)+sqrt(9)=3+sqrt(3)+sqrt(6)+sqrt(9)

Also:

$$T(n)=3+\sum\limits_{i=1}^{n}{\sqrt{n}}$$

Und das wächst in der Ordnung n*sqrt(n)

(n=3k)