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

Man beweise mittels vollständiger Induktion:

$\sum _{j=1}^{n}j\ast 3^{j-1}=\frac{3^n\ast (2n-1)+1}{4}n\ge 1$

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
}}

Induktionsanfang: $n=1$ ergibt

Linke Seite: $1\ast 3^{1-1}=1$

Rechte Seite: $\frac{3^1\ast (2\ast 1-1)+1}{4}=\frac{4}{4}=1$

OK.

Induktionsvorraussetzung: Es muss gezeigt werden, dass gilt:

(Alle n durch n+1 ersetzt)

$\sum _{j=1}^{n+1}j\ast 3^{j-1}=\frac{3^{n+1}\ast (2(n+1)-1)+1}{4}$

Die weitere Auflösung der rechten Seite ergibt:

$\frac{3^{n+1}\ast (2n+1)+1}{4}$

Induktionsschluss: (Nachweis der Induktionsbehauptung)

Die rechte $(n+1)\ast 3^n$ zu addieren. Es soll sich ergeben:

$\frac{3^{n+1}\ast (2n+1)+1}{4}$

$\frac{3^n\ast (2n-1)+1}{4}+(n+1)\ast 3^n=$

$=\frac{3^n\ast (2n-1)+1+4(n+1)\ast 3^n}{4}=$

Wir heben $3^n$ hervor:

$=\frac{3^n\ast ((2n-1)+4(n+1))+1}{4}=$

$=\frac{3^n\ast (2n-1+4n+4)+1}{4}=$

$=\frac{3^n\ast (6n+3)+1}{4}=$

$=\frac{3\ast 3^n\ast (2n+1)+1}{4}=$

$=\frac{3^{n+1}\ast (2n+1)+1}{4}$

Q.e.d.