Master-Theorem Vollständige Induktion

Question

Aufgabe:

 Sei \( T(1)=b \) und \( T(n)=a T(n / c)+b n^{d} \) für Konstanten \( a, b, d>0 \) und \( c>1 \)
1. Zeigen Sie per Induktion, dass \( T(n)=\sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i} \cdot b n^{d} \) für alle \( n=c^{k} \) mit \( k \in \mathbb{N} \) gilt.

 Kann mir das jemand bitte vormachen?

Comments

Vom Duplikat:

Titel: Verstehe die Aufgabenstellung nicht und kann das Thema, weiß jemand, wie der Ablauf ist? Es geht um Master-Theorm

Stichworte: algorithmus

Sei T(1)=b und T(n)=aT(n/c)+bnd für Konstanten a,b,d>0 und c>1.
1. Zeigen Sie per Induktion, dass T(n)=∑ki=0(acd)i⋅bnd für alle n=ck mit k∈N gilt.
2. Beweisen Sie, dass für n=ck gilt:
T(n)≤O(ndlogn), wenn a=cd
T(n)≤O(nlogca), wenn a>cd

Kann mir da jemand weiterhelfen, ich verstehe es überhaupt nicht... :(

Answer 1

Das schaffst du doch bestimmt auch alleine:

Induktionsanfang: \( n = 1 = c^0 \) also \( k=0 \). Einfach nachrechnen, dass die Aussage stimmt

Induktionsschritt \( c^k \to c^{k+1} \) bzw. \( k \to k+1 \). Also

$$ T(c^{k+1}) = a T(c^k) + b\left(c^{k+1}\right)^{d} $$

da setzt du jetzt die Induktionsvoraussetzung ein:

$$ \begin{aligned} T(c^{k+1}) &= a \left( \sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i} \cdot b \left(c^k\right)^{d} \right) + b\left(c^{k+1}\right)^{d} \\ &= a \left( \sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i} \cdot b \left(c^d\right)^{k} \right) + b\left(c^{d}\right)^{k+1} \end{aligned} $$

Jetzt klammere \( b \left(c^d\right)^{k} \) aus (hängt ja nicht von i ab) und erweitere mit \( c^d \) :

$$ \begin{aligned} T(c^{k+1}) &= a b \left(c^d\right)^{k} \left( \sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i} \right) + b\left(c^{d}\right)^{k+1} \\ &= ab  \frac{\left(c^d\right)^{k+1}}{c^d} \left( \sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i} \right) + b\left(c^{d}\right)^{k+1} \end{aligned} $$

Wie könnte es weitergehen?

Comments

Vielen Dank, das hat mir bis jetzt sehr geholfen. Kannst du mir noch zeigen wie es richtig weitergeht? Ich bin noch relativ neu auf diesem Gebiet.

:)

---

Man klammert \( b(c^d)^{k+1} \) aus, zieht das \( \frac{a}{c^d} \) in die Summe, dann steht da i+1 im Exponent. Jetzt verschiebt man die Indizies: i=1 bis n+1 dann steht wieder i im Exponent und jetzt gilt

$$ \left( \frac{a}{c^d}  \right)^0 = 1 $$

---

Ich danke dir sehr, wirklich.

Folgt noch etwas oder sind wir dann fertig wenn das gilt?

:)

---

Du bist fertig, wenn du

$$ T(c^{k+1})=\sum \limits_{i=0}^{k+1}\left(\frac{a}{c^{d}}\right)^{i} \cdot b \left(c^{k+1}\right)^{d} $$

dastehen hast.

Jetzt verschiebt man die Indizies: i=1 bis n+1

Hier sollte es bis k+1 heißen.

---

Okay, danke!

:)

---

Kannst du zur Kontrolle mir noch die letzten Schritte aufschreiben? :)

---

$$ \begin{aligned} &ab  \frac{\left(c^d\right)^{k+1}}{c^d} \left( \sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i} \right) + b\left(c^{d}\right)^{k+1} \\&=\left( \frac{a}{c^d} \left( \sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i} \right) + 1\right) b\left(c^{d}\right)^{k+1} \\ &= \left( \sum \limits_{i=0}^{k}\left(\frac{a}{c^{d}}\right)^{i+1} + \left( \frac{a}{c^d}\right)^0\right) b\left(c^{d}\right)^{k+1} \\&=\sum \limits_{i=0}^{k+1}\left(\frac{a}{c^{d}}\right)^{i} \cdot b \left(c^{k+1}\right)^{d} \end{aligned} $$