Laufzeitabschätzung von Heapsort

Question

Guten Tag liebe Community,

ich bitte euch mir diese Frage zu beantworten, das wäre super lieb. Danke ich im Voraus!

Komme hier einfach nicht weiter, da j in der summe vorkommt und weis nicht wie ich das

j außerhalb der Summe schreibe um durch die Induktionsvoraussetzung einen Teil ersetzen zu können.

Aus Duplikat:

Bei der Laufzeitabschätzung von Heapsort wird folgende Gleichheit für alle j ∈ ℕ₀ verwendet. Zeigen Sie diese: $\sum_{k=1}^{j-1}{{ 2 }^{ k-1 }(j-k)={ 2 }^{ j }-(j+1)}.$ Ich würde versuchen diese Formel mit der Induktion zu Beweisen.

Induktionsanfang:     j = 1;

$$\sum_{k=1}^{j}{{ 2 }^{ 0 }(0)={ 2 }^{ 1 }-(1+1)=0}$$ IA erfüllt.

InduktionsVorausetzung: 2^k-1 = 2^j   =>  k-1 = j  =>  k = j+1

Induktionsschritt:   j=j+1;

$$\sum_{k=1}^{j}{{ 2 }^{ k-1 }(j+1-k)={ 2 }^{ j+1 }-(j+1+1)}$$

Nach IV:
$$\sum_{k=1}^{j}{{ 2 }^{ k-1 }(j+1-k)={ 2 }^{ 1 }·{ 2 }^{ j }-(j+1+1)}$$ $$= \sum_{k=1}^{j}{1(j+1-k)=2-(j+1+1)}$$ $$\sum_{k=1}^{j}{(k-k)=2-(k+1)}$$


Ist das richtig?

Comments

Zum Duplikat:

Kurz und knapp: Nein. Deine Umformungen erscheinen mir willkürlich.

Answer 1

hier der Hinweis für die Summenaufteilung:

$$\sum_{k=1}^j 2^{k-1}(j+1-k) =\left( \sum_{k=1}^{j-1}2^{k-1}(j+1-k) \right) + 2^{j-1} \\ = \left( \sum_{k=1}^{j-1}2^{k-1}(j-k) \right)+ \left( \sum_{k=1}^{j-1}2^{k-1} \right)+2^{j-1}$$

Gruß

Comments

Danke sehr für die Antwort. Leider weis ich nicht wie man weiterrechnen kann hier. Könnten Sie diese Aufgabe bitte zuenderechnen?

Mit schönem Gruß

---

Für die erste Summe setze die IV ein, die zweite Summe ist eine geometrische Reihe:

$$... = 2^j-(j+1) + 2^{j-1}-1+2^{j-1}$$

Das wirst du wohl noch zusammen rechnen können oder?

---

Wie kommt man den nach dem ersten Schritt darauf einfach 2^j-1 zu addieren?

---

Man addiert nichts dazu. Es wurde der letzte Summand aus der Summe gezogen, sprich der Summand für $k=j$.

---

Tut mir wegen den blöden Fragen leid, aber ich will es nicht abschreiben und improvisieren bevor ich es verstanden habe.

Und warum wurde beim letzten Schritt in deiner Antwort beim zweiten Summand das (j-k) weggekürzt?

---

Wurde es nicht. Die Summe wurde in 2 Summen aufgeteilt, dabei wurde ausmultipliziert und das Assoziativgesetz verwendet.