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: ∑k=1j−12k−1(j−k)=2j−(j+1). Ich würde versuchen diese Formel mit der Induktion zu Beweisen.
Induktionsanfang: j = 1;
k=1∑j20(0)=21−(1+1)=0 IA erfüllt.
InduktionsVorausetzung: 2k-1 = 2j => k-1 = j => k = j+1
Induktionsschritt: j=j+1;
k=1∑j2k−1(j+1−k)=2j+1−(j+1+1)
Nach IV:
k=1∑j2k−1(j+1−k)=21 · 2j−(j+1+1) =k=1∑j1(j+1−k)=2−(j+1+1) k=1∑j(k−k)=2−(k+1) Ist das richtig?