0 Daumen
890 Aufrufe

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.



Bild Mathematik

Aus Duplikat:

Bei der Laufzeitabschätzung von Heapsort wird folgende Gleichheit für alle j ∈ ℕ0 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: 2k-1 = 2j   =>  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?
Avatar von
Zum Duplikat:

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

1 Antwort

+1 Daumen

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ß

Avatar von 23 k

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 2j-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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community