Man kann diese Rekursion z. Bsp. mit der Substitutionsmethode lösen. Setze dazu
\(n= 3^k \Rightarrow T(3^k) = 3T(3^{k-1}) + 3^{k+1}\) mit \(k =0,1,2,\ldots\)
Nun schreibe noch zur Vereinfachung
\(a_k = T(3^k) \Rightarrow \boxed{a_k = 3a_{k-1} + 3^{k+1} \text{ mit } a_0 = T(1)} \quad (1)\).
Hier noch eine kurze Zwischenbemerkung zu den Startwerten:
\(T(0) =T(1) = O(1) \Rightarrow\) Nonsense!
Erstens benötigt die Rekursion nur einen Startwert \(T(1)\). \(T(0)\) macht hier keinen Sinn, da man die Rekursion aufgrund ihrer mathematischen Form nicht bei n=0 starten lassen kann.\(O(1)\) bedeutet nur Beschränktheit, wobei \(T(1)\) sowieso ein konstanter Wert ist.
Lösung der Rekursion (1):
(1) ist eine lineare inhomogene Differenzengleichung.
Die Lösung setzt sich zusammen aus der allgemeinen Lösung \(h_k\) der homogenen Gleichung und einer partikulären Lösung \(p_k\) der inhomogenen Gleichung:
\(a_k = h_k + p_k\)
Lösung der homogenen Gleichung:
\(h_k = 3h_{k-1} \stackrel{\text{Hausaufgabe}}{\Longrightarrow} h_k = a_0 3^k\)
Lösung der inhomogenen Gleichung:
Da die inhomogene Lösung den zusätzlichen Term \(3^{k+1}= 3\cdot 3^k\) liefern muss, kann man hier den folgenden Ansatz wählen:
\(p_k = c_k 3^k\) mit noch zu bestimmenden \(c_k\).
Einsetzen in die inhomogene Gleichung gibt
\(c_k 3^k = 3c_{k-1}3^{k-1} +3^{k+1} \Leftrightarrow c_k - c_{k-1}=3\)
Wegen \(a_0 = h_0 + c_0 \Rightarrow c_0 = 0\)
Somit haben wir
\(c_k - c_{k-1}=3, \: c_0=0 \stackrel{\text{Hausaufgabe}}{\Longrightarrow} c_k = 3k\)
Also haben wir für die partikuläre Lösung
\(p_k =c_k\cdot 3^k = 3k\cdot 3^k = k3^{k+1}\).
Die Rekursion hat also die Lösung:
\(\boxed{a_k = a_03^k + k3^{k+1}}\)
bzw. in der etwas mathematisch laxen Algorithmus-Schreibweise mit
\(n=3^k \Leftrightarrow k = \log_3 n\):
\(\boxed{T(n) = T(1)n + 3n\log_3(n)}\)
Nachtrag zu deiner Frage:
Bis hier hin ist alles richtig:
\(T(n) = 9 T\left(\frac n9\right) + 6n\).
Beim nochmaligen Einsetzen musst du in die Rekursionsgleichung \(\frac n9\) einsetzen. Also
\(T(n) = 9\left( 3T\left(\frac 13\cdot \frac n9 \right)+ 3\cdot \frac n9 \right) + 6n=27 T\left(\frac n{27}\right) + 9n \)
