Zeigen, dass eine Formel für alle n ∈ N0 gilt

Question

Aufgabe:

Zeigen, dass \( \sum\limits_{k=0}^{n}{k*2^k} \) = (n - 1)2ⁿ⁺¹ + 2 für alle n ∈ ℕ₀

Problem/Ansatz:

Ich weiß nie genau wie ich bei solchen Aufgaben vorgehen muss. Geht es da nur um umformen bzw. mit binomischem Formeln oder mit einer vollst. Induktion? Woher weiß ich wann ich was benutzen muss für so eine Aufgabe?

Ich habe nämlich versucht die Aufgabe durch umformen zu lösen, aber ich komme nie auf ein richtiges Ergebnis bzw. es sieht immer falsch aus und ich Ende mit einer komischen Umformung und eine Lösung habe ich leider auch nicht dazu.

Answer 1

Hallo vovi,

im Allgemeinen zeigt man dies mit einem Beweis mittels vollständiger Induktion. Das beginnt damit, zu zeigen, dass für ein kleines \(n\) - hier ist \(n=0\) bereits ok - die Gleichung stimmt. Das ist der Fall.

Anschließend zeigt man mit dieser Voraussetzung, dass es auch fü \(n+1\) gilt:$$\begin{aligned} \sum\limits_{k=0}^{n+1}{k\cdot 2^k} &= \sum\limits_{k=0}^{n}{k\cdot 2^k} \space + (n+1)2^{n+1} \\&= (n - 1)2^{n+1} + 2 + (n+1)2^{n+1} \\&= 2n \cdot 2^{n+1} + 2 \\&= ((n+1)-1)2^{(n+1)+1} + 2 \end{aligned}$$In der zweiten Zeile habe ich ausgenutzt, dass die Gleichung für \(n\) stimmt. Anschließend lässt sich der Term so umformen, dass die gleiche rechte Seite wie oben entsteht, nur eben mit \(n+1\) statt \(n\). Also wenn es für \(n=0\) gilt, gilt es auch für \(n=1\). Und wenn es für \(n=1\) gilt, dann gilt es auch für \(n=2\) usw.

Damit ist gezeigt, dass es für alle \(n \ge 0\) gilt.

Alternativ lässt sich der Term auch wie folgt umformen. Setze zunächst mal$$\sum\limits_{k=0}^{n}{k\cdot 2^k} = x$$und \(x\) ist unbekannt. Das dividiere man durch \(2\)$$\begin{aligned} \sum\limits_{k=0}^{n}{k\cdot 2^{k-1}} &= \frac 12 x \quad|\,k\to k+1\\ 0 + \sum\limits_{k=0}^{n-1}{(k+1)\cdot 2^{k}} &= \frac 12 x \end{aligned}$$ Anschließend führt man eine Indexverschiebung durch. Den ersten Summanden kann man weg lassen, da der \(=0\) ist.

Nun zieht man beide Summen von einander ab:$$\begin{aligned} x- \frac 12x &= \sum\limits_{k=0}^{n}{k\cdot 2^k} - \space \sum\limits_{k=0}^{n-1}{(k+1)\cdot 2^{k}} \\ &= n\cdot 2^n + \sum\limits_{k=0}^{n-1}{k\cdot 2^k} - \space \sum\limits_{k=0}^{n-1}{(k+1)\cdot 2^{k}} \\ &= n\cdot 2^n - \sum\limits_{k=0}^{n-1}{2^k} \\ &= n\cdot 2^n - \frac{1-2^{n}}{1-2} \\ &= n\cdot 2^n - (2^{n}-1) \\ \frac 12 x&= (n-1)\cdot 2^n +1\end{aligned}$$durch die Differenz der Summen erhält man eine geometrische Reihe, für die es eine geschlossene Formel gibt (s.o. 3. und 4.Zeile). Die Multiplikation mit \(2\) liefert das Ergebnis$$x = (n-1)\cdot 2^{n+1} +2$$

