TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 6

Man beweise mittels vollständiger Induktion:

$\sum _{j=0}^{n}j{2}^j=2^{n+1}(n-1)+2(n\ge 0)$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösung von Weaver

Induktionsanfang:

$n=0$

Zu zeigen ist also:

$\sum _{j=0}^{0}j{2}^j=2^1(-1)+2$

$0\ast 1=-2+2$

$0=0q.e.d.$

Induktionsvoraussetzung:

Diese entspricht der Angabe:

$\sum _{j=0}^{n}j{2}^j=2^{n+1}(n-1)+2$

Induktionsbehauptung:

Die durch die Gleichung beschriebene Eigenschaft überträgt sich von $n$ auf $n+1$:

$\sum _{j=0}^{n+1}j{2}^j=2^{n+2}(n)+2$

Induktionsschritt:

Wir betrachten die Induktionsbehauptung:

$\sum _{j=0}^{n+1}j{2}^j=2^{n+2}(n)+2$

Wir extrahieren den letzten Summanden (mit $j=n+1$) aus der Summe links:

$(\sum _{j=0}^{n}j{2}^j)+(n+1)2^{n+1}=2^{n+2}(n)+2$

Wir setzen aus der Induktionsvoraussetzung für die übrig gebliebene Summe ein:

$(2^{n+1}(n-1)+2)+(n+1)2^{n+1}=2^{n+2}(n)+2$

Wir subtrahieren auf beiden Seiten $2$ und heben links $2^{n+1}$ heraus:

$2^{n+1}(n-1+n+1)=2^{n+2}(n)$

Den resultierenden Faktor $2$ aus dem Klammernausdruck $2n$ links verschieben wir in den Exponenten der Potenz (erhöhen ihn also um $1$):

$2^{n+2}n=2^{n+2}nq.e.d.$