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 ∈ ℕ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?