Noch ein Hinweis: im Allgemeinen ist es IMHO am einfachsten solche Terme durch den Beweis durch vollständige Induktion abzusichern. Sowohl die Lösung von Tschakabumba als auch diese Umformung hier sind nur in Sonderfällen möglich. Und man muss erst mal drauf kommen ;-)

Gruß Werner

Comments

Vielen Dank für die schnelle ausführliche Erklärung!

---

ich habe noch eine alternative Lösung hinzu gefügt. (s.o.)

Falls Du noch Fragen hast, so melde Dich bitte.

---

noch eine alternative Lösung

besteht darin, die Summe x zunächst einmal zeilenweise aufzuschreiben

x = 2^1
   + 2^2 + 2^2
   + 2^3 + 2^3 + 2^3
   + 2^4 + 2^4 + 2^4 + 2^4
   +  ...
   + 2^n + 2^n + 2^n + 2^n + ... + 2^n

und dann die geometrischen Reihen spaltenweise zu addieren

x = 2^1*(2^n-1) + 2^2*(2^n-1-1)+2^3*(2^n-2-1)+2^4*(2^n-3-1) + ... + 2^n*(2^n-(n-1)-1)

= 2ⁿ⁺¹ - 2^1 + 2ⁿ⁺¹ - 2^2 + 2ⁿ⁺¹ - 2^3 + 2ⁿ⁺¹ - 2^4 + ... +2ⁿ⁺¹ - 2^n

= n*2ⁿ⁺¹ - 2^1*(2^n - 1) = 2ⁿ⁺¹*(n-1) + 2

---

Ich bin Ihnen sehr dankbar für Ihre Hilfe! Jetzt habe ich es besser verstanden :)

Answer 2

Aloha :)

$$\sum\limits_{k=0}^nk\cdot2^k=\sum\limits_{k=1}^nk\cdot2^k=2\cdot\sum\limits_{k=1}^nk\cdot2^{k-1}=2\cdot\left[\sum\limits_{k=1}^n\frac{d}{dx}x^k\right]_{x=2}=2\cdot\left[\frac{d}{dx}\sum\limits_{k=1}^nx^k\right]_{x=2}$$$$\phantom{\sum\limits_{k=0}^nk\cdot2^k}=2\cdot\left[\frac{d}{dx}\left(\sum\limits_{k=0}^nx^k-1\right)\right]_{x=2}=2\cdot\left[\frac{d}{dx}\left(\frac{1-x^{n+1}}{1-x}-1\right)\right]_{x=2}$$$$\phantom{\sum\limits_{k=0}^nk\cdot2^k}=2\cdot\left[\frac{-(n+1)x^n\cdot(1-x)-(1-x^{n+1})\cdot(-1)}{(1-x)^2}\right]_{x=2}$$$$\phantom{\sum\limits_{k=0}^nk\cdot2^k}=2\cdot\frac{(n+1)2^n+(1-2^{n+1})}{(-1)^2}=2\cdot\left(n2^n+2^n+1-2\cdot2^n\right)$$$$\phantom{\sum\limits_{k=0}^nk\cdot2^k}=2\cdot\left(n2^n-2^n+1\right)=(n-1)\cdot2^{n+1}+2$$

Comments

Vielen vielen Dank für den ausführlichen Lösungsweg!

Wie genau wussten Sie, dass man so vorgehen muss? Also welche Regeln haben Sie da genau benutzt?

---

Nunja, man "muss" ja nicht so vorgehen. Werner hat ja den Weg über vollständige Induktion gewählt.

Mir war aufgefallen, dass \(k\cdot 2^k\) Ähnlichkeit mit \(k\cdot x^{k-1}\) hat, also der Ableitung von \(x^k\). Da für die Summe von \(x^k\) die Summenformel für die geometrische Reihe bekannt ist, war diese Vorgehensweise für mich naheliegend.

---

Oh, also haben Sie da ganz normale Umformungen mit binomischen Formeln gemacht oder wie? Oder wäre es ok, wenn sie mir ihren Lösungsweg kurz schrittweise erklären?