0 Daumen
273 Aufrufe

Aufgabe:

Bestimmen Sie die geschlossene Form folgender Rekurrenzgleichungen.

T1: {4k | k ∈ ℕ} → ℚ

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

T2: {3k | k ∈ ℕ0} → ℕ0

2. T2(1) = 0; T2(n) = 3 * T2(n/3) + log3 n für alle n ∈ {3k | 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

T1(4k) = 2T1(\( \frac{4^k}{4} \) ) + 4k
           = 
2(2T1(\( \frac{4^{k-1}}{4} \) ) + 4k-1 ) + 4k
           = 
2(2(2T1(\( \frac{4^{k-2}}{4} \) ) + 4k-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
T1(\( \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

von

1 Antwort

0 Daumen
 
Beste Antwort

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) $$

von 39 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort
+1 Daumen
1 Antwort
Gefragt 24 Okt 2016 von Gast

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community