Geschlossene Form einer Rekurrenzgleichung mit Top-Down bestimmen

Question

Aufgabe:

Bestimmen Sie die geschlossene Form folgender Rekurrenzgleichungen.

T_1: {4^k | k ∈ ℕ} → ℚ

1.T₁(1) = 1,5; T₁(n) = 2T₁(n/4) + n für n ≥ 4

T₂: {3^k | k ∈ ℕ₀} → ℕ₀

2. T₂(1) = 0; T₂(n) = 3 * T₂(n/3) + log₃ n für alle n ∈ {3^k | k ∈ ℕ_≥1}

Problem/Ansatz:

Kann mir jemand erklären wie man mit der Top-Down Variante generell eine geschlossene Form findet? Oben hab ich 2 Beispielaufgaben wo ich die Variante angewandt habe aber ich schaff es einfach nicht daraus eine geschlossene Form zu basteln. Im folgenden zeige ich was ich bisher bei den beiden Aufgaben erreicht habe:

n=4^k

T₁(4^k) = 2T₁(\( \frac{4^k}{4} \) ) + 4^{k
           =} 2(2T₁(\( \frac{4^{k-1}}{4} \) ) + 4^k-1 ) + 4^{k
           =}  2(2(2T₁(\( \frac{4^{k-2}}{4} \) ) + 4^k-2) + 4 ^k-1 ) + 4k

Hier erkennt man schon eine Regelmäßigkeit und ich weiß, dass das jetzt solange ausgeführt wird bis wir bei
T₁(\( \frac{4^{k-(k-1)}}{4} \) ) angekommen sind. Aber ich schaff es nicht daraus eine geschlossene Form zu bilden. Bei der zweiten Rekurrenz bin ich genauso vorangegangen. Ich sehe dort eine Regelmäßigkeit aber daraus jetzt eine geschlossene Form zu bilden, bekomme ich einfach nicht hin.

Ich hoffe ihr könnt mir weiterhelfen.

Gruß,
hexadezimal

Answer 1

Zur ersten Aufgabe

$$ T_1\left(4^k\right) = 2 \cdot T_1\left(4^{k-1}\right) + 4^k = 2^2 \cdot T_1\left(4^{k-2}\right) +2 \cdot 4^{k-1} + 4^k $$ daraus erkennt man folgende Gesetzmäßigkeit

$$ T_1\left( 4^k \right) = 2^k T_1(1) + \sum_{j=0}^{k-1} 2^j 4^{k-j} $$ mit der Formel für die geometrische Reihe und ein wenig umformen bekommt man

$$ T_1\left( 4^k \right) = 2^{k-1} \left( 2^{k+2} -1 \right) $$